To ord er anagrammer av hverandre dersom de består av de samme tegnene, men i forskjellig rekkefølge. Hvert tegn må forekomme like mange ganger, og vi regner et ord som et anagram av seg selv. Anta at du har oppgitt en tekst, og et start-ord A og et slutt-ord B. Du ønsker å konstruere en sekvens med ord som starter med A og som slutter med B, med følgende krav: Hvis to ord X og Y står ved siden av hverandre i denne sekvensen, skal et anagram for X være brukt i samme setning som et anagram for Y. Beskriv svært kort en algoritme som avgjør om en slik sekvens eksisterer.

Denne oppgaven var det svært mange som hadde problemer med å forstå, og det kom mange spørsmål under eksamen. For å skjønne hva som foregår, begynner vi med å finlese oppgaveteksten litt:

To ord er anagrammer av hverandre dersom de består av de samme tegnene, men i forskjellig rekkefølge. Hvert tegn må forekomme like mange ganger, og vi regner et ord som et anagram av seg selv.

Dette er bare definisjonen av et anagram, i tilfelle man ikke har hørt om anagrammer før. Et poeng her er f.eks. at om vi sorterer bokstavene i to ord, så vil vi få samme resultat for begge ordene dersom de er anagrammer av hverandre. For eksempel, om vi sorterer bokstavene i "elvis" og "lives", så vil vi i begge tilfeller få "eilsv".

Vi leser videre:

Anta at du har oppgitt en tekst, og et start-ord A og et slutt-ord B.

Dette er altså input. En tekst og to ord. Det vil si, vi skal definere noe i retning Algorithm(T,A,B), der T er en tekst, A er et ord og B er et ord.

Du ønsker å konstruere en sekvens med ord som starter med A og som slutter med B …

Aå om A er "jeg" og B er "stien" så kan det f.eks. være vi vil konstruere sekvensen:

["jeg", "gikk", "en", "tur", "på", "stien"]

Men vi kan neppe konstruere en vilkårlig sekvens – da kunne vi jo bare ha svart [A, B], og vært ferdige. Nei, som vanlig så kommer det noen krav til resultatet:

… med følgende krav: Hvis to ord X og Y står ved siden av hverandre i denne sekvensen …

Aha, det er altså et krav til ord som skal stå ved siden av hverandre. F.eks. står "tur" og "på" ved siden av hverandre i sekvensen vår over. Det finnes altså en regel som avgjør om det er lovlig eller ikke:

… skal et anagram for X være brukt i samme setning som et anagram for Y.

Så i dette tilfellet må et anagram for "tur" og et anagram for "på" opptre i samme setning i T for at de skal få stå ved siden av hverandre i sekvensen vår.

Før vi beskriver en algoritme, må vi prøve å lage oss en slags beskrivelse eller modell av hva som foregår. En ting som nok er litt uklart er hvor ordene i svaret skal hentes fra. Skal de hentes fra teksten T? Kan de være vilkårlige strenger? Siden vi aldri sammenligner ord og ser om de er like – bare om de er anagrammer av hverandre – så blir dette faktisk helt ekvivalent. For å være på den sikre siden, kan vi tenke oss at ordene hentes fra T, men vi trenger altså ikke bry oss om det mens vi skisserer fremgangsmåten vår.

Hvordan avgjør vi om to ord kan stå etter hverandre i svaret? Vel, hvis det finnes en setning i T der begge ordene forekommer, så er svaret ja. Hvis det finnes en setning i T der et anagram av hver av ordene forekommer, så er svaret også ja. Om vi bare sorterer bokstavene i alle ordene, så bryr vi oss kun om hvorvidt ord er anagrammer av hverandre eller ikke (og ikke om de er like). Vi bytter altså ut "elvis" med "eilsv", etc., i teksten T. Vi kan nå glemme anagram-biten (siden den følger implisitt).

Vi har nå redusert problemet til en litt enklere variant:

Du ønsker å konstruere en sekvens med ord som starter med A og som slutter med B, med følgende krav: Hvis to ord X og Y står ved siden av hverandre i denne sekvensen, skal X være brukt i samme setning som Y.

Vi vil altså starte med A og bevege oss fra ord til ord, til vi kommer til B, men vi kan bare bevege oss mellom ord som forekommer i samme setning. (Hvert ord kan naturligvis forekomme i flere setninger.) Det blir det samme som å finne en sti fra A til B i en graf der nodene er ord, og det er en kant mellom X og Y dersom de forekommer i samme setning. For å finne en slik sti kan vi bruke vanlig traversering.

Løsningen i løsningsforslaget er litt annerledes (og atskillig mer ordknapp); i stedet for å lage en graf der ordene er noder, så legger vi ordene i en hashtabell, med referanser til nodene, men det blir i grunnen det samme.