Buat multi-level 5x5x5 Labirin dengan hanya satu solusi

11

Tujuan dari tantangan ini adalah untuk membuat kode terpendek (dalam karakter) yang berhasil melakukan hal berikut:

Spesifikasi :

  • Harus membuat 5x5x5 labyrinthdengan tepat 1 possible solution(tidak lebih, tidak kurang)
  • Labirin harus dibuat randomly Itu harus dapat menghasilkan setiap solusi yang ada jika dibiarkan berjalan selama bertahun-tahun
  • The startdan finishharus ditempatkan dalam*opposite corners
  • Peta outputharus dalam salah satu format berikut:

Format output opsi 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

Format keluaran opsi 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]]

Catatan keluaran:

  • Gunakan 0untuk emptydan 1untuksquares

  • Garis putus TIDAK perlu

  • Anda memutuskan apa indexitu apa, tetapi pastikan untuk menjelaskannya dengan baik


* Ini adalah contoh dari apa yang saya maksud dengan sudut yang berlawanan:

masukkan deskripsi gambar di sini

Klarifikasi :

  • TIDAK BISA pindahdiagonal
  • TIDAK BISA melewati dua kali di jalur yang sama
  • Memiliki inaccessible areasdiizinkan
  • Anda dapat go up/downlebih dari satu level dalam satu baris

Kiat:

  • Jangan melihatnya sebagai dinding, sebaliknya lihatlah sebagai 5x5x5tumpukan kotak yang beberapa di antaranya hilang dan Anda dapat melewati yang hilang
ajax333221
sumber
Jika ada sesuatu yang tidak jelas, tanyakan saja kepada saya :)
ajax333221
3
Namun, ada satu detail yang ingin saya klarifikasi: apakah dinding ditempatkan di antara kotak, atau apakah dinding memenuhi seluruh kotak?
Ilmari Karonen
1
Anda mengatakan 5x5 (array 2D) di beberapa tempat, namun sampel kode dan gambar menyarankan 5x5x5 (array 3D). Saya menganggap array 3D adalah apa yang dimaksud?
Kae Verens
1
bagaimana diputuskan bahwa solusinya adalah labirin yang valid? Maksud saya, apakah jumlah cabang yang dimiliki jalur yang benar? apakah ada hubungannya dengan rasio 1s ke 0s?
Kae Verens
2
Ketika Anda mengatakan "Labirin harus dibuat secara acak", batasan apa yang harus kita simpulkan? Saya berasumsi, misalnya, bahwa Anda tidak bermaksud untuk mengizinkan, seperti yang secara literal membaca peraturan saat ini, sebuah program yang memilih antara dua output hard-coded secara acak.
Peter Taylor

Jawaban:

10

C ++ C, sekitar 1000 670 643 395 297 248 karakter

Output sampel:

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,

Cara kerjanya: Program ini menggunakan Brownian Motion untuk menghasilkan solusi. Titik awal diatur. Kemudian, titik acak dipilih dan berulang kali dipindahkan secara acak hingga menyentuh satu dan hanya satu titik di cabang mulai. Titik kemudian diatur, dan jika juga menyentuh titik akhir, program keluar dan matriks ditampilkan. Karena tidak ada titik yang dapat bergabung dengan dua cabang, hanya ada satu jalur melalui labirin. Program ini menggunakan fungsi rand, dan argumen integer baris perintah sebagai seed, jadi dengan fungsi rand yang cukup, pada akhirnya mungkin untuk menghasilkan semua labirin yang valid (algoritma ini tidak akan membuat area yang tidak terhubung, jadi tidak akan menghasilkan semua mungkin labirin).

Gerakan Brown dijatuhkan karena ternyata tidak dibutuhkan dan penghapusannya menyederhanakan kode secara signifikan. Saya pikir itu membuat labirin yang lebih bagus. Demikian juga, argumen seed dijatuhkan, karena membutuhkan generator nomor acak stateless lebih masuk akal bagi saya daripada seed 128-bit.

Adalah mungkin bagi program untuk terjebak dalam infinite loop, karena dimungkinkan untuk situasi di mana setiap titik yang ditambahkan ke cabang akan membuat banyak jalur. Ini bisa diperbaiki, tapi saya pikir itu cukup langka untuk tidak menjadi perhatian untuk golf kode.

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

Saya telah menambahkan baris baru dan lekukan ke kode yang ditampilkan agar mudah dibaca.

Sir_Lagsalot
sumber
Saya pikir Anda memenangkan yang satu ini ;-) tidak mungkin saya bisa menyusutkan milik saya sejauh itu
Kae Verens
Saya benar-benar menikmati kompetisi :-) Saya sedikit terkejut kami masih satu-satunya jawaban, saya berharap seorang penulis naskah golf atau yang serupa akan mengalahkan kami berdua sekarang.
Sir_Lagsalot
Entah bagaimana, jalur sederhana, tanpa garpu atau simpul keputusan, tampaknya tidak memenuhi syarat sebagai labirin sejati. Coba tambahkan beberapa jalan buntu.
DavidC
@ David Carraher Algoritme tidak menghasilkan jalan buntu dan jalur bercabang seperti yang ditunjukkan dalam sampel. Tidak memungkinkan titik baru untuk menghubungkan dua cabang yang sudah ada hanya mencegah beberapa solusi atau siklus di labirin.
Sir_Lagsalot
@ Sir_Lagsalot Terima kasih atas klarifikasi
DavidC
5

JavaScript, 874 816 788 686 682 668 637 karakter

output sampel:

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

yang ini bekerja dengan mulai dari titik [0,0,0] dan secara acak menambahkan melampirkan satu lagi 0 di sebelah 0 di mana pun diizinkan (diizinkan == 0 baru tidak di sebelah 0 lainnya kecuali pencetus) sampai tidak ada lagi kemungkinan penambahan.

jika ada 0 baru di sebelah titik keluar (x * y * z == 48) maka kita membuka pintu keluar.

bermain golf

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

asli

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
sumber
4

Mathematica: True Labyrinth (827 chars)

Awalnya, saya membuat jalur dari {1,1,1} ke {5,5,5} tetapi karena tidak ada kesalahan yang mungkin dilakukan, saya memperkenalkan garpu atau "titik keputusan" (simpul derajat> 2) di mana orang perlu memutuskan jalan mana yang harus dilalui. Hasilnya adalah labirin atau labirin sejati.

"Jalan buntu" jauh lebih sulit untuk dipecahkan daripada menemukan jalan langsung yang sederhana. Hal yang paling menantang adalah untuk menghilangkan siklus dalam jalur sementara memungkinkan siklus dari jalur solusi.

Dua baris kode berikut hanya digunakan untuk merender grafik yang digambar, sehingga kode tidak dihitung, karena tidak digunakan dalam solusi.

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

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

Kode yang digunakan:

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]

Output sampel

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

Dibawah tenda

Gambar di bawah ini menunjukkan labirin atau labirin yang sesuai dengan solusi yang ({{"ooxoo",...}}ditampilkan di atas:

solusi1

Berikut adalah labirin yang sama yang dimasukkan dalam 5x5x5 GridGraph. Vertex bernomor adalah node pada jalur terpendek keluar dari labirin. Catat garpu atau titik keputusan pada 34, 64, dan 114. Saya akan memasukkan kode yang digunakan untuk membuat grafik meskipun itu bukan bagian dari solusi:

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

solusi2

Dan grafik ini hanya menunjukkan solusi untuk labirin:

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

solusi3

Akhirnya, beberapa definisi yang dapat membantu membaca kode:

definisi


Solusi asli (432 char, Menghasilkan jalur tetapi bukan labirin atau labirin sejati)

Bayangkan sebuah kubus padat 5x5x5 besar yang terbuat dari kubus satuan yang berbeda. Berikut ini dimulai tanpa satuan kubus pada {1,1,1} dan {5,5,5}, karena kami tahu mereka harus menjadi bagian dari solusi. Kemudian menghapus kubus acak sampai ada jalan tanpa hambatan dari {1,1,1} ke {5,5,5}.

"Labirin" adalah jalur terpendek (jika lebih dari satu dimungkinkan) mengingat satuan kubus yang telah dihapus.

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]

Contoh:

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

Secara teknis ini belum merupakan labirin sejati, karena tidak ada tikungan salah yang bisa dibuat. Tapi saya pikir ini menarik sebagai permulaan karena bergantung pada teori grafik.

Rutinitas sebenarnya membuat labirin tapi saya memasang semua lokasi kosong yang dapat menimbulkan siklus. Jika saya menemukan cara untuk menghapus siklus saya akan memasukkan kode itu di sini.

DavidC
sumber
Pembaruan yang bagus, saya suka bahwa solusi Anda yang diperbarui memungkinkan siklus di jalur non-solusi, itu membuat labirin lebih membingungkan.
Sir_Lagsalot
Terima kasih. Saya masih ingin memiliki jalur solusi itu sendiri lebih cenderung untuk menjauh dari simpul terakhir dari waktu ke waktu. Saat ini tidak disarankan (tetapi tidak sepenuhnya dicegah) oleh FindShortestPath.
DavidC
Saya tidak terlalu terbiasa dengan matlab, tetapi bisakah Anda melakukan sesuatu seperti FindShortestPath, menambahkan bias terhadap setiap node di jalur terpendek, dan kemudian menjalankan FindShortestPath lagi dengan mempertimbangkan bias sehingga akan menghindari node dalam solusi terpendek? Ini bisa dilakukan secara iteratif juga. Saya akan tertarik melihat jenis jalan apa yang akan menghasilkan.
Sir_Lagsalot
@ Sir_Lagsalot Saya memposting ini sebagai pertanyaan untuk grup Mathematica SE di sini ( Mathematica.stackexchange.com/questions/4084/… )
DavidC