Ein Labyrinth in einem N x N-Raster aus quadratischen Zellen wird definiert, indem angegeben wird, ob jede Kante eine Wand ist oder nicht. Alle Außenkanten sind Wände. Eine Zelle ist als Start definiert , und eine Zelle ist als Ausgang definiert , und der Ausgang ist von Anfang an erreichbar. Der Start und der Ausgang sind nie die gleiche Zelle.
Beachten Sie, dass sich weder Start noch Ausgang am äußeren Rand des Labyrinths befinden müssen. Dies ist also ein gültiges Labyrinth:
Eine Reihe von 'N', 'E', 'S' und 'W' zeigt an, dass versucht wird, sich nach Norden, Osten, Süden und Westen zu bewegen. Ein Zug, der von einer Mauer blockiert wird, wird ohne Bewegung übersprungen. Eine Zeichenfolge verlässt ein Labyrinth, wenn das Anwenden dieser Zeichenfolge von Anfang an dazu führt, dass der Ausgang erreicht wird (unabhängig davon, ob die Zeichenfolge nach Erreichen des Ausgangs fortgesetzt wird).
Inspiriert von diesem Rätsel. SEINE Frage, für die xnor eine nachweisbare Methode zum Lösen mit einer sehr langen Zeichenfolge bereitstellte , schreibt Code, der eine einzelne Zeichenfolge findet, die aus einem beliebigen 3 x 3-Labyrinth herauskommt.
Mit Ausnahme ungültiger Labyrinthe (Start und Ende in derselben Zelle oder Ausgang von Anfang an nicht erreichbar) gibt es 138.172 gültige Labyrinthe, und die Zeichenfolge muss jeden von ihnen beenden.
Gültigkeit
Die Zeichenfolge muss Folgendes erfüllen:
- Es besteht nur aus den Zeichen 'N', 'E', 'S' und 'W'.
- Es verlässt jedes Labyrinth, auf das es angewendet wird, wenn es beim Start gestartet wird.
Da die Menge aller möglichen Labyrinthe jedes mögliche Labyrinth mit jedem möglichen gültigen Startpunkt enthält, bedeutet dies automatisch, dass die Zeichenfolge jedes Labyrinth von jedem gültigen Startpunkt verlässt . Das heißt, von jedem Ausgangspunkt aus, von dem aus der Ausgang erreichbar ist.
Gewinnen
Der Gewinner ist die Antwort, die die kürzeste gültige Zeichenfolge bereitstellt und den Code enthält, mit dem sie erstellt wurde. Wenn mehr als eine der Antworten eine Zeichenfolge mit dieser kürzesten Länge bereitstellt, gewinnt die erste, die diese Zeichenfolge veröffentlicht.
Beispiel
Hier ist eine 500 Zeichen lange Beispielzeichenfolge, um Ihnen etwas zu bieten, das Sie schlagen können:
SEENSSNESSWNNSNNNNWWNWENENNWEENSESSNENSESWENWWWWWENWNWWSESNSWENNWNWENWSSSNNNNNNESWNEWWWWWNNNSWESSEEWNENWENEENNEEESEENSSEENNWWWNWSWNSSENNNWESSESNWESWEENNWSNWWEEWWESNWEEEWWSSSESEEWWNSSEEEEESSENWWNNSWNENSESSNEESENEWSSNWNSEWEEEWEESWSNNNEWNNWNWSSWEESSSSNESESNENNWEESNWEWSWNSNWNNWENSNSWEWSWWNNWNSENESSNENEWNSSWNNEWSESWENEEENSWWSNNNNSSNENEWSNEEWNWENEEWEESEWEEWSSESSSWNWNNSWNWENWNENWNSWESNWSNSSENENNNWSSENSSSWWNENWWWEWSEWSNSSWNNSEWEWENSWENWSENEENSWEWSEWWSESSWWWNWSSEWSNWSNNWESNSNENNSNEWSNNESNNENWNWNNNEWWEWEE
Vielen Dank an orlp für die Spende.
Bestenliste
Gleiche Punktzahlen werden in der Reihenfolge der Veröffentlichung dieser Punktzahl aufgelistet. Dies ist nicht unbedingt die Reihenfolge, in der die Antworten veröffentlicht wurden, da die Punktzahl für eine bestimmte Antwort im Laufe der Zeit aktualisiert werden kann.
Richter
Hier ist ein Python 3-Validator , der eine Zeichenfolge von NESW als Befehlszeilenargument oder über STDIN verwendet.
Bei einer ungültigen Zeichenfolge erhalten Sie ein visuelles Beispiel für ein Labyrinth, für das ein Fehler aufgetreten ist.
quelle
Antworten:
C ++,
979593918683828179 ZeichenMeine Strategie ist ziemlich einfach - ein Evolutionsalgorithmus, der gültige Sequenzen vergrößern, verkleinern, Elemente austauschen und mutieren kann. Meine Evolutionslogik ist jetzt fast dieselbe wie die von @ Sp3000, da er eine Verbesserung gegenüber meiner war.
Meine Implementierung der Labyrinthlogik ist jedoch ziemlich geschickt. Auf diese Weise kann ich mit rasender Geschwindigkeit prüfen, ob die Zeichenfolgen gültig sind. Versuchen Sie es anhand des Kommentars
do_move
und desMaze
Konstruktors herauszufinden .quelle
do_move
ist jetzt wahnsinnig schnell.Python 3 + PyPy,
8280 ZeichenIch habe gezögert, diese Antwort zu posten, weil ich im Grunde genommen den Ansatz von orlp gewählt und meine eigene Richtung eingeschlagen habe. Diese Saite wurde ausgehend von einer Lösung mit einer Pseudozufallslänge von 500 gefunden - es wurden eine ganze Reihe von Samen ausprobiert, bevor ich den aktuellen Rekord brechen konnte.
Die einzige große Neuerung ist, dass ich nur ein Drittel der Labyrinthe ansehe. Zwei Kategorien von Labyrinthen sind von der Suche ausgeschlossen:
<= 7
Plätze erreichbar sindDie Idee ist, dass jede Zeichenfolge, die den Rest der Irrgärten löst, auch das oben Genannte automatisch lösen sollte. Ich bin davon überzeugt, dass dies für den zweiten Typ zutrifft, für den ersten jedoch definitiv nicht. Daher enthält die Ausgabe einige False Positives, die separat überprüft werden müssen. Diese falschen Positiven lassen normalerweise nur etwa 20 Irrgärten aus, daher dachte ich, es wäre ein guter Kompromiss zwischen Geschwindigkeit und Genauigkeit, und es würde den Saiten auch ein wenig mehr Luft zum Mutieren geben.
Anfangs habe ich eine lange Liste von Suchheuristiken durchgesehen, aber schrecklicherweise hat keine von ihnen etwas Besseres als 140 oder so gefunden.
quelle
0
zun
auf dem Weg und nehmen wir an, dass die StringS
Sie bekommt von0
zun
. DannS
kommst du auch von irgendeiner Zwischenzellec
zun
. Angenommen, anders. Seia(i)
die Position nachi
Schritten beginnend bei0
undb(i)
beginnend beic
. Danna(0) = 0 < b(0)
ändert sich jeder Schritta
undb
um höchstens 1 unda(|S|) = n > b(|S|)
. Nimm das Kleinstet
so, dassa(t) >= b(t)
. Natürlicha(t) != b(t)
oder sie wären synchron, also müssen sie schrittweise die Plätze tauschen,t
indem sie sich in die gleiche Richtung bewegen.C ++ und die Bibliothek von Lingeling
Mit einem SAT- basierten Ansatz konnte ich das ähnliche Problem für 4x4-Labyrinthe mit blockierten Zellen anstelle von dünnen Wänden und festen Start- und Ausgangspositionen an gegenüberliegenden Ecken vollständig lösen . Also hoffte ich, die gleichen Ideen für dieses Problem verwenden zu können. Obwohl ich für das andere Problem nur 2423 Labyrinthe verwendet habe (in der Zwischenzeit wurde beobachtet, dass 2083 genug sind) und eine Lösung der Länge 29 hat, hat die SAT-Codierung Millionen von Variablen verwendet und das Lösen hat Tage gedauert.
Deshalb habe ich beschlossen, den Ansatz auf zwei wichtige Arten zu ändern:
Ich habe auch einige Optimierungen vorgenommen, um weniger Variablen und Unit-Klauseln zu verwenden.
Das Programm basiert auf @ orlp's. Eine wichtige Änderung war die Auswahl der Labyrinthe:
is_solution
prüft, ob alle erreichbaren Positionen erreicht sind.Auf diese Weise erhalte ich insgesamt 10772 Labyrinthe mit Startpositionen.
Hier ist das Programm:
Zuerst
configure.sh
undmake
derlingeling
Löser, dann kompilieren Sie das Programm mit so etwas wieg++ -std=c++11 -O3 -I ... -o m3sat m3sat.cc -L ... -llgl
, wo...
ist der Pfad, wolglib.h
bzw.liblgl.a
sind, so könnten zum Beispiel beide sein../lingeling-<version>
. Oder legen Sie sie einfach in dasselbe Verzeichnis und verzichten Sie auf die Optionen-I
und-L
.Das Programm nimmt ein obligatorisches Befehlszeilenargument, eine Zeichenfolge , bestehend aus
N
,E
,S
,W
(für feste Richtungen) oder*
. Sie können also nach einer allgemeinen Lösung der Größe 78 suchen, indem Sie eine Zeichenfolge von 78*
s (in Anführungszeichen) eingeben, oder nach einer Lösung suchen, die mitNEWS
der Verwendung vonNEWS
gefolgt von beliebig vielen*
s für zusätzliche Schritte beginnt . Nehmen Sie als ersten Test Ihre Lieblingslösung und ersetzen Sie einige Buchstaben durch*
. Dies findet schnell eine Lösung für einen überraschend hohen Wert von "some".Das Programm erkennt das hinzugefügte Labyrinth anhand der Wandstruktur und der Startposition und gibt die Anzahl der erreichbaren Positionen und Wände an. Die Labyrinthe werden nach diesen Kriterien sortiert und die erste ungelöste wird hinzugefügt. Daher haben die meisten Labyrinthe hinzugefügt
(9/4)
, aber manchmal erscheinen auch andere.Ich nahm die bekannte Lösung der Länge 79 und versuchte, sie für jede Gruppe von 26 benachbarten Buchstaben durch 25 beliebige Buchstaben zu ersetzen. Ich habe auch versucht, 13 Buchstaben am Anfang und am Ende zu entfernen und sie durch 13 am Anfang und 12 am Ende zu ersetzen und umgekehrt. Leider ist alles unbefriedigend ausgefallen. Können wir dies als Indikator dafür nehmen, dass die Länge 79 optimal ist? Nein, ich habe in ähnlicher Weise versucht, die Lösung für Länge 80 auf Länge 79 zu verbessern, und das war auch nicht erfolgreich.
Schließlich habe ich versucht, den Anfang einer Lösung mit dem Ende der anderen zu kombinieren und auch mit einer Lösung, die durch eine der Symmetrien transformiert wurde. Jetzt gehen mir die interessanten Ideen aus und ich habe beschlossen, Ihnen zu zeigen, was ich habe, obwohl es nicht zu neuen Lösungen geführt hat.
quelle