Tilføj kommentar

Det er en sjov opgave, så jeg puslede lidt med den. Hovedet-under-armen brute force virker ikke spor godt, for med f.eks. 7 bogstaver er der "ord på 7 bogstaver"^7 kombinationer at kontrollere. Med min testordbog er det 5000^7 ~= 10^25, hvilket betyder at Solen brænder ud inden det bliver færdigt.

Der er nu er par nemme optimeringer: Hvis man starter oppefra og ned med at tilføje ord, er der ingen grund til tilføje flere ord, hvis man kan afgøre at der ikke findes ord der starter med de bogstaver fås ved at læse lodret ned. Dernæst kan man optimere ordbogsopslagene ved at lave en ordbog for hvert præfix fra længde 1 og op til ordenes længde. Med de to optimeringer røg tiden for ordlængde 6 ned fra anslået 20.000 år til 3 minutter, så jeg gad ikke rode med at tråde skidtet eller tænke videre (desuden er det sengetid).

Den eneste ordbog jeg havde ved hånden er den danske ispell (gys). Den siger at der er to løsninger af størrelse 6:

pragma

rumles

ambens

glente

mentor

assers

og

fisher

impala

spøgen

hagens

elende

ransel

hvoraf nummer to i hvert fald er noget hø og sikkert også nummer et.

Længder over 6 tager noget længere tid, så jeg sætter den til at køre resten af natten og melder tilbage i morgen hvor lang tid det tager. Hvis den ikke er færdig til den tid er de nævnte optimeringer ikke tilstrækkelige. Jeg kan hurtigt gøre koden mere generel og smide den et sted hvis du selv vil lege, men det bliver nok først i morgen aften. Det er skrevet i Java.