In letzter Zeit habe ich auf meinem iPhone ein Spiel namens Scramble gespielt. Einige von euch kennen dieses Spiel vielleicht als Boggle. Wenn das Spiel beginnt, erhalten Sie im Wesentlichen eine Buchstabenmatrix wie folgt:
F X I E
A M L O
E W B X
A S T U
Das Ziel des Spiels ist es, so viele Wörter wie möglich zu finden, die durch Verketten von Buchstaben gebildet werden können. Sie können mit jedem Buchstaben beginnen, und alle Buchstaben, die ihn umgeben, sind Freiwild. Sobald Sie mit dem nächsten Buchstaben fortfahren, sind alle Buchstaben, die diesen Buchstaben umgeben, Freiwild, mit Ausnahme aller zuvor verwendeten Buchstaben . So in dem Gitter oben, zum Beispiel könnte ich mit den Worten kommen LOB
, TUX
, SEA
, FAME
usw. Die Worte müssen mindestens 3 Zeichen lang sein, und nicht mehr als NxN Zeichen, die in diesem Spiel 16 sein würde , aber in einigen Implementierungen variieren kann . Während dieses Spiel Spaß macht und süchtig macht, bin ich anscheinend nicht sehr gut darin und wollte ein bisschen schummeln, indem ich ein Programm mache, das mir die bestmöglichen Wörter gibt (je länger das Wort, desto mehr Punkte bekommst du).
(Quelle: boggled.org )
Ich bin leider nicht sehr gut mit Algorithmen oder deren Effizienz und so weiter. Mein erster Versuch verwendet ein Wörterbuch wie dieses (~ 2,3 MB) und führt eine lineare Suche durch, um Kombinationen mit Wörterbucheinträgen abzugleichen. Das Auffinden der möglichen Wörter dauert sehr lange, und da Sie nur 2 Minuten pro Runde erhalten, ist dies einfach nicht ausreichend.
Ich bin gespannt, ob Stackoverflowers effizientere Lösungen finden können. Ich suche hauptsächlich nach Lösungen mit den Big 3 Ps: Python, PHP und Perl, obwohl alles mit Java oder C ++ auch cool ist, da Geschwindigkeit wichtig ist.
AKTUELLE LÖSUNGEN :
- Adam Rosenfield, Python, ~ 20er Jahre
- John Fouhy, Python, ~ 3s
- Kent Fredric, Perl, ~ 1s
- Darius Bacon, Python, ~ 1s
- rvarcher, VB.NET (Live-Link) , ~ 1s
- Paolo Bergantino, PHP (Live-Link) , ~ 5s (~ 2s lokal)
Antworten:
Meine Antwort funktioniert wie die anderen hier, aber ich werde sie veröffentlichen, da sie etwas schneller aussieht als die anderen Python-Lösungen, da das Wörterbuch schneller eingerichtet wird. (Ich habe dies mit John Fouhys Lösung verglichen.) Nach dem Einrichten ist die Zeit zum Lösen im Rauschen.
Beispielnutzung:
Bearbeiten: Filtern Sie Wörter heraus, die weniger als 3 Buchstaben lang sind.
Edit 2: Ich war neugierig, warum die Perl-Lösung von Kent Fredric schneller war. Es stellt sich heraus, dass anstelle einer Reihe von Zeichen eine Übereinstimmung mit regulären Ausdrücken verwendet wird. Wenn Sie dasselbe in Python tun, verdoppelt sich die Geschwindigkeit.
quelle
def neighbors((x, y))
(sinnlos, soweit ich sehen kann) eingestellt. Außerdem sind Klammern um das Argument erforderlichprint
.Die schnellste Lösung, die Sie erhalten, besteht wahrscheinlich darin, Ihr Wörterbuch in einem Versuch zu speichern . Erstellen Sie dann eine Warteschlange mit Triplets ( x , y , s ), wobei jedes Element in der Warteschlange einem Präfix s eines Wortes entspricht, das im Raster geschrieben werden kann und an der Position ( x , y ) endet . Initialisieren Sie die Warteschlange mit N x N Elementen (wobei N die Größe Ihres Rasters ist), einem Element für jedes Quadrat im Raster. Dann geht der Algorithmus wie folgt vor:
Wenn Sie Ihr Wörterbuch in einem Trie speichern, können Sie in konstanter Zeit testen, ob s + c ein Wort oder ein Präfix eines Wortes ist (vorausgesetzt, Sie behalten auch einige zusätzliche Metadaten in jedem Warteschlangendatum bei, z. B. einen Zeiger auf den aktuellen Knoten in der trie) ist die Laufzeit dieses Algorithmus also O (Anzahl der Wörter, die geschrieben werden können).
[Bearbeiten] Hier ist eine Implementierung in Python, die ich gerade codiert habe:
Anwendungsbeispiel:
Ausgabe:
Hinweise: Dieses Programm gibt keine Wörter mit 1 Buchstaben aus oder filtert überhaupt nicht nach Wortlänge. Das ist einfach hinzuzufügen, aber für das Problem nicht wirklich relevant. Einige Wörter werden auch mehrmals ausgegeben, wenn sie auf verschiedene Arten geschrieben werden können. Wenn ein bestimmtes Wort auf viele verschiedene Arten geschrieben werden kann (schlimmster Fall: Jeder Buchstabe im Raster ist derselbe (z. B. 'A') und ein Wort wie 'aaaaaaaaaa' in Ihrem Wörterbuch), wird die Laufzeit schrecklich exponentiell . Das Herausfiltern von Duplikaten und das Sortieren ist nach Abschluss des Algorithmus trivial.
quelle
(x,y)
, ein möglicher Anhänger ist(x+1,y+1)
. Dann(x+1,y+1)
wird in die Warteschlange geschoben. Doch(x,y)
auch das wird ein Nachfolger für sein(x+1,y+1)
, so wird das nicht führen zu einem unendlichen wieder zwischen ihnen abprallen?Für eine Wörterbuchbeschleunigung gibt es eine allgemeine Transformation / einen allgemeinen Prozess, mit dem Sie die Wörterbuchvergleiche im Voraus erheblich reduzieren können.
Da das obige Raster nur 16 Zeichen enthält, von denen einige doppelt vorhanden sind, können Sie die Anzahl der Gesamtschlüssel in Ihrem Wörterbuch erheblich reduzieren, indem Sie einfach Einträge mit nicht erreichbaren Zeichen herausfiltern.
Ich dachte, dies sei die offensichtliche Optimierung, aber als ich sah, dass niemand es tat, erwähne ich es.
Es reduzierte mich von einem Wörterbuch mit 200.000 Schlüsseln auf nur 2.000 Schlüssel, einfach während des Eingabedurchlaufs. Dies reduziert zumindest den Speicheraufwand und führt sicher zu einer Geschwindigkeitssteigerung, da der Speicher nicht unendlich schnell ist.
Perl-Implementierung
Meine Implementierung ist etwas kopflastig, da ich Wert darauf gelegt habe, den genauen Pfad jeder extrahierten Zeichenfolge zu kennen, nicht nur die Gültigkeit darin.
Ich habe dort auch einige Anpassungen, die theoretisch das Funktionieren eines Gitters mit Löchern und Gittern mit Linien unterschiedlicher Größe ermöglichen würden (vorausgesetzt, Sie haben die richtige Eingabe und es ist irgendwie ausgerichtet).
Der Early-Filter ist bei weitem der bedeutendste Engpass in meiner Anwendung, wie bereits vermutet, und kommentiert, dass die Zeile ihn von 1,5 auf 7,5 Sekunden aufbläht.
Bei der Ausführung scheint es, als ob alle einzelnen Ziffern ihre eigenen gültigen Wörter sind, aber ich bin mir ziemlich sicher, dass dies an der Funktionsweise der Wörterbuchdatei liegt.
Es ist ein bisschen aufgebläht, aber zumindest verwende ich Tree :: Trie von cpan wieder
Ein Teil davon wurde teilweise von den vorhandenen Implementierungen inspiriert, ein Teil davon hatte ich bereits im Sinn.
Konstruktive Kritik und Möglichkeiten, wie sie verbessert werden könnte, willkommen (/ ich stelle fest, dass er CPAN nie nach einem Boggle-Solver durchsucht hat , aber es hat mehr Spaß gemacht, daran zu arbeiten)
aktualisiert für neue Kriterien
Bogen- / Ausführungsinformationen zum Vergleich:
Weitere Murmeln zu dieser Regex-Optimierung
Die von mir verwendete Regex-Optimierung ist für Wörterbücher mit mehreren Lösungen nutzlos. Für Wörterbücher mit mehreren Lösungen benötigen Sie ein vollständiges Wörterbuch, kein vorab zugeschnittenes.
Allerdings ist es für einmalige Lösungen sehr schnell. (Perl Regex sind in C! :))
Hier sind einige unterschiedliche Code-Ergänzungen:
ps: 8,16 * 200 = 27 Minuten.
quelle
Sie könnten das Problem in zwei Teile aufteilen:
Im Idealfall sollte (2) auch eine Möglichkeit zum Testen enthalten, ob eine Zeichenfolge ein Präfix eines gültigen Wortes ist. Auf diese Weise können Sie Ihre Suche bereinigen und einen ganzen Haufen Zeit sparen.
Adam Rosenfields Trie ist eine Lösung für (2). Es ist elegant und wahrscheinlich das, was Ihr Algorithmus-Spezialist bevorzugen würde, aber mit modernen Sprachen und modernen Computern können wir etwas fauler sein. Wie Kent vorschlägt, können wir auch unsere Wörterbuchgröße reduzieren, indem wir Wörter verwerfen, deren Buchstaben nicht im Raster vorhanden sind. Hier ist etwas Python:
Beeindruckend; Präfix-Test mit konstanter Zeit. Das Laden des von Ihnen verknüpften Wörterbuchs dauert einige Sekunden, aber nur ein paar :-) (beachten Sie, dass
words <= prefixes
)Nun, für Teil (1) neige ich dazu, in Graphen zu denken. Also werde ich ein Wörterbuch erstellen, das ungefähr so aussieht:
dh
graph[(x, y)]
ist der Satz von Koordinaten, die Sie von der Position aus erreichen können(x, y)
. Ich werde auch einen Dummy-Knoten hinzufügen, der eineNone
Verbindung zu allem herstellt.Das Bauen ist etwas ungeschickt, da es 8 mögliche Positionen gibt und Sie die Grenzen überprüfen müssen. Hier ist ein entsprechend ungeschickter Python-Code:
Dieser Code erstellt auch eine Wörterbuchzuordnung
(x,y)
zum entsprechenden Zeichen. Auf diese Weise kann ich eine Liste von Positionen in ein Wort verwandeln:Schließlich führen wir eine Tiefensuche durch. Das grundlegende Verfahren ist:
Python:
Führen Sie den Code wie folgt aus:
und überprüfen Sie
res
, um die Antworten zu sehen. Hier ist eine Liste der für Ihr Beispiel gefundenen Wörter, sortiert nach Größe:Der Code benötigt (im wahrsten Sinne des Wortes) einige Sekunden, um das Wörterbuch zu laden, aber der Rest ist sofort auf meinem Computer.
quelle
range(len(w)+1)
stattdessen verwendenrange(len(w))
. Ich habe das behauptet,words <= prefixes
aber anscheinend habe ich das nicht getestet: - /Mein Versuch in Java. Das Lesen und Erstellen von Dateien dauert ca. 2 s und das Lösen des Puzzles ca. 50 ms. Ich habe das in der Frage verknüpfte Wörterbuch verwendet (es enthält einige Wörter, von denen ich nicht wusste, dass sie auf Englisch existieren, wie z. B. fae, ima).
Der Quellcode besteht aus 6 Klassen. Ich werde sie unten veröffentlichen (wenn dies nicht die richtige Vorgehensweise für StackOverflow ist, sagen Sie es mir bitte).
gineer.bogglesolver.Main
gineer.bogglesolver.Solver
gineer.bogglesolver.trie.Node
gineer.bogglesolver.trie.Trie
gineer.bogglesolver.util.Constants
gineer.bogglesolver.util.Util
quelle
Ich denke, Sie werden wahrscheinlich die meiste Zeit damit verbringen, Wörter zu finden, die möglicherweise nicht von Ihrem Buchstabenraster erstellt werden können. Das erste, was ich tun würde, ist zu versuchen, diesen Schritt zu beschleunigen, und das sollte Sie den größten Teil des Weges dorthin bringen.
Zu diesem Zweck würde ich das Raster erneut als Tabelle möglicher "Bewegungen" ausdrücken, die Sie durch den Buchstabenübergang indizieren, den Sie betrachten.
Beginnen Sie, indem Sie jedem Buchstaben eine Nummer aus Ihrem gesamten Alphabet zuweisen (A = 0, B = 1, C = 2, ... usw.).
Nehmen wir dieses Beispiel:
Und jetzt wollen wir das Alphabet der Buchstaben verwenden, die wir haben (normalerweise möchten Sie wahrscheinlich jedes Mal das gleiche ganze Alphabet verwenden):
Anschließend erstellen Sie ein boolesches 2D-Array, das angibt, ob ein bestimmter Buchstabenübergang verfügbar ist:
Gehen Sie nun Ihre Wortliste durch und konvertieren Sie die Wörter in Übergänge:
Überprüfen Sie dann, ob diese Übergänge zulässig sind, indem Sie sie in Ihrer Tabelle nachschlagen:
Wenn sie alle erlaubt sind, besteht die Möglichkeit, dass dieses Wort gefunden wird.
Zum Beispiel kann das Wort "Helm" beim 4. Übergang (m zu e: helMEt) ausgeschlossen werden, da dieser Eintrag in Ihrer Tabelle falsch ist.
Und das Wort Hamster kann ausgeschlossen werden, da der erste (h zu a) Übergang nicht erlaubt ist (existiert nicht einmal in Ihrer Tabelle).
Versuchen Sie nun, die wahrscheinlich wenigen verbleibenden Wörter, die Sie nicht entfernt haben, tatsächlich im Raster so zu finden, wie Sie es jetzt tun, oder wie in einigen anderen Antworten hier vorgeschlagen. Dies dient dazu, Fehlalarme zu vermeiden, die sich aus Sprüngen zwischen identischen Buchstaben in Ihrem Raster ergeben. Zum Beispiel ist das Wort "Hilfe" in der Tabelle zulässig, nicht jedoch im Raster.
Einige weitere Tipps zur Leistungsverbesserung zu dieser Idee:
Verwenden Sie anstelle eines 2D-Arrays ein 1D-Array und berechnen Sie einfach den Index des zweiten Buchstabens selbst. Erstellen Sie also anstelle eines 12x12-Arrays wie oben ein 1D-Array mit der Länge 144. Wenn Sie dann immer dasselbe Alphabet verwenden (dh ein 26x26 = 676x1-Array für das englische Standardalphabet), auch wenn nicht alle Buchstaben in Ihrem Raster angezeigt werden können Sie die Indizes in diesem 1D-Array vorberechnen, die Sie testen müssen, um mit Ihren Wörterbuchwörtern übereinzustimmen. Zum Beispiel wären die Indizes für 'Hallo' im obigen Beispiel
Erweitern Sie die Idee auf eine 3D-Tabelle (ausgedrückt als 1D-Array), dh alle zulässigen 3-Buchstaben-Kombinationen. Auf diese Weise können Sie sofort noch mehr Wörter entfernen und die Anzahl der Array-Suchvorgänge für jedes Wort um 1 reduzieren: Für "Hallo" benötigen Sie nur 3 Array-Suchvorgänge: hel, ell, llo. Es wird übrigens sehr schnell gehen, diese Tabelle zu erstellen, da es nur 400 mögliche 3-Buchstaben-Bewegungen in Ihrem Raster gibt.
Berechnen Sie die Indizes der Bewegungen in Ihrem Raster vor, die Sie in Ihre Tabelle aufnehmen müssen. Für das obige Beispiel müssen Sie die folgenden Einträge auf 'True' setzen:
Ich bin sicher, wenn Sie diesen Ansatz verwenden, können Sie Ihren Code wahnsinnig schnell ausführen, wenn Sie das Wörterbuch vorberechnet und bereits in den Speicher geladen haben.
Übrigens: Eine andere nette Sache, wenn Sie ein Spiel erstellen, ist es, solche Dinge sofort im Hintergrund auszuführen. Beginnen Sie mit dem Generieren und Lösen des ersten Spiels, während der Benutzer noch auf den Titelbildschirm Ihrer App schaut und seinen Finger in Position bringt, um "Play" zu drücken. Generieren und lösen Sie dann das nächste Spiel, während der Benutzer das vorherige spielt. Das sollte Ihnen viel Zeit geben, um Ihren Code auszuführen.
(Ich mag dieses Problem, daher werde ich wahrscheinlich versucht sein, meinen Vorschlag in den nächsten Tagen in Java umzusetzen, um zu sehen, wie er tatsächlich funktionieren würde. Ich werde den Code hier veröffentlichen, sobald ich dies tue.)
AKTUALISIEREN:
Ok, ich hatte heute etwas Zeit und habe diese Idee in Java umgesetzt:
Hier sind einige Ergebnisse:
Für das Raster aus dem Bild in der Originalfrage (DGHI ...):
Für die Briefe, die als Beispiel in der ursprünglichen Frage veröffentlicht wurden (FXIE ...)
Für das folgende 5x5-Raster:
es gibt dies:
Dafür habe ich die TWL06 Tournament Scrabble Word List verwendet , da der Link in der ursprünglichen Frage nicht mehr funktioniert. Diese Datei ist 1,85 MB groß und daher etwas kürzer. Und der
buildDictionary
Funktion wirft alle Wörter mit weniger als 3 Buchstaben aus.Hier einige Beobachtungen zur Leistung:
Es ist ungefähr zehnmal langsamer als die gemeldete Leistung der OCaml-Implementierung von Victor Nicollet. Ob dies durch den unterschiedlichen Algorithmus, das kürzere Wörterbuch, das er verwendet hat, die Tatsache, dass sein Code kompiliert wird und meiner in einer virtuellen Java-Maschine ausgeführt wird, oder die Leistung unserer Computer (meiner ist ein Intel Q6600 mit 2,4 MHz unter WinXP) verursacht wird, Ich weiß es nicht. Es ist jedoch viel schneller als die Ergebnisse für die anderen Implementierungen, die am Ende der ursprünglichen Frage angegeben sind. Ob dieser Algorithmus dem Trie-Wörterbuch überlegen ist oder nicht, weiß ich derzeit noch nicht.
Die in verwendete Tabellenmethode
checkWordTriplets()
liefert eine sehr gute Annäherung an die tatsächlichen Antworten. Nur 1 von 3-5 Wörtern, die von ihm bestanden wurden, besteht dencheckWords()
Test nicht (siehe Anzahl der Kandidaten im Vergleich zur Anzahl der tatsächlichen Wörter oben).Was Sie oben nicht sehen können: Die
checkWordTriplets()
Funktion dauert ca. 3,65 ms und ist daher im Suchprozess voll dominant. DiecheckWords()
Funktion nimmt so ziemlich die verbleibenden 0,05 bis 0,20 ms ein.Die Ausführungszeit der
checkWordTriplets()
Funktion hängt linear von der Wörterbuchgröße ab und ist praktisch unabhängig von der Kartengröße!Die Ausführungszeit von
checkWords()
hängt von der Kartengröße und der Anzahl der Wörter ab, die nicht ausgeschlossen sindcheckWordTriplets()
.Die
checkWords()
obige Implementierung ist die dümmste erste Version, die ich mir ausgedacht habe. Es ist grundsätzlich überhaupt nicht optimiert. Aber im Vergleich dazu istcheckWordTriplets()
es für die Gesamtleistung der Anwendung irrelevant, also habe ich mir darüber keine Sorgen gemacht. Aber , wenn die Plattengröße größer wird, wird diese Funktion erhalten langsamer und langsamer und wird schließlich auf die Materie beginnen. Dann müsste es auch optimiert werden.Eine schöne Sache an diesem Code ist seine Flexibilität:
initializeBoard()
.Ok, aber ich denke jetzt ist dieser Beitrag waaaay lang genug. Ich kann definitiv alle Ihre Fragen beantworten, aber lassen Sie uns das zu den Kommentaren verschieben.
quelle
ok = possibleTriplets[entry.triplets[t]];
. hmm?entry.letters[i] = (byte) letter - 65;
Er nimmt einfach den ASCII-Wert und subtrahiert 65 ("A"). Wenn Ihr Wörterbuch Umlaute oder Kleinbuchstaben enthält, ergeben sich Werte über 31, die durch die Einstellung der Alphabetgröße in Zeile 9 nicht geplant sind. Um andere Buchstaben zu unterstützen, müssten Sie diese Zeile erweitern um sie in den Bereich abzubilden, der durch die Alphabetgröße zulässig ist.Überraschenderweise versuchte niemand eine PHP-Version davon.
Dies ist eine funktionierende PHP-Version von John Fouhys Python-Lösung.
Obwohl ich einige Hinweise aus den Antworten aller anderen genommen habe, wird dies größtenteils von John kopiert.
Hier ist ein Live-Link wenn Sie es ausprobieren möchten. Obwohl es auf meinem lokalen Computer ~ 2 Sekunden dauert, dauert es auf meinem Webserver ~ 5 Sekunden. In beiden Fällen ist es nicht sehr schnell. Trotzdem ist es ziemlich abscheulich, so dass ich mir vorstellen kann, dass die Zeit erheblich reduziert werden kann. Hinweise, wie dies erreicht werden kann, sind willkommen. Das Fehlen von Tupeln in PHP machte es seltsam, mit den Koordinaten zu arbeiten, und meine Unfähigkeit, genau zu verstehen, was zum Teufel los ist, half überhaupt nichts.
BEARBEITEN : Mit einigen Korrekturen dauert es lokal weniger als 1 Sekunde.
quelle
Sie interessieren sich nicht für VB? :) Ich konnte nicht widerstehen. Ich habe dies anders gelöst als viele der hier vorgestellten Lösungen.
Meine Zeiten sind:
BEARBEITEN: Die Ladezeiten des Wörterbuchs auf dem Webhostserver dauern etwa 1 bis 1,5 Sekunden länger als auf meinem Heimcomputer.
Ich weiß nicht, wie stark sich die Zeiten mit einer Auslastung des Servers verschlechtern werden.
Ich habe meine Lösung als Webseite in .Net geschrieben. myvrad.com/boggle
Ich verwende das Wörterbuch, auf das in der ursprünglichen Frage verwiesen wird.
Buchstaben werden nicht in einem Wort wiederverwendet. Es werden nur Wörter mit 3 oder mehr Zeichen gefunden.
Ich verwende eine Hashtabelle aller eindeutigen Wortpräfixe und Wörter anstelle eines Versuchs. Ich wusste nichts über Tries, also habe ich dort etwas gelernt. Die Idee, zusätzlich zu den vollständigen Wörtern eine Liste mit Präfixen von Wörtern zu erstellen, hat meine Zeit schließlich auf eine respektable Zahl gebracht.
Lesen Sie die Codekommentare für weitere Details.
Hier ist der Code:
quelle
Sobald ich die Problemstellung sah, dachte ich "Trie". Da jedoch mehrere andere Poster von diesem Ansatz Gebrauch machten, suchte ich nach einem anderen Ansatz, um anders zu sein. Leider ist der Trie-Ansatz besser. Ich habe Kents Perl-Lösung auf meinem Computer ausgeführt und die Ausführung dauerte 0,31 Sekunden, nachdem ich sie an die Verwendung meiner Wörterbuchdatei angepasst hatte. Meine eigene Perl-Implementierung benötigte 0,54 Sekunden, um ausgeführt zu werden.
Das war mein Ansatz:
Erstellen Sie einen Übergangs-Hash, um die rechtlichen Übergänge zu modellieren.
Durchlaufen Sie alle 16 ^ 3 möglichen Drei-Buchstaben-Kombinationen.
Durchlaufen Sie dann alle Wörter im Wörterbuch.
Drucken Sie die gefundenen Wörter aus.
Ich habe 3-Buchstaben- und 4-Buchstaben-Sequenzen ausprobiert, aber 4-Buchstaben-Sequenzen haben das Programm verlangsamt.
In meinem Code verwende ich / usr / share / dict / words für mein Wörterbuch. Es ist Standard bei MAC OS X und vielen Unix-Systemen. Sie können eine andere Datei verwenden, wenn Sie möchten. Um ein anderes Puzzle zu knacken, ändern Sie einfach die Variable @puzzle. Dies wäre für größere Matrizen leicht anzupassen. Sie müssten nur den% Transitions-Hash und den% legalTransitions-Hash ändern.
Die Stärke dieser Lösung besteht darin, dass der Code kurz und die Datenstrukturen einfach sind.
Hier ist der Perl-Code (der, wie ich weiß, zu viele globale Variablen verwendet):
quelle
Ich weiß, dass ich super spät bin, aber ich habe vor einiger Zeit eines davon in PHP gemacht - nur zum Spaß auch ...
http://www.lostsockdesign.com.au/sandbox/boggle/index.php?letters=fxieamloewbxastu 75 Wörter (133 Punkte) in 0,90108 Sekunden gefunden
F.........X..I..............E............... A......................................M..............................L............................O............................... E....................W............................B..........................X A..................S..................................................T.................U....
Gibt einen Hinweis darauf, was das Programm tatsächlich tut - in jedem Buchstaben beginnt es, durch die Muster zu schauen, während jedes '.' zeigt einen Pfad, den es versucht hat zu nehmen. Je mehr '.' es gibt je weiter es gesucht hat.
Lassen Sie mich wissen, wenn Sie den Code wollen ... es ist eine schreckliche Mischung aus PHP und HTML, die nie das Licht der Welt erblicken sollte, also wage ich es nicht, sie hier zu posten: P.
quelle
Ich habe 3 Monate an einer Lösung für das Problem mit den 10 besten 5x5 Boggle-Boards gearbeitet.
Das Problem ist jetzt gelöst und auf 5 Webseiten vollständig offengelegt. Bitte kontaktieren Sie mich bei Fragen.
Der Board-Analysealgorithmus verwendet einen expliziten Stapel, um die Board-Quadrate pseudorekursiv durch ein gerichtetes azyklisches Wortdiagramm mit direkten untergeordneten Informationen und einem Zeitstempel-Verfolgungsmechanismus zu durchlaufen. Dies ist möglicherweise die weltweit fortschrittlichste Lexikon-Datenstruktur.
Das Schema bewertet ungefähr 10.000 sehr gute Platinen pro Sekunde auf einem Quad-Core. (9500+ Punkte)
Übergeordnete Webseite:
DeepSearch.c - http://www.pathcom.com/~vadco/deep.html
Komponentenwebseiten:
Optimale Anzeigetafel - http://www.pathcom.com/~vadco/binary.html
Erweiterte Lexikonstruktur - http://www.pathcom.com/~vadco/adtdawg.html
Board-Analyse-Algorithmus - http://www.pathcom.com/~vadco/guns.html
Parallele Stapelverarbeitung - http://www.pathcom.com/~vadco/parallel.html
- Dieses umfassende Werk wird nur eine Person interessieren, die das Beste verlangt.
quelle
Verringert Ihr Suchalgorithmus die Wortliste kontinuierlich, während Ihre Suche fortgesetzt wird?
Zum Beispiel gibt es in der obigen Suche nur 13 Buchstaben, mit denen Ihre Wörter beginnen können (effektiv reduziert auf die Hälfte der Anfangsbuchstaben).
Wenn Sie weitere Buchstabenpermutationen hinzufügen, werden die verfügbaren Wortsätze weiter verringert, wodurch die erforderliche Suche verringert wird.
Ich würde dort anfangen.
quelle
Ich müsste mir mehr Gedanken über eine Komplettlösung machen, aber als praktische Optimierung frage ich mich, ob es sich lohnen könnte, eine Tabelle mit Häufigkeiten von Digrammen und Trigrammen (2- und 3-Buchstaben-Kombinationen) vorab zu berechnen Wörter aus Ihrem Wörterbuch und verwenden Sie diese, um Ihre Suche zu priorisieren. Ich würde mit den Anfangsbuchstaben der Wörter gehen. Wenn Ihr Wörterbuch also die Wörter "Indien", "Wasser", "Extrem" und "Außergewöhnlich" enthält, lautet Ihre vorberechnete Tabelle möglicherweise:
Suchen Sie dann nach diesen Digrammen in der Reihenfolge der Gemeinsamkeiten (zuerst EX, dann WA / IN).
quelle
Lesen Sie zunächst, wie einer der C # -Sprachendesigner ein verwandtes Problem gelöst hat: http://blogs.msdn.com/ericlippert/archive/2009/02/04/a-nasality-talisman-for-the-sultana-analyst.aspx .
Wie er können Sie mit einem Wörterbuch beginnen und Wörter kanonisieren, indem Sie ein Wörterbuch aus einer Reihe von Buchstaben erstellen, die alphabetisch sortiert sind, und eine Liste von Wörtern erstellen, die aus diesen Buchstaben geschrieben werden können.
Erstellen Sie als Nächstes die möglichen Wörter an der Tafel und suchen Sie sie nach. Ich vermute, das wird dich ziemlich weit bringen, aber es gibt sicherlich mehr Tricks, die die Dinge beschleunigen könnten.
quelle
Ich schlage vor, einen Baum aus Buchstaben zu erstellen, der auf Wörtern basiert. Der Baum würde aus folgenden Buchstabenstrukturen bestehen:
Dann bauen Sie den Baum auf, wobei jede Tiefe einen neuen Buchstaben hinzufügt. Mit anderen Worten, auf der ersten Ebene würde es das Alphabet geben; Dann würde es von jedem dieser Bäume weitere 26 Einträge geben und so weiter, bis Sie alle Wörter buchstabiert haben. Halten Sie sich an diesen analysierten Baum, damit alle möglichen Antworten schneller nachgeschlagen werden können.
Mit diesem analysierten Baum können Sie sehr schnell Lösungen finden. Hier ist der Pseudocode:
Dies könnte mit etwas dynamischer Programmierung beschleunigt werden. In Ihrem Beispiel stehen die beiden 'A' neben einem 'E' und einem 'W', die (von dem Punkt an, an dem sie sie treffen) identisch wären. Ich habe nicht genug Zeit, um den Code dafür wirklich zu formulieren, aber ich denke, Sie können die Idee sammeln.
Ich bin mir auch sicher, dass Sie andere Lösungen finden werden, wenn Sie Google nach "Boggle Solver" suchen.
quelle
Nur zum Spaß habe ich eine in Bash implementiert. Es ist nicht super schnell, aber vernünftig.
http://dev.xkyle.com/bashboggle/
quelle
Urkomisch. Ich habe vor ein paar Tagen wegen des gleichen verdammten Spiels fast dieselbe Frage gestellt! Ich habe es jedoch nicht getan, weil ich gerade bei Google nach Boggle Solver Python gesucht und alle Antworten bekommen habe, die ich mir wünschen konnte.
quelle
Mir ist klar, dass die Zeit dieser Frage gekommen und gegangen ist, aber da ich selbst an einem Löser gearbeitet habe und beim Googeln darauf gestoßen bin, dachte ich, ich sollte einen Verweis auf meine veröffentlichen, da er sich von einigen anderen etwas zu unterscheiden scheint.
Ich entschied mich für ein flaches Array für das Spielbrett und für rekursive Jagden von jedem Buchstaben auf dem Brett, wobei ich von einem gültigen Nachbarn zu einem gültigen Nachbarn überging und die Jagd erweiterte, wenn die aktuelle Liste der Buchstaben ein gültiges Präfix in einem Index war. Beim Durchlaufen des Begriffs des aktuellen Wortes wird eine Liste von Indizes in die Tafel aufgenommen, nicht die Buchstaben, aus denen ein Wort besteht. Bei der Überprüfung des Index werden die Indizes in Buchstaben übersetzt und die Prüfung durchgeführt.
Der Index ist ein Brute-Force-Wörterbuch, das ein bisschen wie ein Versuch ist, aber pythonische Abfragen des Index zulässt. Wenn die Wörter "Katze" und "Cater" in der Liste enthalten sind, erhalten Sie dies im Wörterbuch:
Wenn das aktuelle_Wort also 'ca' lautet, wissen Sie, dass es sich um ein gültiges Präfix handelt, da
'ca' in d
True zurückgegeben wird (fahren Sie also mit dem Board-Traversal fort). Und wenn das aktuelle_Wort 'cat' ist, wissen Sie, dass es ein gültiges Wort ist, da es ein gültiges Präfix und ist'cat' in d['cat']
True zurückgibt.Wenn Sie dies für richtig halten, können Sie lesbaren Code verwenden, der nicht zu langsam erscheint. Wie bei allen anderen sind die Kosten in diesem System das Lesen / Erstellen des Index. Das Lösen des Boards ist ziemlich laut.
Der Code befindet sich unter http://gist.github.com/268079 . Es ist absichtlich vertikal und naiv mit vielen expliziten Gültigkeitsprüfungen, weil ich das Problem verstehen wollte, ohne es mit einer Menge Magie oder Dunkelheit zu verkrüppeln.
quelle
Ich habe meinen Solver in C ++ geschrieben. Ich habe eine benutzerdefinierte Baumstruktur implementiert. Ich bin nicht sicher, ob es als Versuch angesehen werden kann, aber es ist ähnlich. Jeder Knoten hat 26 Zweige, 1 für jeden Buchstaben des Alphabets. Ich durchquere die Zweige des Boggle-Boards parallel zu den Zweigen meines Wörterbuchs. Wenn der Zweig nicht im Wörterbuch vorhanden ist, stoppe ich die Suche auf dem Boggle-Board. Ich konvertiere alle Buchstaben auf der Tafel in Ints. Also 'A' = 0. Da es sich nur um Arrays handelt, ist die Suche immer O (1). Jeder Knoten speichert, ob er ein Wort vervollständigt und wie viele Wörter in seinen untergeordneten Knoten vorhanden sind. Der Baum wird beschnitten, wenn Wörter gefunden werden, um die wiederholte Suche nach denselben Wörtern zu reduzieren. Ich glaube, das Beschneiden ist auch O (1).
CPU: Pentium SU2700 1,3 GHz
RAM: 3 GB
Lädt ein Wörterbuch mit 178.590 Wörtern in <1 Sekunde.
Löst 100x100 Boggle (boggle.txt) in 4 Sekunden. ~ 44.000 Wörter gefunden.
Das Lösen eines 4x4 Boggle ist zu schnell, um einen aussagekräftigen Benchmark zu liefern. :) :)
Schneller Boggle Solver GitHub Repo
quelle
Nehmen wir bei einem Boggle-Board mit N Zeilen und M Spalten Folgendes an:
Unter diesen Annahmen ist die Komplexität dieser Lösung O (N * M).
Ich denke, dass der Vergleich der Laufzeiten für dieses eine Beispielboard in vielerlei Hinsicht den Punkt verfehlt, aber der Vollständigkeit halber ist diese Lösung auf meinem modernen MacBook Pro in <0,2 Sekunden abgeschlossen.
Diese Lösung findet alle möglichen Pfade für jedes Wort im Korpus.
quelle
Diese Lösung gibt auch die Richtung für die Suche in der angegebenen Karte an
Algo:
Ausgabe:
Code:
quelle
Ich habe eine Lösung in OCaml implementiert . Es kompiliert ein Wörterbuch als Trie vor und verwendet Sequenzfrequenzen mit zwei Buchstaben, um Kanten zu entfernen, die niemals in einem Wort erscheinen könnten, um die Verarbeitung weiter zu beschleunigen.
Es löst Ihre Beispielplatine in 0,35 ms (mit einer zusätzlichen Startzeit von 6 ms, die hauptsächlich mit dem Laden des Versuchs in den Speicher zusammenhängt).
Die gefundenen Lösungen:
quelle
/usr/share/dict
Wörterbuch und einige der Wörter fehlen tatsächlich (z. B. EMBOLE).Eine Node.JS-JavaScript-Lösung. Berechnet alle 100 eindeutigen Wörter in weniger als einer Sekunde, einschließlich des Lesens der Wörterbuchdatei (MBA 2012).
Ausgabe:
["FAM", "TUX", "TUB", "FAE", "ELI", "ELM", "ELB", "TWA", "TWA", "SAW", "AMI", "SWA" , "SWA", "AME", "SEA", "SEW", "AES", "AWL", "AWE", "SEA", "AWA", "MIX", "MIL", "AST", " ASE "," MAX "," MAE "," MAW "," MEW "," AWE "," MES "," AWL "," LIE "," LIM "," AWA "," AES "," ABER " , "BLO", "WAS", "WAE", "WEA", "LEI", "LEO", "LOB", "LOX", "WEM", "OIL", "OLM", "WEA", " WAE "," WAX "," WAF ","MILO", "EAST", "WAME", "TWAS", "TWAE", "EMIL", "WEAM", "OIME", "AXIL", "WEST", "TWAE", "LIMB", "WASE" "," WAST "," BLEO "," STUB "," BOIL "," BOLE "," LIME "," SAWT "," LIMA "," MESA "," MEWL "," AXLE "," FAME ", "ASEM", "MILE", "AMIL", "SEAX", "SEAM", "SEMI", "SWAM", "AMBO", "AMLI", "AXILE", "AMBLE", "SWAMI", "AWEST" "," AWEST "," LIMAX "," LIMES "," LIMBU "," LIMBO "," EMBOX "," SEMBLE "," EMBOLE "," WAMBLE "," FAMBLE "]EAST "," WAME "," TWAS "," TWAE "," EMIL "," WEAM "," OIME "," AXIL "," WEST "," TWAE "," LIMB "," WASE "," WAST " , "BLEO", "STUB", "BOIL", "BOLE", "LIME", "SAWT", "LIMA", "MESA", "MEWL", "AXLE", "FAME", "ASEM", " MILE "," AMIL "," SEAX "," SEAM "," SEMI "," SWAM "," AMBO "," AMLI "," AXILE "," AMBLE "," SWAMI "," AWEST "," AWEST " , "LIMAX", "LIMES", "LIMBU", "LIMBO", "EMBOX", "SEMBLE", "EMBOLE", "WAMBLE", "FAMBLE"]EAST "," WAME "," TWAS "," TWAE "," EMIL "," WEAM "," OIME "," AXIL "," WEST "," TWAE "," LIMB "," WASE "," WAST " , "BLEO", "STUB", "BOIL", "BOLE", "LIME", "SAWT", "LIMA", "MESA", "MEWL", "AXLE", "FAME", "ASEM", " MILE "," AMIL "," SEAX "," SEAM "," SEMI "," SWAM "," AMBO "," AMLI "," AXILE "," AMBLE "," SWAMI "," AWEST "," AWEST " , "LIMAX", "LIMES", "LIMBU", "LIMBO", "EMBOX", "SEMBLE", "EMBOLE", "WAMBLE", "FAMBLE"]"TWAE", "EMIL", "WEAM", "OIME", "AXIL", "WEST", "TWAE", "LIMB", "WASE", "WAST", "BLEO", "STUB", "BOIL" "," BOLE "," LIME "," SAWT "," LIMA "," MESA "," MEWL "," AXLE "," FAME "," ASEM "," MILE "," AMIL "," SEAX ", "SEAM", "SEMI", "SWAM", "AMBO", "AMLI", "AXILE", "AMBLE", "SWAMI", "AWEST", "AWEST", "LIMAX", "LIMES", "LIMBU" "," LIMBO "," EMBOX "," SEMBLE "," EMBOLE "," WAMBLE "," FAMBLE "]"TWAE", "EMIL", "WEAM", "OIME", "AXIL", "WEST", "TWAE", "LIMB", "WASE", "WAST", "BLEO", "STUB", "BOIL" "," BOLE "," LIME "," SAWT "," LIMA "," MESA "," MEWL "," AXLE "," FAME "," ASEM "," MILE "," AMIL "," SEAX ", "SEAM", "SEMI", "SWAM", "AMBO", "AMLI", "AXILE", "AMBLE", "SWAMI", "AWEST", "AWEST", "LIMAX", "LIMES", "LIMBU" "," LIMBO "," EMBOX "," SEMBLE "," EMBOLE "," WAMBLE "," FAMBLE "]"WEST", "TWAE", "LIMB", "WASE", "WAST", "BLEO", "STUB", "BOIL", "BOLE", "LIME", "SAWT", "LIMA", "MESA" "," MEWL "," AXLE "," FAME "," ASEM "," MILE "," AMIL "," SEAX "," SEAM "," SEMI "," SWAM "," AMBO "," AMLI ", "AXILE", "AMBLE", "SWAMI", "AWEST", "AWEST", "LIMAX", "LIMES", "LIMBU", "LIMBO", "EMBOX", "SEMBLE", "EMBOLE", "WAMBLE" "," FAMBLE "]"WEST", "TWAE", "LIMB", "WASE", "WAST", "BLEO", "STUB", "BOIL", "BOLE", "LIME", "SAWT", "LIMA", "MESA" "," MEWL "," AXLE "," FAME "," ASEM "," MILE "," AMIL "," SEAX "," SEAM "," SEMI "," SWAM "," AMBO "," AMLI ", "AXILE", "AMBLE", "SWAMI", "AWEST", "AWEST", "LIMAX", "LIMES", "LIMBU", "LIMBO", "EMBOX", "SEMBLE", "EMBOLE", "WAMBLE" "," FAMBLE "]SAWT "," LIMA "," MESA "," MEWL "," AXLE "," FAME "," ASEM "," MILE "," AMIL "," SEAX "," SEAM "," SEMI "," SWAM " , "AMBO", "AMLI", "AXILE", "AMBLE", "SWAMI", "AWEST", "AWEST", "LIMAX", "LIMES", "LIMBU", "LIMBO", "EMBOX", " SEMBLE "," EMBOLE "," WAMBLE "," FAMBLE "]SAWT "," LIMA "," MESA "," MEWL "," AXLE "," FAME "," ASEM "," MILE "," AMIL "," SEAX "," SEAM "," SEMI "," SWAM " , "AMBO", "AMLI", "AXILE", "AMBLE", "SWAMI", "AWEST", "AWEST", "LIMAX", "LIMES", "LIMBU", "LIMBO", "EMBOX", " SEMBLE "," EMBOLE "," WAMBLE "," FAMBLE "]LIMAX "," LIMES "," LIMBU "," LIMBO "," EMBOX "," SEMBLE "," EMBOLE "," WAMBLE "," FAMBLE "]LIMAX "," LIMES "," LIMBU "," LIMBO "," EMBOX "," SEMBLE "," EMBOLE "," WAMBLE "," FAMBLE "]
Code:
quelle
Deshalb wollte ich eine weitere PHP-Methode hinzufügen, um dieses Problem zu lösen, da jeder PHP liebt. Es gibt ein bisschen Refactoring, das ich gerne machen würde, wie die Verwendung eines regulären Ausdrucks für die Wörterbuchdatei, aber im Moment lade ich nur die gesamte Wörterbuchdatei in eine Wortliste.
Ich habe dies mit einer Idee für eine verknüpfte Liste gemacht. Jeder Knoten hat einen Zeichenwert, einen Positionswert und einen nächsten Zeiger.
Der Standortwert ist, wie ich herausgefunden habe, ob zwei Knoten verbunden sind.
Wenn ich dieses Raster verwende, weiß ich, dass zwei Knoten verbunden sind, wenn der Standort des ersten Knotens dem Standort des zweiten Knotens +/- 1 für dieselbe Zeile, +/- 9, 10, 11 für die Zeile darüber und darunter entspricht.
Ich benutze Rekursion für die Hauptsuche. Es nimmt ein Wort aus der Wortliste, findet alle möglichen Startpunkte und findet dann rekursiv die nächste mögliche Verbindung, wobei zu beachten ist, dass es nicht an einen Ort gehen kann, den es bereits verwendet (weshalb ich $ notInLoc hinzufüge).
Wie auch immer, ich weiß, dass es einer Umgestaltung bedarf, und würde gerne Gedanken darüber hören, wie es sauberer gemacht werden kann, aber es liefert die richtigen Ergebnisse basierend auf der von mir verwendeten Wörterbuchdatei. Abhängig von der Anzahl der Vokale und Kombinationen auf dem Brett dauert es ungefähr 3 bis 6 Sekunden. Ich weiß, dass sich die Ergebnisse des Wörterbuchs, sobald ich preg_match habe, erheblich verringern werden.
quelle
Ich weiß, dass ich sehr spät auf der Party bin, aber ich habe als Codierungsübung einen Boggle-Solver in mehreren Programmiersprachen (C ++, Java, Go, C #, Python, Ruby, JavaScript, Julia, Lua, PHP, Perl) und implementiert Ich dachte, dass jemand daran interessiert sein könnte, also lasse ich den Link hier: https://github.com/AmokHuginnsson/boggle-solvers
quelle
Hier ist die Lösung Verwenden vordefinierter Wörter im NLTK-Toolkit NLTK hat das Paket nltk.corpus, indem wir ein Paket namens words haben, das mehr als 2Lakhs englische Wörter enthält, die Sie einfach alle in Ihrem Programm verwenden können.
Konvertieren Sie Ihre Matrix nach dem Erstellen in ein Zeichenarray und führen Sie diesen Code aus
Ausgabe:
Ich hoffe du verstehst es.
quelle
Hier ist meine Java-Implementierung: https://github.com/zouzhile/interview/blob/master/src/com/interview/algorithms/tree/BoggleSolver.java
Der Build dauerte 0 Stunden, 0 Minuten, 1 Sekunden, 532 Millisekunden. Die
Wortsuche dauerte 0 Stunden, 0 Minuten, 0 Sekunden, 92 Millisekunden
Hinweis: Ich habe das Wörterbuch und die Zeichenmatrix am Anfang dieses Threads verwendet. Der Code wurde auf meinem MacBookPro ausgeführt. Nachfolgend finden Sie einige Informationen zum Computer.
Modellname: MacBook Pro
Modellkennung: MacBookPro8,1
Prozessorname: Intel Core i5
Prozessorgeschwindigkeit: 2,3 GHz
Anzahl der Prozessoren: 1
Gesamtzahl der Kerne: 2
L2-Cache (pro Kern): 256 KB
L3-Cache: 3 MB
Speicher: 4 GB
Boot ROM-Version: MBP81.0047.B0E
SMC-Version (System): 1.68f96
quelle
Ich habe das auch mit Java gelöst. Meine Implementierung ist 269 Zeilen lang und ziemlich einfach zu bedienen. Zuerst müssen Sie eine neue Instanz der Boggler-Klasse erstellen und dann die Lösungsfunktion mit dem Raster als Parameter aufrufen. Es dauert ungefähr 100 ms, um das Wörterbuch mit 50.000 Wörtern auf meinen Computer zu laden, und es findet die Wörter in ungefähr 10 bis 20 ms. Die gefundenen Wörter werden in einer ArrayList gespeichert
foundWords
.quelle
Ich habe das in c gelöst. Die Ausführung auf meinem Computer dauert ca. 48 ms (ca. 98% der Zeit, die für das Laden des Wörterbuchs von der Festplatte und das Erstellen des Versuchs aufgewendet wurde). Das Wörterbuch ist / usr / share / dict / american-english mit 62886 Wörtern.
Quellcode
quelle
Ich habe das perfekt und sehr schnell gelöst. Ich habe es in eine Android-App gestellt. Sehen Sie sich das Video unter dem Link "Play Store" an, um es in Aktion zu sehen.
Word Cheats ist eine App, die jedes Wortspiel im Matrix-Stil "knackt". Diese App wurde entwickelt, um mir zu helfen, Word Scrambler zu betrügen. Es kann für Wortsuche, Rätsel, Wörter, Wortsucher, Wortriss, Boggle und mehr verwendet werden!
Es kann hier gesehen werden https://play.google.com/store/apps/details?id=com.harris.wordcracker
Zeigen Sie die App in Aktion im Video https://www.youtube.com/watch?v=DL2974WmNAI an
quelle