Dies wurde als Teil des First Periodic Premier Programming Puzzle Push geschrieben .
Das Spiel
Es werden ein Start- und ein Endwort gleicher Länge bereitgestellt. Das Ziel des Spiels ist es, einen Buchstaben im Startwort zu ändern, um ein anderes gültiges Wort zu bilden. Wiederholen Sie diesen Schritt, bis das Endwort erreicht ist, und verwenden Sie dabei die geringste Anzahl von Schritten. Bei den Wörtern TREE und FLED wäre die Ausgabe beispielsweise:
TREE
FREE
FLEE
FLED
2
Spezifikationen
- Die Wikipedia-Artikel für die OWL oder SOWPODS könnten ein nützlicher Ausgangspunkt sein, was Wortlisten betrifft .
- Das Programm sollte zwei Arten der Auswahl der Start- und Endwörter unterstützen:
- Wird vom Benutzer über die Befehlszeile, stdin oder eine andere für die Sprache Ihrer Wahl geeignete Sprache angegeben (geben Sie nur an, was Sie tun).
- Auswahl von 2 zufälligen Wörtern aus der Datei.
- Die Start- und Endwörter sowie alle Zwischenwörter sollten gleich lang sein.
- Jeder Schritt sollte in seiner Zeile ausgedruckt werden.
- Die letzte Zeile Ihrer Ausgabe sollte die Anzahl der Zwischenschritte sein, die zwischen dem Anfangs- und dem Endwort erforderlich waren.
- Wenn zwischen dem Anfangs- und dem Endwort keine Übereinstimmung gefunden werden kann, sollte die Ausgabe aus drei Zeilen bestehen: dem Anfangswort, dem Endwort und dem Wort OY.
- Nehmen Sie die Big O-Notation für Ihre Lösung in Ihre Antwort auf
- Bitte geben Sie 10 eindeutige Start- und Endwortpaare an (natürlich mit ihrer Ausgabe), um die Schritte anzuzeigen, die Ihr Programm erzeugt. (Um Platz zu sparen, kann Ihr Programm diese in einzelnen Zeilen ausgeben, Sie können diese jedoch zu einer einzelnen Zeile zusammenfassen, um sie zu veröffentlichen. Dabei werden neue Zeilen durch Leerzeichen und ein Komma zwischen den einzelnen Zeilen ersetzt.
Ziele / Gewinnkriterien
- Die schnellste / beste Big O-Lösung mit den kürzesten Zwischenschritten nach einer Woche gewinnt.
- Wenn sich aus den Big O-Kriterien ein Gleichstand ergibt, gewinnt der kürzeste Code.
- Wenn es immer noch ein Unentschieden gibt, gewinnt die erste Lösung, die ihre schnellste und kürzeste Revision erreicht.
Tests / Beispielausgabe
DIVE
DIME
DAME
NAME
2
PEACE
PLACE
PLATE
SLATE
2
HOUSE
HORSE
GORSE
GORGE
2
POLE
POSE
POST
PAST
FAST
3
Validierung
Ich arbeite an einem Skript, mit dem die Ausgabe überprüft werden kann.
Es wird:
- Stellen Sie sicher, dass jedes Wort gültig ist.
- Stellen Sie sicher, dass sich jedes Wort genau um einen Buchstaben vom vorherigen Wort unterscheidet.
Es wird nicht:
- Überprüfen Sie, ob die kürzeste Anzahl von Schritten verwendet wurde.
Sobald ich das geschrieben habe, werde ich diesen Beitrag natürlich aktualisieren. (:
code-challenge
word-puzzle
1p5
Rebecca Chernoff
quelle
quelle
HOUSE
zuGORGE
kommt, als 2 gemeldet wird. Mir ist klar, dass es 2 Zwischenwörter gibt, daher macht es Sinn, aber die Anzahl der Operationen wäre intuitiver.The fastest/best Big O solution producing the shortest interim steps after one week will win.
Da Sie nicht garantieren können, dass die schnellste Lösung inzwischen diejenige ist, die die wenigsten Schritte verwendet, sollten Sie eine Präferenz angeben, wenn eine Lösung weniger Schritte verwendet, das Ziel jedoch später erreicht.BAT
undCAT
habe keine Schritte, richtig?Antworten:
Da die Länge als Kriterium aufgeführt ist, ist hier die Golfversion mit 1681 Zeichen (könnte wahrscheinlich noch um 10% verbessert werden):
Die ungolfed-Version, die Paketnamen und -methoden verwendet und keine Warnungen ausgibt oder Klassen erweitert, nur um sie zu aliasen, lautet:
Wie Sie sehen können, ist die Analyse der laufenden Kosten
O(filelength + num_words * hash + V * n * (n + hash) + E * hash)
. Wenn Sie meine Annahme akzeptieren, dass das Einfügen / Nachschlagen einer Hash-Tabelle eine konstante Zeit ist, dann ist das soO(filelength + V n^2 + E)
. Die besonderen Statistiken der Graphen in SOWPODS bedeuten, dassO(V n^2)
sieO(E)
für die meisten wirklich dominierenn
.Beispielausgaben:
IDOLA, IDOLS, IDYLS, ODYLS, ODALS, OVALS, OVELS, OVENS, EVENS, ETENS, STENS, SKENS, SKINS, SPINS, SPINE, 13
WICCA, PROSY, OY
BRINY, BRINS, TRINS, TAINS, TARNS, YARNS, YAWNS, YAWPS, YAPPS, 7
GALES, GASES, GASTS, GESTS, GESTE, GESSE, DESSE, 5
SURES, DURES, DUNEN, DINES, DINGS, DINGY, 4
LICHT, LICHT, BICHT, BIGOT, BIGOS, BIROS, GIROS, MÄDCHEN, GURNS, GUANS, GUANA, RUANA, 10
SARGE, SERGE, SERRE, SERRS, SEER, DEERS, DYERS, OYERS, OVERS, OVELS, OVALS, ODALS, ODYLS, IDYLS, 12
KEIRS, SEIRS, SEHER, BIER, BRER, BRERE, BREME, CREME, CREPE, 7
Dies ist eines der 6 Paare mit dem längsten kürzesten Weg:
GAINEST, FAINEST, FAIREST, SAIREST, SAIDEST, SADDEST, MADDEST, MIDDEST, MILDEST, WILDEST, WILIEST, WALIEST, WANIEST, CANIEST, CANTEST, WETTBEWERB, CONFEST, CONFESS, CONFERS, COOPERS, COOPERS, COP, POPPITS, POPPIES, POPSIES, MOPSIES, MOUSIES, MOUSSES, POUSSES, PLUSSES, PLISSES, PRISSES, PRESSES, PREASES, UREASES, UNEASES, UNCASES, UNCASED, UNBASED, UNVERMITTELT, UNVERMITTELT, VERMITTELT, ENDET INDEXES, INDENES, INDENTS, INCENTS, INCESTS, INFESTS, INFECTS, INJECTS, 56
Und eines der schlimmsten löslichen 8-Buchstaben-Paare:
Anstechen, Ausstechen, Ausstechen, Ausstechen, Ausstechen, Ausstechen, Ausstechen, Ausstechen, Ausstechen, Ausstechen, Ausstechen, Ausstechen, Aufspielen, Ausstechen, Stapfen, Stolpern, Stolpern CRIMPING, CRISPING, CRISPINS, CRISPENS, CRISPERS, CRIMPERS, CRAMPERS, CLAMPERS, CLASPERS, CLASHERS, SLASHERS, SLATHERS, SLITHERS, SMITHERS, SMOTHERS, SOOTHERS, SOUTHERS, POCHERS, MOUTHERS, MOUCHERS LUNCHERS, LYNCHERS, LYNCHETS, LINCHETS, 52
Jetzt, wo ich denke, dass ich alle Anforderungen der Frage aus dem Weg habe, meine Diskussion.
Für einen CompSci reduziert sich die Frage offensichtlich auf den kürzesten Weg in einem Graphen G, dessen Eckpunkte Wörter sind und dessen Kanten Wörter verbinden, die sich in einem Buchstaben unterscheiden. Das effiziente Generieren des Diagramms ist nicht trivial - ich habe tatsächlich eine Idee, die ich überdenken muss, um die Komplexität auf O (V n -Hash + E) zu reduzieren. Die Art und Weise, wie ich das mache, besteht darin, ein Diagramm zu erstellen, das zusätzliche Eckpunkte (die Wörtern mit einem Platzhalterzeichen entsprechen) einfügt und homöomorph zu dem fraglichen Diagramm ist. Ich habe darüber nachgedacht, diesen Graphen zu verwenden, anstatt ihn auf G zu reduzieren - und ich nehme an, dass ich dies aus Golfsicht hätte tun sollen - auf der Grundlage, dass ein Platzhalterknoten mit mehr als 3 Kanten die Anzahl der Kanten im Graphen reduziert und Die Standardlaufzeit im ungünstigsten Fall für Algorithmen mit kürzestem Pfad beträgt
O(V heap-op + E)
.Als erstes habe ich jedoch einige Analysen der Grafiken G für verschiedene Wortlängen durchgeführt und festgestellt, dass sie für Wörter mit 5 oder mehr Buchstaben äußerst spärlich sind. Das 5-Buchstaben-Diagramm hat 12478 Eckpunkte und 40759 Kanten. Das Hinzufügen von Verbindungsknoten verschlechtert das Diagramm. Wenn Sie bis zu 8 Buchstaben haben, gibt es weniger Kanten als Knoten, und 3/7 der Wörter sind "fern". Daher habe ich diese Optimierungsidee als nicht wirklich hilfreich abgelehnt.
Die Idee, die sich als hilfreich erwies, bestand darin, den Haufen zu untersuchen. Ich kann ehrlich sagen, dass ich in der Vergangenheit einige mäßig exotische Haufen implementiert habe, aber keine so exotische wie diese. Ich verwende A-Stern (da C keinen Vorteil bietet, wenn ich den Haufen verwende) mit der offensichtlichen Heuristik der Anzahl der Buchstaben, die sich vom Ziel unterscheiden, und eine kleine Analyse zeigt, dass es zu keinem Zeitpunkt mehr als 3 verschiedene Prioritäten gibt auf dem Haufen. Wenn ich einen Knoten mit der Priorität (Kosten + Heuristik) platziere und seine Nachbarn betrachte, gibt es drei Fälle, die ich in Betracht ziehe: 1) Die Kosten des Nachbarn sind Kosten + 1; Die Heuristik des Nachbarn ist heuristisch-1 (weil der geänderte Buchstabe "korrekt" wird). 2) Kosten + 1 und Heuristik + 0 (weil der geänderte Buchstabe von "falsch" in "immer noch falsch" wechselt; 3) Kosten + 1 und Heuristik + 1 (da der geänderte Buchstabe von "richtig" in "falsch" wechselt). Wenn ich also den Nachbarn entspanne, füge ich ihn mit derselben Priorität, Priorität + 1 oder Priorität + 2 ein. Als Ergebnis kann ich ein 3-Element-Array von verknüpften Listen für den Heap verwenden.
Ich sollte eine Anmerkung zu meiner Annahme hinzufügen, dass Hash-Lookups konstant sind. Sehr gut, können Sie sagen, aber was ist mit Hash-Berechnungen? Die Antwort ist, dass ich sie abschreibe:
java.lang.String
ZwischenspeichernhashCode()
, so dass die Gesamtzeit, die für das Berechnen von Hashes aufgewendet wirdO(V n^2)
(für das Generieren des Diagramms).Es gibt eine weitere Änderung, die sich auf die Komplexität auswirkt. Die Frage, ob es sich um eine Optimierung handelt oder nicht, hängt jedoch von Ihren statistischen Annahmen ab. (IMO "die beste Big O-Lösung" als Kriterium zu setzen, ist ein Fehler, weil es aus einem einfachen Grund keine beste Komplexität gibt: Es gibt keine einzige Variable). Diese Änderung wirkt sich auf den Schritt der Diagrammerstellung aus. Im obigen Code ist es:
Das ist
O(V * n * (n + hash) + E * hash)
. DerO(V * n^2)
Teil besteht jedoch darin, für jede Verknüpfung eine neue Zeichenfolge mit n Zeichen zu generieren und dann ihren Hashcode zu berechnen. Dies kann mit einer Helferklasse vermieden werden:Dann wird die erste Hälfte der Graphgenerierung
Mithilfe der Struktur des Hashcodes können wir die Links in generieren
O(V * n)
. Dies wirkt sich jedoch nachteilig aus. In meiner Annahme, dass Hash-Lookups eine konstante Zeit sind, liegt die Annahme, dass der Vergleich von Objekten auf Gleichheit billig ist. Der Gleichstellungstest von Link ist jedochO(n)
im schlimmsten Fall. Der schlimmste Fall ist, wenn eine Hash-Kollision zwischen zwei gleichen Links vorliegt, die aus verschiedenen WörternO(E)
generiert wurden. Davon abgesehen sind wir gut, außer im unwahrscheinlichen Fall einer Hash-Kollision zwischen ungleichen Links. Deshalb haben wir gehandeltO(V * n^2)
fürO(E * n * hash)
. Siehe meinen vorherigen Punkt zur Statistik.quelle
Java
Komplexität : ?? (Ich habe keinen CompSci-Abschluss, daher würde ich mich über Hilfe in dieser Angelegenheit freuen.)
Eingabe : Geben Sie ein Wortpaar (mehr als 1 Paar, wenn Sie dies wünschen) in die Befehlszeile ein. Wenn keine Befehlszeile angegeben ist, werden 2 verschiedene zufällige Wörter ausgewählt.
quelle
System.nanoTime()
.c unter Unix
Verwendung des Dijkstra-Algorithmus.
Ein großer Teil des Codes ist eine Kostüm-N-Ary-Tree-Implementierung, die zum Halten dient
Wer daran interessiert, wie es funktioniert , sollten Sie vielleicht gelesen
findPath
,process
undprocessOne
(und ihre zugehörigen Kommentare). Und vielleichtbuildPath
undbuildPartialPath
. Der Rest ist Buchhaltung und Gerüste. Einige Routinen, die beim Testen und Entwickeln verwendet wurden, jedoch nicht in der "Produktions" -Version, wurden beibehalten.Ich verwende
/usr/share/dict/words
auf meinem Mac OS 10.5 - Box, die so viele lange, esoterische Einträge hat , dass lässt sie völlig zufällig laufen eine erzeugt viel vonOY
s.Einige Ausgaben:
Die Komplexitätsanalyse ist nicht trivial. Die Suche ist eine zweiseitige, iterative Vertiefung.
W
.S_min = (<number of different letter>-1)
weil wir, wenn wir nur einen Buchstaben voneinander entfernt sind, die Änderung bei 0 Zwischenschritten bewerten. Das Maximum ist schwer zu quantifizieren, siehe den obigen TRICKY-SWOOSH-Lauf. Jede Hälfte des Baumes wirdS/2-1
zuS/2
B
.Die Mindestanzahl an Operationen ist also
2 * (S/2)^B * W
nicht wirklich gut.quelle
O(|V|+|E|)
anstattO(|E|+|V| log |V|)
?