Ihre Aufgabe ist es, die Rollen beider Charaktere in dieser Szene aus Inception zu spielen. Darin fordert Cobb Ariadne heraus:
Sie haben zwei Minuten Zeit, um ein Labyrinth zu entwerfen, dessen Lösung eine Minute dauert.
Einige Freiheiten werden bei dieser Beschreibung übernommen. Am wichtigsten ist jedoch, dass diese Herausforderung nicht auf der Zeit basiert, sondern auf der Effektivität Ihrer Labyrinthe und Labyrinthlöser.
Ich entschuldige mich für die vielen Änderungen an dieser Herausforderung, während wir uns für ein einfaches und faires Format einsetzen.
Teil I: Labyrinthformat
Alle Irrgärten sind quadratisch. Eine Zelle im Labyrinth wird als ein Tupel mit Nullindex dargestellt row column
.
Wände werden durch zwei binäre Zeichenfolgen dargestellt: eine für horizontale Wände (die die Bewegung zwischen Zeilen blockieren) und eine für vertikale Wände (umgekehrt). In einem NxN
Labyrinth gibt es Nx(N-1)
mögliche Wände jedes Typs. Nehmen wir ein 3x3-Beispiel, in dem die Zellen beschriftet sind:
A B | C
---
D | E F
---
G H | I
alle möglichen vertikalen Wände sind: AB BC DE EF GH HI
. Übersetzt in eine Schnur sind die gezeigten Wände 011001
für vertikale Wände und 010010
für horizontale Wände. Mit "Binärzeichenfolge" meine ich auch "die Zeichen" 0 "und" 1 "".
Das vollständige Labyrinthformat ist eine Zeichenfolge, die in dieser Reihenfolge Folgendes enthält:
- Breite
- Starte das Zellentupel
- end cell tuple
- horizontale Wände
- vertikale Wände
Zum Beispiel dieses Labyrinth:
0 1 2 3 4
_________
0 | | E| _|
1 | _|_|_ |
2 |_ _ _ | |
3 | _ _ | |
4 |____S|___|
start:(4,2)
end:(0,2)
ist wie folgt formatiert:
5
4 2
0 2
00001011101110001100
10100110000100010010
Teil II: Der Architekt
Das Architect-Programm erstellt das Labyrinth. Es muss sich an die Regeln halten und ein gültiges Labyrinth bereitstellen (eines, bei dem eine Lösung existiert und das Ende nicht über dem Anfang liegt).
Eingabe: Zwei positive ganze Zahlen:
size [random seed]
Wo size
wird in sein [15, 50]
. Es wird empfohlen, den Zufallsstartwert zu verwenden, damit Übereinstimmungen wiederholt werden können, obwohl dies nicht erforderlich ist.
Ausgabe: Ein gültiges Labyrinth der Größe x Größe (Quadrat) mit dem in Teil I beschriebenen Format. "Gültig" bedeutet, dass eine Lösung vorhanden ist und die Startzelle nicht mit der Endzelle übereinstimmt.
Die Punktzahl eines Architekten für ein bestimmtes Labyrinth ist
# steps taken to solve
–––––––––––––––––––––––––––––
max(dist(start,end),(# walls))
So werden Architekten für komplexe Irrgärten belohnt, aber für jede errichtete Mauer bestraft (dies ist ein Ersatz für die zeitliche Beschränkung von Ariadne). Die dist()
Funktion stellt sicher, dass ein Labyrinth ohne Wände keine unendliche Punktzahl erhält. Die Außenränder des Labyrinths tragen nicht zur Anzahl der Wände bei.
Teil III: Der Löser
The Solver versucht Labyrinthe zu lösen, die von den Architekten anderer erstellt wurden. Es gibt eine Art Nebel des Krieges: Es werden nur Wände eingeschlossen, die an besuchte Zellen angrenzen (alle anderen werden durch '?' Ersetzt).
Eingabe: das gleiche Labyrinthformat, aber mit '?' Wobei Wände unbekannt sind, eine zusätzliche Zeile für den aktuellen Standort und eine durch Kommas getrennte Liste der gültigen Auswahlmöglichkeiten für diesen Standort. (Dies ist eine umfangreiche Bearbeitung, die das Schreiben einer Labyrinth-Parsing-Funktion vereinfachen soll.)
Beispiel (wie das obige 5x5-Labyrinth nach einem Schritt nach links)
5
4 2
0 2
???????????????011??
????????????????001?
4 1
4 0,4 2
Was so etwas entspricht, wo ?
ist Nebel:
0 1 2 3 4
_________
0 |????E????|
1 |?????????|
2 |?????????|
3 | ?_?_????|
4 |__C_S|_?_|
output: Eines der Tupel aus der Liste der gültigen Auswahlmöglichkeiten
Die Punktzahl jedes Solvers ist die Umkehrung der Punktzahl des Architekten.
Teil IV: König des Hügels
Architekten und Solver erhalten separate Bewertungen, sodass es möglicherweise zwei Gewinner gibt.
Jedes Paar von Architekten und Solvern hat viele Chancen, sich gegenseitig zu überlisten. Die Punktzahl wird über alle Tests und Gegner gemittelt. Im Gegensatz zu Code-Golf-Konventionen gewinnt die höchste Durchschnittspunktzahl!
Ich beabsichtige dies fortzusetzen, aber ich kann nicht garantieren, dass die Tests für immer fortgesetzt werden! Angenommen, in einer Woche wird ein Gewinner ermittelt.
Teil V: Einreichen
- Ich behalte mein Vetorecht bei allen Einsendungen bei - Klugheit wird gefördert, aber nicht, wenn sie die Konkurrenz oder meinen Computer bricht! (Wenn ich nicht sagen kann, was Ihr Code tut, werde ich wahrscheinlich ein Veto einlegen)
- Überlegen Sie sich einen Namen für Ihr Architect / Solver-Paar. Veröffentlichen Sie Ihren Code zusammen mit Anweisungen zur Ausführung.
In Kürze: ein aktualisiertes Python-Testkit für das neue Format. Es gab große Änderungen, die das Einreichen von Sprachen erlaubten.
quelle
Antworten:
BuildFun und SolveFun
Nun, das hat eine Weile gedauert und ich bin mir nicht ganz sicher, ob der Solver schummelt oder nicht. Während es die ganze Zeit über Zugriff auf das gesamte Labyrinth hat, betrachtet es nur die Zelle, in der es sich befindet, die Wände, die es umgeben, und, wenn es keine Wand zwischen ihnen gibt, die angrenzenden Zellen. Wenn dies gegen die Regeln verstößt, lass es mich bitte wissen und ich werde versuchen, es zu ändern.
Wie auch immer, hier ist der Code:
Mir ist klar, dass dies lächerlich lang und nicht besonders einfach zu lesen ist, aber ich bin faul, also bleibt es so.
BuildFun
Der Architekt BuildFun ist ein relativ einfaches Programm zur Erzeugung von Labyrinthen, das immer ein 'perfektes' Labyrinth erzeugt (eines ohne Schleifen und bei dem zwei beliebige Punkte immer genau einen Pfad zwischen sich haben). Es basiert seine Logik auf der Sameneingabe, was bedeutet, dass die generierten Labyrinthe pseudozufällig sind und häufig sich wiederholende Muster aufweisen. Mit demselben Samen und derselben Größe wird dasselbe Labyrinth erstellt.
Sobald das Labyrinth generiert wurde, versucht das Programm, die Punktzahl des Labyrinths zu maximieren, indem es nach dem Start- und Endpunkt sucht, die den längsten Pfad zwischen ihnen ergeben. Dazu durchläuft es jeden Startpunkt, verteilt die Tracer, um den am weitesten entfernten Endpunkt zu finden, und wählt die Kombination mit dem längsten Pfad aus.
Danach zeichnet es das Labyrinth, zählt die Wände und gibt die Informationen des Labyrinths aus. Dies ist der Startpunkt, der Endpunkt, der Abstand zwischen ihnen, die Anzahl der Wände und die Punktzahl. Außerdem werden diese Informationen in den oben beschriebenen Stil für Größe, Anfang und Ende, horizontale Wände und vertikale Wände formatiert und zur späteren Verwendung in einer Textdatei mit dem Namen Maze.txt gespeichert.
SolveFun
Der Solver SolveFun verwendet die Textdatei Maze.txt als Eingabe und funktioniert ähnlich wie der Architekt. Für jede Bewegung wählt es eine Richtung, die es gehen möchte, basierend auf seiner relativen Position zum Ende, und dann schaut es auf die Wände, die es umgeben. Wenn eine Wand nicht vorhanden ist, wird geprüft, ob sie sich in der angrenzenden Zelle befindet. Andernfalls wird sie als mögliche Option hinzugefügt. Es bewegt sich dann in die Richtung, die seiner Vorzugsrichtung am nächsten kommt, sofern es über Optionen verfügt. Wenn es keine Optionen gibt, wird es zurückverfolgt, bis dies der Fall ist. Dies geht so lange weiter, bis das Ende erreicht ist.
Während der Bewegung zeichnet es den Pfad, den es nimmt, in dem variablen Pfad auf, der am Ende zur Ausgabe der Gesamtzahl der Schritte verwendet wird. Es zeichnet auch auf, wie oft es zurückverfolgt werden musste, um die verschwendeten Schritte am Ende zu berechnen. Wenn es das Ende erreicht, gibt es das Labyrinth mit dem kürzesten Weg vom Anfang zum Ende aus, der mit
*
s markiert ist .Wie man läuft
Aufgrund der Methode zur Ausgabe des Labyrinths (die das Unterstreichen bestimmter Zeichen umfasst) muss dies über eine Befehlszeile im Formular ausgeführt werden
python -c 'import filename;filename.BuildFun(Size, Seed)'
und
python -c 'import filename;filename.SolveFun()'
Dabei ist Size eine ganze Zahl zwischen 15 und 50 (einschließlich) und Seed eine ganze Zahl zwischen 4 und Size (einschließlich).
quelle