Seneste kommentarer

Ja, der er helt sikkert et enormt uudtalt behov for ordkvadrater blandt den danske befolkning! Men er det ikke en app man laver i disse tider? "Dagens ordkvadrat" eller måske "Ordfinurligheder"?

Jeg aer den ene af mine katte. Begge mine katte går hen og spiser. Den aedes madskål er størst.

Jeg synes bedre & bedre om den opgave du har stillet, Steven Snedker. Alternering mellem afprøvning af vandrette og lodrette ordkandidater gav mulighed for ordbogsreducering efter præfix og det gav såmænd også 10x højere hastighed (okay, det er løgn: Eftersom reduceringen betyder færre tests, relativt til korpus og kvadratstørrelse, er det nok snarere en ændring fra O(et eller andet) til O(noget mindre), men det er for langhåret til at jeg kan regne det ud). Det er bare slet ikke godt nok til en udtømmende søgning.

Den bedre hastighed resulterede dog i nogen bud hen over natten og fandt bl.a. 5000 5x5 ordkvadrater med diagonaler (den nåede til "afdet" som første ord, så det er langt fra det komplette svar). Et par af disse er

adict

tenes

opdra

moser

stuts

acids

genet

ordne

reren

asens

der begge har en diagonal med det fremragende ord 'aedes'. Den fandt også 4 8x8'ere der dog var uden diagonaler, f.eks.

abbedier

brunalge

buketten

eneboers

datoerne

ilterhed

egernene

rensedes

Nu vil jeg prøve at få fat i Sprognævnets ordliste, men ellers kunne man være så fræk at lave automatisk kontrol gennem deres webside, for de få kvadrater der er med større sidelængder.

Ikke overraskende er der forskel på folk, Steven Snedker: Med erkendelsen af at det ikke er nok med et hurtigt hack er det spændende for mig helt klart at lave noget der kan finde en 10'er. Elegante ordkvadrater er ... elegante, men mest som et kuriosum.

Lidt interessant fra tidligere tests med mindre ordbog er at større ordkvadrater ikke nødvendigvis er sværere. Jo længere ord, jo større sandsynlighed for at det tidligt i opbygningen kan afgøres at der ikke kan bygges videre. Dette skal så holdes op imod mængden af unikke ordbegyndelser ved den givne størrelse og det var så den kombination der toppede ved ordlængde 8 i mit gamle forsøg.

Lidt snak med kontorfællen Thomas Egense har resulteret i næste optimering der skal forsøges: Løbende reducering af ordbogens størrelse. Jeg kan selvfølgelig bare nærlæse de forskellige papers, men det er ikke sjovt at få den fulde løsning med det samme.

Meget interessant!

Dette problem findes også for tal, hvor man skal putte tallene fra 1-n i et m x m kvadrat, hvor n = m^2 og summen på alle led er n (også diagonalen). Enkelt for m=3, men allerede ved m=4 begynder det at blive utrolig vanskeligt.

Jeps, der skal spises ord. Eller rettere: Optimeres implementation. Den nåede én procent gennem 5x5 i løbet af natten og mindre end det for 6x6, 7x7 og 8x8. Den nåede dog at finde

ankrene

kanelen

trolige

arkader

nektere

treeren

sildens

Meeen "nektere" lyder lidt mystisk i mine ører og "related" helt forkert.

Både Logologens og gtoal's artikler ser gode ud (jeg har kun frokostpauseskimmet dem). Trie-tingen er nok det næste jeg vil benytte, hvis det bliver nødvendigt.

Det er ret sjovt med det historiske perspektiv, hvor det fremgår af artiklerne at der skulle spares på hukommelsen og i det hele taget laves mange tricks blot for at få overskuelige ordbøger og størrelser processeret.

Tak Toke! Det var dog fantastisk. Jeg blev interesseret i problemet i går eftermiddags da der dukkede et næsten perfekt ordkvadrat op under et spil Wordfeud.

Jeg tænkte på alle mulige snedige algoritmer og optimeringer, men kunne ikke lige se hvordan jeg bedst fik hul på problemet.

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.