Dies ist ein Worträtsel.
Ihr Programm sollte zwei Wörter für die Standardeingabe akzeptieren.
Wort eins ist das Startwort. Wort zwei ist das Endwort.
Vom Startwort an müssen Sie das Endwort erreichen, indem Sie jeweils einen Buchstaben ändern / hinzufügen / entfernen. Nach jeder Änderung muss ein neues gültiges Wort gebildet werden. Hinzugefügte Buchstaben werden am Anfang oder Ende hinzugefügt. Sie können Buchstaben von jedem Ort entfernen (das Wort darf jedoch nicht drei Buchstaben lang sein). Hinweis: Sie können die Buchstaben nicht neu anordnen, um ein Wort zu bilden.
Die Ausgabe des Programms ist die Folge von Wörtern, die vom Startwort zum Endwort gelangen.
Beispiel:
Input:
Post Shot
Output:
Post
cost
coat
goat
got
hot
shot
Gewinner:
- Das Programm muss in einer angemessenen Zeit (weniger als 10 Sekunden) ausgeführt werden.
- Das Programm, das die kürzeste Ausgabesequenz für die Preiswörter generieren kann.
- Zink -> Silizium
- Wenn mehr als ein Programm die kürzeste Sequenz erhält, dann das kürzeste Programm in Zeichen (ohne Leerzeichen).
- Wenn wir noch mehr als ein Programm haben, wird das Datum / die Uhrzeit der Programmeinreichung verwendet.
Anmerkungen:
- Die Großschreibung ist nicht relevant.
- Der Code zum Erstellen eines Wörterbuchs wird nicht auf die Codekosten angerechnet.
- Preiswörter und -sequenzen werden generiert aus:
http://dl.packetstormsecurity.net/Crackers/wordlists/dictionaries/websters-dictionary.gz
- Preiswörter und -sequenzen werden generiert aus:
code-golf
word-puzzle
Martin York
quelle
quelle
Antworten:
Python, 288 Zeichen
(ohne die Wörterbuch-Lesezeile zu zählen)
für die Herausforderung
zink
ansilicon
:Es gibt einige seltsame Wörter in diesem Wörterbuch ...
quelle
guester overturn
(dauert einige Zeit) oderregatta gyrally
(kehrt nicht zurück) ;-)Traceroute - 10 Zeichen
Detail
Router sind mit aktiviertem OSPF vorkonfiguriert und auf diese Weise angeordnet.
Und ja, ich brauche 233614 Router, um alle Wörter vollständig zu unterstützen. :-)
quelle
zink->pink->pank->pani->panic->pinic->sinic->sinico->silico->silicon
Ich versuche es wirklich mit dem Dijkstra-Algorithmus (der in OSPF verwendet wird) und kann diesen Pfad um 1s finden poste es später in einem separaten Post, sobald ich Golf gespielt habe.PHP -
886689644612Wörterbuch wird geladen:
Aktueller Code (nur beides zusammenfassen):
Verwendungszweck:
Ergebnis:
Dies sollte für 'Zink Silicon' in weniger als 0,5 Sekunden und in den meisten Fällen in weniger als 1 Sekunde ablaufen (manchmal länger, wenn keine Lösung vorhanden ist, aber immer noch zurückkehrt).
Dies verwendet den A * -Algorithmus mit Levenshtein-Abstand , um eine Untergrenze der Abstände abzuschätzen.
Einige interessante Tests:
vas arm
->vas bas bar barm arm
(mit einem Wort, das länger als Anfang und Ende ist)oxy pom
->oxy poxy poy pom
regatta gyrally
-> (keine, aber das Skript wird korrekt beendet)aal presolution
-> +8 Zeichenlenticulated aal
-> -9 Zeichenacarology lowness
-> 46 Hopfencaniniform lowness
-> 51 Hopfencauliform lowness
-> 52 Hopfenoverfoul lowness
-> 54 Hopfendance facia
-> Einige Wörter im Pfad haben 4 Zeichen mehr als beide Start / Endequelle
PHP Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 71 bytes)
php -dmemory_limit=256M
.had->hand
ist kein gültiger Zug, Sie können nur einen Buchstaben am Anfang oder Ende hinzufügen. Gleiches gilt fürvest->verst
:-)Python
Da ich Golf-Dijkstra-Codes nicht auf einige hundert Bytes komprimieren konnte, ist hier eine ungolfed Version von mir.
Tests
Tests von user300 hinzugefügt
Etwas mehr
quelle
3 <= len(x) <= max(map(len, [nodea, nodeb]))
Ist garantiert, dass der Pfad niemals länger als Start- und Endwörter durch ein Wort führt?oxy pom
; kürzester Weg istoxy->poxy->poy->pom
. Es scheint auch, dass Sie Permutationen und Einfügungen an jedem Ort zulassen, die nicht erlaubt sind :-)