[java] pentagram puzzle algoritme

[unconnected]

ik probeer in java een algoritme te bedenken dat aan de hand van een woordenlijst met woordjes van 5 letters (zie http://www.psc.edu/~burkardt/wordplay/pentagram.html) pentagrampuzzels maakt. er moet dus uiteindelijk een matrix uitkomen die van links naar rechts en van boven naar beneden woorden vormt (met woordjes uit die lijst hierboven).

een voorbeeldje:

code:

S A T O R
A R E P O
T E N E T
O P E R A
R O T A S

nou heb ik gisteravond een algoritme bedacht dat eerst random een woord pakt voor de eerste kolom, en dan bovenaan de lijst begint voor de 2de kolom en dan kijkt of de rijen geldige beginlettercombinaties vormen voor de woorden in de rijen. zo ja dan ga ik naar kolom 3. zo niet dan proberen we een nieuw woord uit de lijst.
is er geen woord mogelijk in kolom 3 dat goede beginlettercombinaties opleverd voor de woorden in de rijen dan spring ik 1 kolom terug en verander het woord in kolom 2.

met een korte woordenlijst (zoals een lijst met alleen de woordjes in het pentagram hierboven) was het algoritme in 1 seconde klaar. ik liet hem vanacht alleen los op de totale woordenlijst uit de url hierboven en vanochtend (na 7 uur proberen ) was hij nog steeds niet klaar... hij probeert gewoon teveel combinaties.

zijn laatste output was:

code:

raiaz
eatey
dragm
uglii
xhosn
column 4 is consistent
no matches found for column 5 -> resetting column 4

hij was dus nog steeds maar bij kolom 4 met proberen

het algoritme zoals ik het nu gebruik staat hier.

weet misschien iemand een beter algoritme? of enige optimalisaties die ik kan doorvoeren??

[djluc]

no matches found for column 5 -> resetting column

Zorg je er wel voor dat hij als alle items doorlopen zijn en nog steeds niets gevonden heeft dan kolom 3 wordt gereset?

[Vaan Banaan]

Volgens mij is het makkelijker, om in het midden te beginnen.
Je moet een symetrisch woord hebben.

Bijvoorbeeld: lepel
Dan moet het woord om het midden als 3de letter een 'e' hebben

code:

  l       o a
  e      opera
lepel     e e
  e      arepo  
  l       a o

En het buitenste woord in dit geval _ola_

edit:
Na tig keer editen is dit volgens mij toch wel goed.

[ Voor 18% gewijzigd door Vaan Banaan op 22-08-2003 12:53 ]

[Soultaker]

Als ik het probleem goed begrijp, dan kun je sowieso beginnen met alle woorden die niet omkeerbaar zijn, uit je woordenlijst gooien. "Opera" is bijvoorbeeld alleen bruikbaar als "Arepo" ook in je woordenlijst staat. Je kunt die twee woorden dus tegelijk invullen, zoals Vaan_Banaan al zei.

Verder weet je zeker dat in het midden (op de derde rij en in de derde kolom) een palindroom moet komen te staan (LEPEL, TENET, enzovoorts). Het is dus praktisch om een aparte lijst met alleen de palindromen uit je woordenlijst aan te leggen, zodat je het aantal iteraties van je algoritme enigszins kunt beperken.

Je hoeft dan dus maar drie woorden te kiezen (waarvan één woord een palindroom moet zijn). Het lijkt me dan handig om te beginnen met het woord dat de meeste beperkingen oplegt; dat is dus het woord in de eerste of de tweede rij (want die leveren elk twee letters van de overige woorden op) maar aan de andere kant is het aantal mogelijkheden voor het middelste woord een stuk kleiner, omdat dat uitsluitend palindromen zijn. Het is dus misschien toch het handigst om met het middelste woord te beginnen; welk woord je er daarna bij probeert, maakt niets uit, denk ik.

edit:
In jouw woordenlijst zitten een kleine 2000 oplossingen, trouwens.


edit:
En met de woorden in het Groene Boekje kun je helemaal niets.

[ Voor 10% gewijzigd door Soultaker op 23-08-2003 01:14 ]

[Soultaker]

Ik bedacht me trouwens nog dat dit probleem veel simpeler is dan het lijkt. Je hoeft nooit te backtracken en het is dus niet nodig om een handige volgorde te kiezen. Het enige wat van belang is, is dat je ervoor zorgt dat je uitsluitend passende woorden kiest. Voor de eerste regel kies je een willekeurig woord; voor de tweede regel een willekeurig woord waarvan de eerste en laatste letter corresponderen met de tweede en op-een-na-laatste letter van het eerste woord, en iets vergelijkbaars doe je voor het derde woord. Als het goed is vind je dan alle oplossingen dubbel, omdat de elk magisch vierkant gespiegeld kan worden over een diagonaal.

Met een slimme benadering van de woordenlijst, draait het hele algoritme dan in O(n) tijd, met n het totale aantal oplossingen (en dus niet het aantal woorden in de lijst!). Overigens is de woordenlijst die jij gaf nogal flauw; het gros bestaat uit (naar mijn mening) onzinnige woorden.

[unconnected]

dat idee met die palindromen had ik ook al bedacht, maar helaas was dat deel 2 van mijn opdracht, dus dat ging over

Configuring Pentagram Puzzles
Configure Word Pentagrams, with meaningful words from left to right and from top to bottom. Extend your program to also develope palindrome-pentagrams.

Soultaker schreef op 23 August 2003 @ 00:32:
Voor de eerste regel kies je een willekeurig woord; voor de tweede regel een willekeurig woord waarvan de eerste en laatste letter corresponderen met de tweede en op-een-na-laatste letter van het eerste woord, en iets vergelijkbaars doe je voor het derde woord. Als het goed is vind je dan alle oplossingen dubbel, omdat de elk magisch vierkant gespiegeld kan worden over een diagonaal.

even kijken of ik je goed begrijp hoor. je begint met een willekeurig woord (ik neem even de woorden uit het voorbeeld bovenaan):

S A T O R

dan pak je vervolgens een 2de willekeurig woord waarvan de eerste en laatste letters corresponderen met de tweede en op-een-na-laatste letter van het eerste woord:

S A T O R
A R E P O

voor het 3de woord doe je dan:

S A T O R
A R E P O
T E N E T

het 4de wordt het 2de woord maar dan gespiegeld. het 5de woord het 1ste woord gespiegeld ofzo. maar dan moeten die woorden wel bestaan, dus daar moet ik eerst op controleren... ik ga het ff proberen!!

[Soultaker]

unconnected schreef op 23 August 2003 @ 12:55:
even kijken of ik je goed begrijp hoor.

Lijkt er wel op!

maar dan moeten die woorden wel bestaan, dus daar moet ik eerst op controleren...

Ik had een test gemaakt waarin ik simpelweg alle woorden direct toevoeg in een aparte lijst, op basis van de eerste en laatste letter (voor het tweede woord) en op basis van de eerste twee letters (voor het laatste woord). In Java kun je iets vergelijkbaars doen.

Als je dus als eerste woord "SATOR" gekozen hebt, dan pak je voor het tweede woord de lijst met woorden die beginnen met "A" en eindigen op "O", en die probeer je allemaal; voor het derde woord pak je alle palindromen die beginnen met "TE".

[ Voor 20% gewijzigd door Soultaker op 23-08-2003 14:04 ]

[unconnected]

Soultaker schreef op 23 August 2003 @ 14:03:
In Java kun je iets vergelijkbaars doen.

het is me gelukt:

code:

-= CreatePentagramPuzzle =-

Start reading words
18554 words read

Trying to find reversed word of apers
<...>
Trying to find reversed word of meter

Start matrix: 

meter
-----
-----
-----
-----

Searching a word like e---e
word found: eadie, testing for reversability...
<...>
word found: edile, testing for reversability...

Start matrix: 

meter
edile
-----
-----
-----

Searching a word like ti-it
no such word found (pentagram not possible) -> trying a new start matrix...

Trying to find reversed word of lwala
<...>
Trying to find reversed word of gater

Start matrix: 

gater
edile
-----
-----
-----

Searching a word like a---e
word found: abade, testing for reversability...
<...>
word found: amene, testing for reversability...

Start matrix: 

gater
amene
-----
-----
-----

Searching a word like te-et

Start matrix: 

gater
amene
tebet
-----
-----

Final matrix: 

gater
amene
tebet
enema
retag

Elapsed time: 00:00:01
Done

hij doet het nu dus in een seconde!
hartstikke bedankt voor jullie hulp!