Erstellen Sie ein mehrstufiges 5x5x5-Labyrinth mit nur einer Lösung

11

Ziel dieser Herausforderung ist es, den kürzesten Code (in Zeichen) zu erstellen, der Folgendes erfolgreich ausführt:

Technische Daten :

  • Muss ein 5x5x5 labyrinthmit genau erstellen 1 possible solution(nicht mehr und nicht weniger)
  • Das Labyrinth muss geschaffen werden randomly Es muss in der Lage sein, jede vorhandene Lösung zu generieren, wenn es jahrelang ausgeführt wird
  • Das startund finishmuss in platziert werden*opposite corners
  • Die Karte outputmuss 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 0für emptyund 1fürsquares

  • Unterbrechungslinien sind NICHT erforderlich

  • Sie entscheiden, was was indexist, aber stellen Sie sicher, dass Sie es gut erklären


* Hier ist ein Beispiel dafür, was ich mit gegenüberliegenden Ecken meine:

Geben Sie hier die Bildbeschreibung ein

Erläuterungen :

  • Kann NICHT einziehendiagonal
  • Kann NICHT zweimal auf demselben Pfad passieren
  • Haben inaccessible areasist erlaubt
  • Sie können go up/downmehrere Ebenen hintereinander ausführen

Tipps:

  • Sehen Sie sie nicht als Wände, sondern als 5x5x5Stapel von Quadraten, von denen einige fehlen, und Sie können die fehlenden durchgehen
ajax333221
quelle
Wenn etwas unklar ist, frag mich einfach :)
ajax333221
3
Es gibt jedoch ein Detail, das ich näher erläutern möchte: Sind Wände zwischen Quadraten angeordnet oder füllt eine Wand ein ganzes Quadrat aus?
Ilmari Karonen
1
Sie sagen an einigen Stellen 5x5 (ein 2D-Array), aber die Codebeispiele und das Bild deuten auf 5x5x5 (ein 3D-Array) hin. Ich nehme an, das 3D-Array ist gemeint?
Kae Verens
1
Wie wird entschieden, dass die Lösung ein gültiges Labyrinth ist? Ich meine, ist es die Anzahl der Ableger, die der richtige Weg hat? hat das etwas mit dem Verhältnis von 1s zu 0s zu tun?
Kae Verens
2
Wenn Sie sagen "Das Labyrinth muss zufällig erstellt werden", auf welche Einschränkungen sollten wir schließen? Ich gehe zum Beispiel davon aus, dass Sie nicht beabsichtigen, ein Programm zuzulassen, das zufällig zwischen zwei fest codierten Ausgaben wählt, wie dies beim wörtlichen Lesen der Regeln derzeit der Fall ist.
Peter Taylor

Antworten:

10

C ++ C, ungefähr 1000 670 643 395 297 248 Zeichen

Beispielausgabe:

00111,10011,10111,00110,11000,
11001,01010,00100,11011,10101,
10111,10101,10001,01010,00101,
11001,11110,11100,11110,10101,
11100,10010,11001,10101,00000,

So funktioniert es: Das Programm verwendet Brownian Motion , um Lösungen zu generieren. Der Startpunkt ist festgelegt. Dann wird ein zufälliger Punkt ausgewählt und 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-Funktion und 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.

#define M m[*p+1][p[1]][p[2]]
#define F(a,b)for(p[a]=5;p[a]--;putchar(b))
#define f for(i=3;i--;p[i]
p[]={4,4,4},h[3],m[7][6][6]={1};
main(i){
    for(M=2;h[1]^1||(M=1)^h[2];){
        f=rand()%5)
            h[i]=0;
        f++)
            p[i]++,
            h[M]++,
            p[i]-=2,
            h[M]++;
    }
    F(0,10)
        F(1,44)
            F(2,48+!M);
}

Ich habe dem angezeigten Code zur besseren Lesbarkeit Zeilenumbrüche und Einrückungen hinzugefügt.

Sir_Lagsalot
quelle
Ich denke du
gewinnst diesen ;-)
Ich habe den Wettbewerb wirklich genossen :-) Ich bin ein bisschen überrascht, dass wir immer noch die einzigen Antworten sind. Ich hatte erwartet, dass ein Golf-Scripter oder ähnliches uns beide inzwischen geschlagen hätte.
Sir_Lagsalot
Irgendwie scheint ein einfacher Pfad ohne Gabeln oder Entscheidungsknoten kein echtes Labyrinth zu sein. Versuchen Sie, einige Sackgassen hinzuzufügen.
DavidC
@ David Carraher Der Algorithmus generiert Sackgassen und Verzweigungspfade, wie im Beispiel gezeigt. Wenn nicht zugelassen wird, dass ein neuer Punkt zwei bereits vorhandene Zweige verbindet, werden einfach mehrere Lösungen oder Zyklen im Labyrinth verhindert.
Sir_Lagsalot
@ Sir_Lagsalot Danke für die Klarstellung
DavidC
5

JavaScript, 874 816 788 686 682 668 637 Zeichen

Beispielausgabe:

00000,10111,10111,01010,11000
01011,01000,01010,01111,00011
00100,11010,00111,10111,11010
01111,10001,01110,01010,01000
00000,11110,00001,10101,10110

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

b=[]
I=Math.random
for(i=5;i--;)for(j=5,b[i]=[];j--;)b[i][j]=[1,1,1,1,1]
b[0][0][0]=0
k=[[0,0,0]]
function q(x,y,z){J=b[x]
if(x<0||y<0||z<0||x>4||y>4||z>4||!J[y][z])return 
n=6-!x||b[x-1][y][z]
n-=!y||J[y-1][z]
n-=!z||J[y][z-1]
n-=x==4||b[x+1][y][z]
n-=y==4||J[y+1][z]
n-=z==4||J[y][z+1]
n==1&&v.push([x,y,z])}while(I){F=k.length
B=k[C=0|I(v=[])*F]
x=B[0]
q(x-1,y=B[1],z=B[2])
q(x,y-1,z)
q(x,y,z-1)
q(x+1,y,z)
q(x,y+1,z)
q(x,y,z+1)
if(D=v.length){k.push(A=v[0|I()*D])
b[A[0]][A[1]][A[2]]=0
if(A[0]*A[1]*A[2]==48)b[4][4][4]=I=0}else{for(E=[];F--;)F^C&&E.push(k[F])
k=E}}for(i=25;i--;)b[H=0|i/5][i%5]=b[H][i%5].join('')
alert(b.join("\n"))

Original

window.map=[];
for (i=0;i<5;++i) {
  map[i]=[];
  for (j=0;j<5;++j) {
    map[i][j]=[1,1,1,1,1];
  } 
} 
points=[[0,0,0]];
map[0][0][0]=0;
function spaces(x,y,z) {
  var n=6;
  if (x<0 || y<0 || z<0) return 0;
  if (x>4 || y>4 || z>4) return 0;
  if (!map[x][y][z]) return 0;
  if (!x || map[x-1][y][z]) n--;
  if (!y || map[x][y-1][z]) n--;
  if (!z || map[x][y][z-1]) n--;
  if (x==4 || map[x+1][y][z]) n--;
  if (y==4 || map[x][y+1][z]) n--;
  if (z==4 || map[x][y][z+1]) n--;
  return n;
} 
do {
  var index=Math.floor(Math.random()*points.length);
  point=points[index];
  v=[];
  x=point[0];
  y=point[1];
  z=point[2];
  spaces(x-1,y,z)==1 && v.push([x-1,y,z]);
  spaces(x,y-1,z)==1 && v.push([x,y-1,z]);
  spaces(x,y,z-1)==1 && v.push([x,y,z-1]);
  spaces(x+1,y,z)==1 && v.push([x+1,y,z]);
  spaces(x,y+1,z)==1 && v.push([x,y+1,z]);
  spaces(x,y,z+1)==1 && v.push([x,y,z+1]);
  if (v.length) {
    var point=v[Math.floor(Math.random()*v.length)];
    points.push(point);
    map[point[0]][point[1]][point[2]]=0;
    if (point[0]*point[1]*point[2]==48) {
      map[4][4][4]=0;
    } 
  } 
  else {
    var np=[];
    for (var i=0;i<points.length;++i) {
      i!=index && np.push(points[i]); 
    } 
    points=np;
  } 
} while(points.length);
for (i=0;i<5;++i) {
  for (j=0;j<5;++j) {
    map[i][j]=map[i][j].join('');
  } 
  map[i]=map[i].join();
} 
alert(map.join("\n"));
Kae Verens
quelle
4

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.

o = Sequence[VertexLabels -> "Name", ImagePadding -> 10, GraphHighlightStyle -> "Thick", 
    ImageSize -> 600];

o2 = Sequence[ImagePadding -> 10, GraphHighlightStyle -> "Thick", ImageSize -> 600];

Verwendeter Code:

e[c_] := Cases[EdgeList[GridGraph[ConstantArray[5, 3]]], j_ \[UndirectedEdge] k_ /; (MemberQ[c, j] && MemberQ[c, k])]

m[] :=
Module[{d = 5, v = {1, 125}},
   While[\[Not] MatchQ[FindShortestPath[Graph[e[v]], 1, 125], {1, __, 125}],

v = Join[v, RandomSample[Complement[Range[125], v], 1]]];
   Graph[e[Select[ConnectedComponents[Graph[e[v]]], MemberQ[#, 1] &][[1]]]]]

w[gr_, p_] := EdgeDelete[gr, EdgeList[PathGraph[p]]]

y[p_, u_] := Select[Intersection[#, p] & /@ ConnectedComponents[u], Length[#] > 1 &]

g = HighlightGraph[lab = m[],  PathGraph[s = FindShortestPath[lab, 1, 125]],o]
u = w[g, s]
q = y[s, u]

While[y[s, u] != {}, u =  EdgeDelete[u, Take[FindShortestPath[u,  q[[1, r = RandomInteger[Length@q[[1]] - 2] + 1]], 
  q[[1, r + 1]]], 2] /. {{a_, b_} :> a \[UndirectedEdge] b}];

q = y[s, u]]

g = EdgeAdd[u, EdgeList@PathGraph[s]];

Partition[StringJoin /@ Partition[ReplacePart[Table["x", {125}], 
Transpose[{VertexList[g], Table["o", {Length[VertexList@g]}]}]/. {{a_, b_} :>  a -> b}], {5}], 5]

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 :

Lösung1

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:

HighlightGraph[gg = GridGraph[ConstantArray[5, 3]], g,  
 GraphHighlightStyle ->"DehighlightFade", 
 VertexLabels -> Rule @@@ Transpose[{s, s}] ]

Lösung2

Und diese Grafik zeigt nur die Lösung für das Labyrinth:

HighlightGraph[gg = GridGraph[ConstantArray[5, 3]], 
   Join[s, e[s]], GraphHighlightStyle -> "DehighlightFade", VertexLabels -> Rule @@@    Transpose[{s, s}] ]

Lösung3

Schließlich einige Definitionen, die beim Lesen des Codes hilfreich sein können:

Definitionen


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.

d=5
v={1,d^3}
edges[g_,c_]:=Cases[g,j_\[UndirectedEdge] k_/;(MemberQ[c,j]&&MemberQ[c,k])]

g:=Graph[v,edges[EdgeList[GridGraph[ConstantArray[d,d]]],v]];

While[\[Not]FindShortestPath[g,1,d^3]!={},
    v=Join[v,RandomSample[Complement[Range[d^3],v],1]]]

Partition[Partition[ReplacePart[
   Table["x",{d^3}],Transpose[{FindShortestPath[g,1,d^3],Table["o",{Length[s]}]}]
      /.{{a_,b_}:>  a->b}],{d}]/.{a_,b_,c_,d_,e_}:>  StringJoin[a,b,c,d,e],5]

Beispiel:

{{"ooxxx", "xxxxx", "xxxxx", "xxxxx", "xxxxx"}, 
 {"xoxxx", "xoooo", "xxxxo", "xxxxo", "xxxxo"}, 
 {"xxxxx", "xxxxx", "xxxxx", "xxxxx", "xxxxo"}, 
 {"xxxxx", "xxxxx", "xxxxx", "xxxxx", "xxxxo"}, 
 {"xxxxx", "xxxxx", "xxxxx", "xxxxx", "xxxxo"}}

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.

DavidC
quelle
Schönes Update, ich finde es gut, dass Ihre aktualisierte Lösung Zyklen auf Nicht-Lösungspfaden zulässt, was zu einem verwirrenderen Labyrinth führt.
Sir_Lagsalot
Vielen Dank. Ich möchte immer noch, dass der Lösungspfad selbst von Zeit zu Zeit eher vom endgültigen Knoten abweicht. Dies wird derzeit von entmutigt (aber nicht vollständig verhindert) FindShortestPath.
DavidC
Ich bin mit Matlab nicht allzu vertraut, aber könnten Sie etwas wie FindShortestPath tun, eine Verzerrung für jeden Knoten auf dem kürzesten Pfad hinzufügen und dann FindShortestPath erneut ausführen, wobei die Verzerrung berücksichtigt wird, um Knoten in der kürzesten Lösung zu vermeiden? Dies könnte auch iterativ erfolgen. Es würde mich interessieren, welche Art von Pfad sich daraus ergeben würde.
Sir_Lagsalot
@ Sir_Lagsalot Ich habe dies als Frage für die Mathematica SE-Gruppe hier gepostet ( mathematica.stackexchange.com/questions/4084/… )
DavidC