Ziel dieser Herausforderung ist es, den kürzesten Code (in Zeichen) zu erstellen, der Folgendes erfolgreich ausführt:
Technische Daten :
- Muss ein
5x5x5 labyrinth
mit genau erstellen1 possible solution
(nicht mehr und nicht weniger) Das Labyrinth muss geschaffen werdenEs muss in der Lage sein, jede vorhandene Lösung zu generieren, wenn es jahrelang ausgeführt wirdrandomly
- Das
start
undfinish
muss in platziert werden*opposite corners
- Die Karte
output
muss in einem der folgenden Formate vorliegen:
Optionsausgabeformat 1 strings, printed or alerted
:
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx/
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx/
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx/
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx/
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx
Optionsausgabeformat 2 arrays
:
[[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx],
[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx],
[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx],
[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx],
[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx]]
Hinweise zur Ausgabe:
Verwenden Sie
0
fürempty
und1
fürsquares
Unterbrechungslinien sind NICHT erforderlich
Sie entscheiden, was was
index
ist, aber stellen Sie sicher, dass Sie es gut erklären
* Hier ist ein Beispiel dafür, was ich mit gegenüberliegenden Ecken meine:
Erläuterungen :
- Kann NICHT einziehen
diagonal
- Kann NICHT zweimal auf demselben Pfad passieren
- Haben
inaccessible areas
ist erlaubt - Sie können
go up/down
mehrere Ebenen hintereinander ausführen
Tipps:
- Sehen Sie sie nicht als Wände, sondern als
5x5x5
Stapel von Quadraten, von denen einige fehlen, und Sie können die fehlenden durchgehen
code-golf
maze
generation
ajax333221
quelle
quelle
Antworten:
C ++C,ungefähr 1000670643395297248 ZeichenBeispielausgabe:
So funktioniert es:
Das Programm verwendet Brownian Motion , um Lösungen zu generieren.Der Startpunkt ist festgelegt. Dann wird ein zufälliger Punkt ausgewähltund wiederholt zufällig verschoben,bis er einen und nur einen Punkt auf dem Startzweig berührt. Der Punkt wird dann gesetzt, und wenn er auch den Endpunkt berührt, wird das Programm beendet und die Matrix angezeigt. Da kein Punkt zwei Zweige verbinden kann, gibt es nur einen Weg durch das Labyrinth. Das Programm verwendet die Rand-Funktionund ein Integer-Argument für die Befehlszeile als Startwert.Mit einer ausreichenden Rand-Funktion sollte es möglich sein, schließlich alle gültigen Labyrinthe zu generieren (dieser Algorithmus erstellt jedoch keine nicht verbundenen Bereiche, sodass nicht alle generiert werden mögliche Labyrinthe).Die Brownsche Bewegung wurde fallen gelassen, da sie sich als nicht erforderlich herausstellte und das Entfernen den Code erheblich vereinfacht. Ich denke allerdings, dass es schönere Labyrinthe gemacht hat. Ebenso wurde das Seed-Argument gestrichen, da das Erfordernis eines zustandslosen Zufallszahlengenerators für mich sinnvoller ist als ein 128-Bit-Seed.
Es ist möglich, dass das Programm in einer Endlosschleife hängen bleibt, da es in Situationen möglich ist, in denen jeder Punkt, der zu den Zweigen hinzugefügt wird, mehrere Pfade erzeugt. Dies ist behebbar, aber ich denke, dass es selten genug ist, um sich nicht um Code-Golf zu kümmern.
Ich habe dem angezeigten Code zur besseren Lesbarkeit Zeilenumbrüche und Einrückungen hinzugefügt.
quelle
JavaScript,
874816788686682668637 ZeichenBeispielausgabe:
Dieser beginnt mit Punkt [0,0,0] und fügt nach dem Zufallsprinzip eine weitere 0 neben eine 0 ein, wo immer dies zulässig ist (erlaubt == die neue 0 steht nicht neben einer anderen 0 außer dem Urheber), bis keine weitere mehr vorhanden ist mögliche Ergänzungen.
Wenn sich neben dem Austrittspunkt eine neue 0 befindet (x * y * z == 48), öffnen wir den Ausgang.
Golf gespielt
Original
quelle
Mathematica: Wahres Labyrinth (827 Zeichen)
Ursprünglich habe ich einen Pfad von {1,1,1} nach {5,5,5} erstellt, aber da keine möglichen falschen Abbiegungen möglich waren, habe ich Gabeln oder "Entscheidungspunkte" (Eckpunkte> 2) eingeführt, bei denen man müsste sich entscheiden, welchen Weg man gehen soll. Das Ergebnis ist ein echtes Labyrinth oder Labyrinth.
Die "Sackgassen" waren weitaus schwieriger zu lösen als einen einfachen, direkten Weg zu finden. Die größte Herausforderung bestand darin, Zyklen innerhalb des Pfads zu eliminieren und gleichzeitig Zyklen außerhalb des Lösungspfads zuzulassen.
Die folgenden zwei Codezeilen werden nur zum Rendern der gezeichneten Diagramme verwendet, sodass der Code nicht zählt, da er in der Lösung nicht verwendet wird.
Verwendeter Code:
Beispielausgabe
{{"oxooo", "xxooo", "xoxxo", "xoxxo", "xxoox"}, {"ooxoo", "xoooo", "ooxox", "oooxx", "xooxx"}, {"oooxx", "ooxxo", "ooxox", "xoxoo", "xxxoo"}, {"oxxxx", "oooox", "xooox", "xoxxx", "oooxx"}, {"xxxxx", "ooxox", "oooox" "," xoxoo "," oooxo "}}
Unter der Haube
Das Bild unten zeigt das Labyrinth oder Labyrinth, das der
({{"ooxoo",...}}
oben gezeigten Lösung entspricht :Hier ist das gleiche Labyrinth in einem 5x5x5 eingefügt
GridGraph
. Die nummerierten Eckpunkte sind Knoten auf dem kürzesten Weg aus dem Labyrinth. Beachten Sie die Gabeln oder Entscheidungspunkte bei 34, 64 und 114. Ich werde den Code einfügen, der zum Rendern des Diagramms verwendet wird, obwohl er nicht Teil der Lösung ist:Und diese Grafik zeigt nur die Lösung für das Labyrinth:
Schließlich einige Definitionen, die beim Lesen des Codes hilfreich sein können:
Ursprüngliche Lösung (432 Zeichen, Produziert einen Pfad, aber kein echtes Labyrinth oder Labyrinth)
Stellen Sie sich einen 5x5x5 großen festen Würfel vor, der aus verschiedenen Einheitswürfeln besteht. Das Folgende beginnt ohne Einheitswürfel bei {1,1,1} und {5,5,5}, da wir wissen, dass sie Teil der Lösung sein müssen. Dann werden zufällige Würfel entfernt, bis ein ungehinderter Pfad von {1,1,1} zu {5,5,5} vorhanden ist.
Das "Labyrinth" ist der kürzeste Weg (wenn mehr als einer möglich ist) angesichts der entfernten Einheitswürfel.
Beispiel:
Technisch gesehen ist dies noch kein echtes Labyrinth, da es keine falschen Wendungen gibt, die man machen kann. Aber ich fand es zunächst interessant, da es auf der Graphentheorie beruht.
Die Routine bildet tatsächlich ein Labyrinth, aber ich habe alle leeren Stellen verstopft, die zu Zyklen führen könnten. Wenn ich einen Weg finde, Zyklen zu entfernen, werde ich diesen Code hier einfügen.
quelle
FindShortestPath
.