Nyeste kommentarer
Stevens notitser
Seneste Illustration
Seneste Gear
Populæreste kommentarer
Nyeste anmeldelser
Forslag?
Algoritme-kloge: kender I et program, der, givet en dansk ordbog, kan konstruere det størst mullige ordkvadrat?
Algoritme-kloge: kender I et program, der, givet en dansk ordbog, kan konstruere det størst mullige ordkvadrat? Et ordkvadrat ser sådan ud
HUN
ARA
LET
9 bogstaver skal give 3 ord vandret og 3 ord lodret. 16 ord skal give 4 ord vandret og 4 ord lodret.
3'ere kan laves i hånden. 4'ere er sværere og jeg tror ikke at man kan lave en 5'er i hånden inden for rimelig tid.
Kan man bevise at man ikke kan nå højere end en 5'er eller 6'er?
Log ind eller registrer dig for at lægge langtidsholdbare, konstruktive kommentarer.
Registrerede brugere får bedre editor og flere likes.
Kolofon
Alt indhold er © de respektive skribenter, illustratorer og fotografer. Kontakt dem ved at klikke på deres navn. Navnet står i toppen af artiklerne. Billeder kommer fra skribenterne, producenter, AI-illustratorer, emoji- og ikon-pakker og krediteres på artiklerne.
Internetforbrugeren.dk er bygget til videbegærlige dig og for sjov af Drupal-folkene fra Vertikal.dk. Abonnér med RSS (flere muligheder).
Privatlivspolitiken siger meget tydeligt, at du til en afveksling ikke udsættes for annoncer og tredjepartsovervågning her. Nyd det.
Ingen sponsorerede artikler / no sponsored posts fortæller folk, at Internetforbrugeren ikke gør sig i sponsorerede artikler.
Vi forsøger at vinde på integritet.
Kommentarer
"Bevise" vil jo nok blive noget med at godtgøre ved en søgning, for selvfølgelig findes der ordbøger hvor man kan konstruere arbitrært store kvadrater. Programmet der søger er til at forestille sig, men det er nemt at lave så forkert at det aldrig stopper....
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.
Okay, det toppede ved et kvarter for ord på 8 bogstaver, før processeringstiderne faldt igen, så det ser brugbart ud. Den rå udgave, der skal køres som JUnit-test, ligger på http://ekot.dk/diverse/SquareTest.java ⟲
Jeg laver det om til noget lidt mere direkte brugbart senere.
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.
Her til morgen har jeg så også søgt efter løsninger på problemet. Jeg kunne ikke umiddelbart finde kode, men fandt en fremragende Wikipedia-artikel:
http://en.wikipedia.org/wiki/Word_square ⟲
"A specimen of the order-six square (or 6-square) was first published in English in 1859; the 7-square in 1877; the 8-square in 1884; and the 9-square in 1897"
Det vi jager er dog en "Double word square", en lidt sværere variant. På engelsk er rekorden en 8'er - dog med 2 knap så korrekte ord. Hverdags-engelsk går altså, tror jeg, til 7. Så er det spørgsmålet om dansk også går til 7?
http://en.wikipedia.org/wiki/Word_square#Vocabulary ⟲ har i øvrigt en interessant pointe om ordkvadratkvalitet. Hyppigt brugte ord er mere værd end sjældent brugte ord og et ordkvadrat med et højt hverdagssprogindex er mere imponerende end noget der føles fremmed og konstrueret.
Ovenfor står der "ordkvadrat", "ordkvadratkvalitet" og "hverdagssprogindex". Tre udmærkede danske ord, der ikke findes i en ordbog, men giver mening. Spørgsmålet er om man med sammensatte ord (brødflov, bøgeflis, madmorforklæde) kunne nå længere end 7. -Ah, ved nærmere eftertanke: sammensatteord-dobbelt-ordkvadrater kunne konstrueres let ved at lægge 4'ere eller 5'ere side om side. Men de ville nok give 80% halvvrøvlede sammensatte ord.
Logologens afhandling om at finde en 10'er har mange af dine midnats-pointer, Toke: http://digitalcommons.butler.edu/cgi/viewcontent.cgi?article=4858&context=wordways ⟲
Og her er kode og eksempler, der - i min bog - viser at 7'ere nok er det længste man kan komme (på engelsk) uden at puste ordbogen op med lavkvalitetsord: http://gtoal.com/wordgames/wordsquare/ ⟲
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.
Med moderne hardware og lidt tålmodighed (læs: Lad det køre natten over) vil jeg mene at den klart største udfordring bliver at skaffe en nogenlunde autoritativ ordliste. Det ser nu ud til at denne opgave falder ind under http://www.dsn.dk/nyt/nyheder/2012/sprognaevnets-ordliste ⟲
Bum bum. Jeg må nok æde mine ord i mig igen... Efter at have hapset de rå ord fra da-source på http://da.speling.org/filer/ ⟲ er ordbogen vokset til 620K unikke ord og mit hurtige aftenhack har vist sig utilstrækkeligt. Nu lader jeg den lige køre natten over, men det ser ud til at der skal bruges flere tricks for at få acceptabel udførelsestid.
Jeg har rettet min kode så andre end mig kan bruge den, men du har jo givet link til langt mere modne implementationer. Skulle nogen alligevel være nysgerrige har jeg smidt mit foreløbige bud på http://ekot.dk/diverse/WordSquare.java ⟲
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.
Det er dog alligevel utrolig blæret. Men jo, selv med 6'ere er det nok svært at få et 100% korrekt, dansk ordkvadrat. Når du har fundet rigtig mange tror jeg, at jeg vil lære nogle af dem udenad og så sidde og lave dem henkastet i toget til sidemændenes benovelse. Jeg er dog mere fascineret af kvalitet end af kvantitet. En elegant 5'er er min i bog sjovere end en haltende 6'er. De der, der hælder ordbøger og stednavnsindexer på for at nå en 10'er, forstår jeg ikke helt.
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.
Ricco Førgaard Det er faktisk ret trivielt at finde de "magiske kvadrater". For ulige tal vil en 10 årig være i stand til at lave, da metoden er meget let. Ved "magiske kvadrater" skal summen også passe diagonalt. Ellers kalder man det "semi-magic". Det kan fint udvides til ord kvadrater, og det vil være lidt finere hvis de 2 diagonaler også danner et ord.
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.
Jeg er imponeret over jer, Toke Eskildsen og Thomas Egense . Jeg tror ikke på diagonaler. Ord har det med at have skiftevis vokaler og konsonanter og det duer slet ikke for den håndlavede 3'er, der startede tråden. 6'er-eksemplerne lover heller ikke godt for diagonal-ord. Jeg kan ikke forestille mig et ordkvadrat (størrelse 2-10) der kan levere bare to diagonal-ord.
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.
En perfekt 8'er! Jeg er imponeret! 5000 5x5 ordkvadrater med diagonaler! Endnu mere imponeret (og overrasket). Det bliver spændende at se de perfekte. 'aedes' optræder ikke i RO http://www.dsn.dk/ ⟲ eller mit dagligdags ordforråd, men de ~4998 andre 4'ere med diagonaler må næsten indeholde perfekte ord og gøre min fornemmelse til skamme. Jeg begynder helt at tænke i en webtjeneste, der serverer ordkvadrater til de hungrende masser.
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.
Ah! Jeg troede jeg blev spist af med ædes, fejlstavet. Vi har den første perfekte 5'er med 2 diagonaler!
Apps er yt, blev vi enige om i går https://plus.google.com/u/0/112786534420585287262/posts/8VkjE3Y9BWN ⟲ , og de tager lang tid at lave. Men jeg kunne godt forestille mig at fundne ordkvadrater kunne publiceres på en knapt så arbejdskrævende måde.
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!
PS. Egentlig ville det bare være en slags kryds-og-tværs, men det ville der jo heller ikke nødvendigvis være noget galt i.
Til eftertiden: ordkvadrat-projekt-side på http://ekot.dk/programmer/Ordkvadrat/ ⟲
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.
Thomas Emil Hansen: Jeps til det med ordlængden og RAM. Faktisk håber jeg at det hele kan pakkes ned så det ligger i level 2/3 cache. Langt størstedelen af processeringen handler om opslag og der giver det voldsomt meget at undgå forespørgsler til den langsomme RAM.
Jeg har ikke rodet med parallelisering, men du har ret i at det er meget nemt med denne opgave.
Det med flere søgeindex er interessant, da det er muligt at afgrænse de ord der skal afprøves ved at kigge på hvilke bogstaver der er mulige på bestemte pladser inde i ordene. Det er forøvrigt noget der passer rigtig godt til Trie-strukturen. Det svære er at lave afgrænsningslogikken så effektiv at det introducerede overhead er mindre end den tid der senere spares.
En af mine kollegaer var også inde på at anvende en heuristisk tilgang til at finde kvadraterne hurtigere. Min tilgang er lige nu er dog fokuseret på at bringe den samlede tid ned for en udtømmende søgning og en heuristik til at give en delmængde af resultaterne hurtigere vil (sandsynligvis) være på bekostning af den samlede udførelsestid.
> Faktisk håber jeg at det hele kan pakkes ned så det ligger i level 2/3 cache
Hvordan gør man det i Java?
Som med alle andre sprog: Lav strukturerne så små at der er plads til dem og til alt det andet skidt der konkurrerer om pladsen. Med Java er det så incl. den aktive del af JVMen, men med et så "lokalt" problem som ordkvadrater burde det også være muligt.
Ingen løsning for 15*15. Den var rimelig hurtig at køre igennem (1.5 time), og jeg vil nok også kunne afprøve alle 14*14 og måske 13*13...
Desværre er mit program pt. for langsomt til 9*9 og 10*10 - vil formodentlig tage mere end 1 år CPU.
Hvor mange ord er der for de forskellige ordlængder?
#længde : #ord
15:35296
14:43995
13:53319
12:61885
11:65396
10:62270
9:54876
8:43921
Men det er ikke kun antal ord der bestemmer tiden. Ved min 15*15 udregning kunne man kun udfylde de første 3-4 rækker maximalt og dermed bliver muligheder hurtigt undersøgt. Og netop fordi jeg var så langt fra en løsning med 15*15 er jeg umådeligt overbevist om der ikke findes en højere, men det kan heldigvis hurtigt testet, og det vil jeg g're i løbet af ugen. Altså >= 13 tilfældene.
Tilføj kommentar