Seneste kommentarer

Et par tanker til optimering (som måske allerede er tænkt):

- Ordbogen skal naturligvis kun indeholde ord af den aktuelle længde. Laver man en 8'er skal alle ord i ordbogen være af længden 8.

- Ordbogen kan også optimeres med flere søgeindeks, så man ikke kun søger på ordenes begyndelsesbogstaver. Fordelen af en sådan optimering vil være afhængig af algoritmen, der benyttes.

- Parallelisering er opgaven er oplagt. Har man en maskine med flere processorer/kerner, kan de hver tage fra med næsten linær skalering.

- Jeg går ud fra, at ordbogen ligger i RAM. Selv en ordbog på 44.000 ord fylder kun meget lidt.

- En mere avanceret metode kunne være at vægte ordene efter anvendlighed. Ord med flere vokaler kunne f.eks. antages at kunne bruges i flere kombination end ord med et X i midten. Således kunne man starte med at søge efter ord, som er mere sandsynlige at få et godt resultat med. Man kommer ikke nødvendigvis hurtigere igennem det hele, men man vil hurtigere kunne få interessante resultater.

Tip1: Der er også en video med Martin Thorborg.

Tip2: Jeg har lavet videofremvisningssystemet.

Jeg tænker, kunne man lave det ligesom en slags Sudoku, hvor man skal udfylde de manglende bogstaver? Det ville være en app, der kunne sælge!

Imponerende! +1 til Toke Eskildsen fra mig.

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.