Hallo!
Ich habe hier ein Beispiel für ein Kreuzworträtzel-Algorithmus. gefunden, der im Prinzip auch gut funktioniert. Aktuell "schmeißt" der Algo. jedoch Wörter, die nicht mit anderen Wörtern verbunden sind einfach raus. Ich hätte diese jedoch gerne noch an der Seite platziert; dann eben ohne eine Verbindung...
Aktuell -- gewollt
_H_______ -- _H_______
WURM___ -- WURM____
_N_______ -- _N_____E_
_D_______ -- _D_____I_
Ich beschäftige mich mit dem Programmieren erst seit einigen Monaten und bin hier ganz klar an der Grenze meines Wissens angelangt :K
Vielen Dank schonmal im Vorraus!!!
Erweiterung eines Kreuzworträtzel-Algorithmus
-
BlackJack
@PCNB: Läuft das nicht einem *Kreuz*worträtsel zuwieder wenn sich Worte nicht kreuzen, und somit Hilfestellung geben beziehungsweise überhaupt erst überprüfbar machen ob man richtig liegt und nicht ein falsches oder alternatives Wort mit gleicher Länge gefunden hat. Nicht das sich kreuzende Worte dagegen 100% schützen, aber es ist immerhin unwahrscheinlicher das so etwas passiert.
Das Programm ist übrigens nicht so toll. Die `Crossword`-Klasse tut, enthält, und weiss viel zu viel. Das wird neben der schieren Anzahl von Attributen und Methoden in der `compute_crossword()`-Methode deutlich wo ein Kopie des Objekts erstellt wird auf dem einiges gemacht wird, um davon dann am Ende wieder Attribute auf das Objekt auf dem die Methode aufgerufen wurde zu übertragen. Das sieht sehr danach aus als wenn in der `Crossword`-Klasse mindestens zwei Datentypen vermengt sind die man trennen sollte.
Einiges ist kein idiomatisches Python wie zum Beispel das erstellen von Zeichenketten in dem da wiederholt Teilzeichenketten in Schleifen zusammengefügt werden und dabei in den Schleifen teilweise auch noch das ``for i in range(sequence):`` „anti pattern” verwendent wird. In der `display()`-Methode findet man dann auch noch eine Zuweisung bei der man sich fragen muss ob der Autor die Semantik von Python überhaupt verstanden hat:
Das Programm ist übrigens nicht so toll. Die `Crossword`-Klasse tut, enthält, und weiss viel zu viel. Das wird neben der schieren Anzahl von Attributen und Methoden in der `compute_crossword()`-Methode deutlich wo ein Kopie des Objekts erstellt wird auf dem einiges gemacht wird, um davon dann am Ende wieder Attribute auf das Objekt auf dem die Methode aufgerufen wurde zu übertragen. Das sieht sehr danach aus als wenn in der `Crossword`-Klasse mindestens zwei Datentypen vermengt sind die man trennen sollte.
Einiges ist kein idiomatisches Python wie zum Beispel das erstellen von Zeichenketten in dem da wiederholt Teilzeichenketten in Schleifen zusammengefügt werden und dabei in den Schleifen teilweise auch noch das ``for i in range(sequence):`` „anti pattern” verwendent wird. In der `display()`-Methode findet man dann auch noch eine Zuweisung bei der man sich fragen muss ob der Autor die Semantik von Python überhaupt verstanden hat:
Code: Alles auswählen
copy = self
for word in self.current_word_list:
copy.set_cell(word.col, word.row, word.number)
for r in range(copy.rows):
for c in copy.grid[r]:
outStr += '%s ' % c
outStr += '\n'Danke für die Antwort.
Ja, normalerweise ist dies nicht der Sinn eines Kreuzworträtzels; hier aber schon.
Dass das Programm nicht so toll ist hab ich mir schon fast gedacht; ist mir aber eigendlich egal, solange es läuft. Es muss nicht besonders schnell und "schön programmiert" sein.
Hast Du denn vielleicht eine Idee, wie man die zusätzliche Funktion einbauen könnte?
Ja, normalerweise ist dies nicht der Sinn eines Kreuzworträtzels; hier aber schon.
Dass das Programm nicht so toll ist hab ich mir schon fast gedacht; ist mir aber eigendlich egal, solange es läuft. Es muss nicht besonders schnell und "schön programmiert" sein.
Hast Du denn vielleicht eine Idee, wie man die zusätzliche Funktion einbauen könnte?
-
BlackJack
@PCNB: Man müsste sich halt mit dem Algorithmus auseinander setzen und die Stelle identifizieren an der er ”fertig” ist mit einem Rätsel und dort dann ansetzen und einen geeigneten neuen Startpunkt für ein noch nicht verwendetes Wort zu finden mit dem man den Algoritmus dann weiterlaufen lässt. Und das solange bis man, als neue Abbruchbedingung, keinen freien Platz mehr für einen neuen Startpunkt findet.
@PCNB: um es nochmal deutlich zu sagen: der Code ist so schlecht, dass ich schätzungsweise einige Stunden bräuchte, um ihn zu verstehen und die Stelle zu finden, wo man was ändern müßte. Freiwillig würde ich das nicht machen. In der Zeit könnte man wahrscheinlich sich selbst einen Algorithmus überlegen und umsetzen.
-
BlackJack
@PCNB: An sich ist der Algorithmus dort gar nicht mal so schlecht, aber die Umsetzung ist nicht so gut. Damit meine ich jetzt nicht den Quelltext selber, sondern zum Beispiel das er anscheinend grundsätzlich leere Kästchen neben platzierten Worten, ausser an den Kreuzungsstellen lässt. Damit wird Platz vergeuded und ausserdem werden von platzierten Worten dadurch effektiv nur jeder zweite Buchstabe überhaupt als Kandidat für andere Kreuzende Worte gelassen.
Und ich habe nicht überprüft ob der Warnhinweis stimmt, aber im Text des Blogbeitrags wird davor gewarnt kurze Worte zu verwenden die in längeren Worten vorkommen können, weil die dann ”in” diesen Worten platziert werden könnten. Das ist zum einen blöd, weil das vermeidbar wäre. Zum anderen würden sich kurze Worte eigentlich sehr gut zum füllen von Lücken eignen. Und dann frage ich mich gerade ob es dann nicht auch passieren kann, dass die Implementierung auch bei längeren Worten die Teilübereinstimmungen beim Anfang und Ende aufweisen, diese überlappend platziert, was man eigentlich auch verhindern sollte.
Ich habe mit dem grundsätzlichen Algorithmus, wie er in Worten im Blogbeitrag beschrieben ist, mal herumgespielt und bekomme deutlich kompaktere Belegungen. Nicht unbedingt mit mehr Worten, aber das sollte sich mit einer grösseren Datenbank als den 20 die dort im Beispielprogramm stehen, lösen lassen.
Und ich habe nicht überprüft ob der Warnhinweis stimmt, aber im Text des Blogbeitrags wird davor gewarnt kurze Worte zu verwenden die in längeren Worten vorkommen können, weil die dann ”in” diesen Worten platziert werden könnten. Das ist zum einen blöd, weil das vermeidbar wäre. Zum anderen würden sich kurze Worte eigentlich sehr gut zum füllen von Lücken eignen. Und dann frage ich mich gerade ob es dann nicht auch passieren kann, dass die Implementierung auch bei längeren Worten die Teilübereinstimmungen beim Anfang und Ende aufweisen, diese überlappend platziert, was man eigentlich auch verhindern sollte.
Ich habe mit dem grundsätzlichen Algorithmus, wie er in Worten im Blogbeitrag beschrieben ist, mal herumgespielt und bekomme deutlich kompaktere Belegungen. Nicht unbedingt mit mehr Worten, aber das sollte sich mit einer grösseren Datenbank als den 20 die dort im Beispielprogramm stehen, lösen lassen.