torsdag 5. desember 2013 Julekalender
Jeg tar en liten statusoppdatering nå, selv om dagen er langt fra over. For dem som ikke har klart oppgaven enda kan man bruke dette til å i alle fall få med seg ett poeng.
Dagens oppgave gikk ut på å finne ut hvor like to forskjellige setninger var. På fagspråket kalles dette Levenshtein-distanse.
Jeg hadde hintet om at man kunne programmere for å finne løsningen, men regnet med at mange ville google og finne frem til online verktøy for å løse problemet. Og det hadde jeg nok rett i, for svarene haglet inn fra første minutt. Likevel er jeg imponert over hvor rask enkelte var.
Og aller raskest var Eric Carr. Han er CTO i selskapet TravelText, som forenkler reiseregnings-hverdagen din ved hjelp av en kreativ SMS-løsning. Eric ligger nå på 12-plass sammenlagt. Han kunne fortelle meg at:
"Heldigvis hadde jeg nettopp mekket på noe Levenshtein-greier og fikk kanskje et lite forsprang."
Ellers var gutta på poengtoppen raske til å svare også denne gang, og her er den oppdaterte topp-10-listen etter fem luker:
Stian, Dag Stuan, Jarle Stabell og Alf Kåre Lefdal avanserer, og skyver ut William Killerud, Bente C. Andorsen og Andreas Lien Olsen. Magnar Sveen gjeninntar lederposisjonen.
Hvis du ønsker å vite hvordan man kan kode seg frem til løsningen, så har jeg laget et eksempel i C#:
static int LevenshteinDistance(string s, string t)
{
int[,] d = new int[s.Length + 1, t.Length + 1];
for (int i = 0; i <= s.Length; i++)
d[i, 0] = i;
for (int j = 0; j <= t.Length; j++)
d[0, j] = j;
for (int j = 1; j <= t.Length; j++)
for (int i = 1; i <= s.Length; i++)
if (s[i - 1] == t[j - 1])
d[i, j] = d[i - 1, j - 1]; //no operation
else
d[i, j] = Math.Min(Math.Min(
d[i - 1, j] + 1, //a deletion
d[i, j - 1] + 1), //an insertion
d[i - 1, j - 1] + 1 //a substitution
);
return d[s.Length, t.Length];
}
Du kan lese mer om denne algoritmen på nettet.
Luken i morgen er en helt annen type oppgave, og minner kanskje mest om luke 1. Jeg tipper at noen veldig få vet svaret og tar det fra hukommelsen, mens alle andre kan finne det ut med litt smart søking. Så da kan du bare varme opp Google-muskelen din og være parat klokken 09:00 i morgen.