Utwórz wielopoziomowy labirynt 5x5x5 za pomocą tylko jednego rozwiązania

11

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:

wprowadź opis zdjęcia tutaj

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
ajax333221
źródło
Jeśli coś jest niejasne, po prostu zapytaj mnie :)
ajax333221,
3
Chciałbym jednak wyjaśnić jeden szczegół: czy ściany są umieszczone między kwadratami, czy też ściana wypełnia cały kwadrat?
Ilmari Karonen
1
mówisz 5x5 (tablica 2D) w kilku miejscach, ale próbki kodu i obraz sugerują 5x5x5 (tablica 3D). Zakładam, że tablica 3D ma na myśli?
Kae Verens,
1
jak zdecydowano, że rozwiązaniem jest ważny labirynt? Mam na myśli, czy jest to liczba odgałęzień, które ma właściwa ścieżka? czy ma to coś wspólnego ze stosunkiem 1s do 0?
Kae Verens
2
Kiedy mówisz „Labirynt trzeba tworzyć losowo”, jakie ograniczenia powinniśmy wywnioskować? Zakładam, na przykład, że nie zamierzasz zezwalać, tak jak obecnie na dosłowne czytanie reguł, na program, który wybiera losowo dwa zakodowane wyjścia.
Peter Taylor,

Odpowiedzi:

10

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.

Sir_Lagsalot
źródło
Myślę, że
wygrałeś
Naprawdę podobała mi się konkurencja :-) Jestem trochę zaskoczony, że wciąż jesteśmy jedynymi odpowiedziami. Spodziewałem się, że golfista lub podobny pokona nas do tej pory.
Sir_Lagsalot
Jakoś prosta ścieżka, bez widelców i węzłów decyzyjnych, nie wydaje się kwalifikować jako prawdziwy labirynt. Spróbuj dodać jakieś ślepe uliczki.
DavidC
@David Carraher Algorytm generuje ślepe zaułki i ścieżki rozgałęzienia, jak pokazano w przykładzie. Niedopuszczenie do nowego punktu połączenia dwóch już istniejących gałęzi po prostu zapobiega wielu rozwiązaniom lub cyklom w labiryncie.
Sir_Lagsalot,
@Sir_Lagsalot Dzięki za wyjaśnienie
DavidC
5

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"));
Kae Verens
źródło
4

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:

rozwiązanie 1

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}] ]

rozwiązanie 2

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}] ]

rozwiązanie 3

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

definicje


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.

DavidC
źródło
Fajna aktualizacja, podoba mi się, że twoje zaktualizowane rozwiązanie pozwala na cykle na ścieżkach nierozwiązanych, sprawia, że ​​labirynt jest bardziej mylący.
Sir_Lagsalot
Dzięki. Nadal chciałbym, aby ścieżka rozwiązania była bardziej skłonna od czasu do czasu odwrócić się od ostatniego węzła. Obecnie jest to odradzane (ale nie w pełni zapobiegane) przez FindShortestPath.
DavidC
Nie znam się zbyt dobrze na Matlabie, ale czy możesz zrobić coś takiego jak FindShortestPath, dodać odchylenie dla każdego węzła na najkrótszej ścieżce, a następnie ponownie uruchomić FindShortestPath, biorąc pod uwagę odchylenie, aby uniknąć węzłów w najkrótszym rozwiązaniu? Można to zrobić również iteracyjnie. Byłbym zainteresowany zobaczeniem, jaki rodzaj ścieżki stworzyłby.
Sir_Lagsalot,
@ Sir_Lagsalot Wysłałem to jako pytanie do grupy Mathematica SE tutaj ( mathematica.stackexchange.com/questions/4084/... )
DavidC