El objetivo de este desafío es crear el código más corto (en caracteres) que haga con éxito lo siguiente:

Especificaciones :

• Debe crear un 5x5x5 labyrinthcon exactamente 1 possible solution(ni más ni menos)
• El laberinto debe ser creado randomly Debe poder generar todas las soluciones existentes si se deja funcionando durante años
• El starty finishdebe colocarse en*opposite corners
• El mapa outputdebe tener uno de los siguientes formatos:

Opción de salida formato 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

Opción formato de salida 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]]

Notas de salida:

• Usar 0para emptyy 1parasquares

• Las líneas de corte NO son necesarias

• Tú decides qué indexes qué, pero solo asegúrate de explicarlo bien

* Aquí hay un ejemplo de lo que quiero decir con esquinas opuestas:

Aclaraciones :

• NO puede mudarsediagonal
• NO puede pasar dos veces en el mismo camino
• Tener inaccessible areasestá permitido
• Puedes go up/downmás de un nivel en una fila

Consejos:

• No los vea como paredes, en cambio, véalos como una 5x5x5pila de cuadrados que faltan algunos de ellos y puede pasar por los que faltan

C ++ C, alrededor de 1000 670 643 395 297 248 caracteres

Salida de muestra:

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,

Cómo funciona: el programa utiliza Brownian Motion para generar soluciones. El punto de inicio está establecido. Luego, se selecciona un punto aleatorio y se mueve repetidamente al azar hasta que toca uno y solo un punto en la rama de inicio. Luego se establece el punto, y si también toca el punto final, el programa sale y se muestra la matriz. Como ningún punto puede unir dos ramas, solo hay un camino a través del laberinto. El programa usa la función rand y un argumento entero de línea de comando como la semilla, por lo que con una función rand suficiente debería ser posible generar eventualmente todos los laberintos válidos (sin embargo, este algoritmo no creará áreas no conectadas, por lo que no generará todos posibles laberintos).

El movimiento browniano se abandonó porque resultó ser innecesario y su eliminación simplifica significativamente el código. Sin embargo, creo que hizo laberintos más bonitos. Del mismo modo, se eliminó el argumento semilla, ya que requerir un generador de números aleatorios sin estado tiene más sentido para mí que una semilla de 128 bits.

Es posible que el programa se quede atascado en un bucle infinito, ya que es posible en situaciones donde cualquier punto agregado a las ramas crearía múltiples caminos. Esto es reparable, pero creo que es lo suficientemente raro como para no ser una preocupación para el golf de código.

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

He agregado nuevas líneas y sangría al código que se muestra para facilitar la lectura.

JavaScript, 874 816 788 686 682 668 637 caracteres

salida de muestra:

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

este funciona comenzando desde el punto [0,0,0] y agregando al azar adjuntando un 0 más al lado de un 0 donde esté permitido (permitido == el nuevo 0 no está al lado de ningún otro 0 excepto el originador) hasta que no haya más posibles adiciones.

Si cualquier nuevo 0 está al lado del punto de salida (x * y * z == 48) entonces abrimos la salida.

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

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

Mathematica: Laberinto verdadero (827 caracteres)

Originalmente, produje un camino de {1,1,1} a {5,5,5} pero como no había posibles giros incorrectos, introduje bifurcaciones o "puntos de decisión" (vértices de grado> 2) donde uno tendría que decidir qué camino tomar. El resultado es un verdadero laberinto o laberinto.

Los "callejones sin salida" eran mucho más difíciles de resolver que encontrar un camino simple y directo. Lo más desafiante fue eliminar los ciclos dentro de la ruta mientras se permitían los ciclos fuera de la ruta de la solución.

Las siguientes dos líneas de código solo se usan para representar los gráficos dibujados, por lo que el código no cuenta, ya que no se emplea en la solución.

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

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

Código usado:

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]

Salida de muestra

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

Bajo el capó

La siguiente imagen muestra el laberinto o laberinto que corresponde a la solución que se ({{"ooxoo",...}}muestra arriba:

Aquí está el mismo laberinto insertado en un 5x5x5 GridGraph. Los vértices numerados son nodos en el camino más corto fuera del laberinto. Tenga en cuenta las bifurcaciones o los puntos de decisión en 34, 64 y 114. Incluiré el código utilizado para representar el gráfico aunque no sea parte de la solución:

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

Y este gráfico muestra solo la solución al laberinto:

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

Finalmente, algunas definiciones que pueden ayudar a leer el código:

Solución original (432 caracteres, produjo un camino pero no un verdadero laberinto o laberinto)

Imagine un cubo sólido grande de 5x5x5 formado por cubos de unidades distintas. Lo siguiente comienza sin cubos unitarios en {1,1,1} y {5,5,5}, ya que sabemos que deben ser parte de la solución. Luego, elimina los cubos aleatorios hasta que haya una ruta sin obstáculos de {1,1,1} a {5,5,5}.

El "laberinto" es el camino más corto (si es posible más de uno) dados los cubos unitarios que se han eliminado.

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]

Ejemplo:

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

Técnicamente, esto aún no es un verdadero laberinto, ya que no hay giros incorrectos que uno pueda hacer. Pero, para empezar, me pareció interesante, ya que se basa en la teoría de grafos.

La rutina en realidad hace un laberinto, pero conecté todas las ubicaciones vacías que podrían dar lugar a ciclos. Si encuentro una manera de eliminar ciclos, incluiré ese código aquí.