Celem tego wyzwania jest stworzenie najkrótszego kodu (w znakach), który z powodzeniem wykona następujące czynności:

Dane techniczne :

• Musisz stworzyć 5x5x5 labyrinthdokładnie 1 possible solution(nie więcej, nie mniej)
• Labirynt musi zostać stworzony randomly Musi być w stanie wygenerować każde istniejące rozwiązanie, jeśli będzie działać przez lata
• startI finishmuszą być umieszczone w*opposite corners
• Mapa outputmusi mieć jeden z następujących formatów:

Opcja formatu wyjściowego 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

Opcja formatu wyjściowego 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]]

Uwagi wyjściowe:

• Użyj 0dla emptyi 1dlasquares

• Linie przerwania NIE są konieczne

• Ty decydujesz, co indexjest co, ale po prostu dobrze to wytłumacz

* Oto przykład tego, co rozumiem przez przeciwne rogi:

Wyjaśnienia :

• NIE można się wprowadzićdiagonal
• NIE można przejść dwukrotnie tą samą ścieżką
• Posiadanie inaccessible areasjest dozwolone
• Możesz go up/downwięcej niż jeden poziom z rzędu

Wskazówki:

• Nie postrzegaj ich jako ścian, zamiast tego postrzegaj je jako 5x5x5stos kwadratów, których niektórych brakuje, i możesz przejść przez te brakujące

C ++ C, około 1000 670 643 395 297 248 znaków

Przykładowe dane wyjściowe:

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,

Jak to działa: program wykorzystuje Brownian Motion do generowania rozwiązań. Punkt początkowy jest ustawiony. Następnie wybierany jest losowy punkt i wielokrotnie przesuwany losowo, aż dotknie jednego i tylko jednego punktu na gałęzi początkowej. Punkt jest następnie ustawiany, a jeśli dotyka on również punktu końcowego, program kończy pracę i wyświetla się macierz. Ponieważ żaden punkt nie może połączyć dwóch gałęzi, istnieje tylko jedna ścieżka przez labirynt. Program korzysta z funkcji rand i argumentu liczb całkowitych wiersza poleceń jako zarodka, więc przy wystarczającej funkcji rand powinno być możliwe wygenerowanie wszystkich poprawnych labiryntów (ten algorytm nie utworzy jednak niepowiązanych obszarów, więc nie wygeneruje wszystkich możliwe labirynty).

Ruch Browna został porzucony, ponieważ okazał się niepotrzebny, a jego usunięcie znacznie upraszcza kod. Sądzę jednak, że dzięki temu były ładniejsze labirynty. Podobnie zrezygnowano z argumentu źródłowego, ponieważ wymaganie bezstanowego generatora liczb losowych ma dla mnie więcej sensu niż ziarno 128-bitowe.

Możliwe jest, że program utknie w nieskończonej pętli, ponieważ jest to możliwe w sytuacjach, w których dowolny punkt dodany do gałęzi utworzyłby wiele ścieżek. Można to naprawić, ale myślę, że jest to dość rzadkie, aby nie przejmować się golfem kodowym.

#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);
}

Dodałem znaki nowej linii i wcięcia do wyświetlanego kodu w celu zapewnienia czytelności.

JavaScript, 874 816 788 686 682 668 637 znaków

próbka wyjściowa:

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

ten działa, zaczynając od punktu [0,0,0] i losowo dodając dołączenie jeszcze jednego 0 obok 0, gdziekolwiek jest to dozwolone (dozwolone == nowe 0 nie znajduje się obok żadnych innych zer z wyjątkiem nadawcy), dopóki nie będzie już więcej możliwe uzupełnienia.

jeśli jakieś nowe 0 znajduje się obok punktu wyjścia (x * y * z == 48), wówczas otwieramy wyjście.

grał w golfa

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"))

oryginalny

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"));

Mathematica: True Labyrinth (827 znaków)

Początkowo stworzyłem ścieżkę od {1,1,1} do {5,5,5}, ale ponieważ nie było żadnych możliwych złych zwrotów, wprowadziłem widelce lub „punkty decyzyjne” (wierzchołki stopnia> 2), w których trzeba by zdecydować, którą drogą iść. Rezultatem jest prawdziwy labirynt lub labirynt.

„Ślepe zaułki” były o wiele trudniejsze do rozwiązania niż znalezienie prostej, bezpośredniej ścieżki. Najtrudniejszą rzeczą było wyeliminowanie cykli na ścieżce, jednocześnie umożliwiając cykle poza ścieżką rozwiązania.

Poniższe dwa wiersze kodu są używane tylko do renderowania narysowanych wykresów, więc kod się nie liczy, ponieważ nie jest wykorzystywany w rozwiązaniu.

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

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

Zastosowany kod:

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]

Próbka wyjściowa

{{„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 ”}}

Pod maską

Poniższy obrazek pokazuje labirynt lub labirynt, który odpowiada rozwiązaniu ({{"ooxoo",...}}przedstawionemu powyżej:

Oto ten sam labirynt wstawiony w 5x5x5 GridGraph. Ponumerowane wierzchołki są węzłami na najkrótszej drodze z labiryntu. Zwróć uwagę na rozwidlenia lub punkty decyzyjne na 34, 64 i 114. Dołączę kod użyty do renderowania wykresu, nawet jeśli nie jest on częścią rozwiązania:

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

A ten wykres pokazuje tylko rozwiązanie labiryntu:

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

Na koniec kilka definicji, które mogą pomóc w odczytaniu kodu:

Oryginalne rozwiązanie (432 znaków, wyprodukowano ścieżkę, ale nie prawdziwy labirynt lub labirynt)

Wyobraź sobie dużą solidną kostkę 5 x 5 x 5 złożoną z odrębnych kostek jednostkowych. Poniższe rozpoczyna się bez kostek jednostkowych w {1,1,1} i {5,5,5}, ponieważ wiemy, że muszą być częścią rozwiązania. Następnie usuwa losowe kostki, aż do uzyskania niezakłóconej ścieżki od {1,1,1} do {5,5,5}.

„Labirynt” jest najkrótszą ścieżką (jeśli możliwa jest więcej niż jedna), biorąc pod uwagę usunięte kostki jednostek.

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]

Przykład:

{{"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"}}

Technicznie nie jest to jeszcze prawdziwy labirynt, ponieważ nie ma żadnych złych zwrotów, które można wykonać. Ale pomyślałem, że to interesujące na początek, ponieważ opiera się na teorii grafów.

Rutyna faktycznie tworzy labirynt, ale podłączyłem wszystkie puste miejsca, które mogłyby powodować cykle. Jeśli znajdę sposób na usunięcie cykli, dołączę ten kod tutaj.