Le but de ce défi est de créer le code le plus court (en caractères) qui réussisse à faire ce qui suit:

Spécifications :

• Doit créer un 5x5x5 labyrinthavec exactement 1 possible solution(ni plus, ni moins)
• Le labyrinthe doit être créé randomly Il doit être capable de générer toutes les solutions existantes s'il reste en service pendant des années
• Le startet finishdoit être placé dans*opposite corners
• La carte outputdoit être dans l'un des formats suivants:

Format de sortie de l'option 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 de sortie de l'option 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]]

Notes de sortie:

• Utiliser 0pour emptyet 1poursquares

• Les lignes de rupture ne sont PAS nécessaires

• Vous décidez ce qui indexest quoi, mais assurez - vous d' expliquer bien

* Voici un exemple de ce que j'entends par coins opposés:

Clarifications :

• Peut pas se déplacer dansdiagonal
• Ne peut PAS passer deux fois sur le même chemin
• Avoir inaccessible areasest autorisé
• Vous pouvez avoir go up/downplusieurs niveaux d'affilée

Conseils:

• Ne les voyez pas comme des murs, au lieu de cela, voyez-les comme une 5x5x5pile de carrés dont certains manquent et vous pouvez parcourir ceux qui manquent

C ++ C, environ 1000 670 643 395 297 248 car.

Exemple de sortie:

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,

Comment ça marche: Le programme utilise Brownian Motion pour générer des solutions. Le point de départ est défini. Ensuite, un point aléatoire est sélectionné et déplacé de manière répétée de manière aléatoire jusqu'à ce qu'il touche un et un seul point sur la branche de départ. Le point est alors défini, et s'il touche également le point final, le programme se ferme et la matrice s'affiche. Puisqu'aucun point ne peut joindre deux branches, il n'y a qu'un seul chemin à travers le labyrinthe. Le programme utilise la fonction rand et un argument entier de ligne de commande comme valeur de départ, donc avec une fonction rand suffisante, il devrait être possible de générer éventuellement tous les labyrinthes valides (cet algorithme ne créera cependant pas de zones non connectées, donc il ne générera pas tous labyrinthes possibles ).

Le mouvement brownien a été abandonné car il s'est avéré inutile et sa suppression simplifie considérablement le code. Je pense cependant que cela a rendu les labyrinthes plus agréables. De même, l'argument de départ a été abandonné, car nécessiter un générateur de nombres aléatoires sans état est plus logique pour moi qu'un départ de 128 bits.

Il est possible que le programme reste bloqué dans une boucle infinie, car il est possible dans des situations où tout point ajouté aux branches créerait plusieurs chemins. C'est réparable, mais je pense que c'est assez rare pour ne pas être un problème pour le golf de code.

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

J'ai ajouté des nouvelles lignes et une indentation au code affiché pour plus de lisibilité.

JavaScript, 874 816 788 686 682 668 637 caractères

exemple de sortie:

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

celui-ci fonctionne en commençant à partir du point [0,0,0] et en ajoutant au hasard en attachant un 0 de plus à côté d'un 0 partout où cela est autorisé (autorisé == le nouveau 0 n'est pas à côté de tout autre 0 à l'exception de l'origine) jusqu'à ce qu'il n'y en ait plus ajouts possibles.

si un nouveau 0 est à côté du point de sortie (x * y * z == 48), nous ouvrons la sortie.

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: True Labyrinth (827 caractères)

A l'origine, je produisais un chemin de {1,1,1} à {5,5,5} mais comme il n'y avait pas de mauvais virages possibles à faire, j'ai introduit des fourches ou "points de décision" (sommets de degré> 2) où il faudrait décider de la voie à suivre. Le résultat est un véritable labyrinthe ou labyrinthe.

Les «ruelles aveugles» étaient beaucoup plus difficiles à résoudre que de trouver un chemin simple et direct. La chose la plus difficile était d'éliminer les cycles dans le chemin tout en autorisant les cycles hors du chemin de la solution.

Les deux lignes de code suivantes sont uniquement utilisées pour le rendu des graphiques dessinés, donc le code ne compte pas, car il n'est pas utilisé dans la solution.

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

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

Code utilisé:

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]

Exemple de sortie

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

Sous la capuche

L'image ci-dessous montre le labyrinthe ou le labyrinthe qui correspond à la solution ({{"ooxoo",...}}affichée ci-dessus:

Voici le même labyrinthe inséré dans un 5x5x5 GridGraph. Les sommets numérotés sont des nœuds sur le chemin le plus court hors du labyrinthe. Notez les fourchettes ou points de décision à 34, 64 et 114. Je vais inclure le code utilisé pour le rendu du graphique même s'il ne fait pas partie de la solution:

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

Et ce graphique ne montre que la solution au labyrinthe:

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

Enfin, quelques définitions qui peuvent aider à lire le code:

Solution originale (432 caractères, produit un chemin mais pas un vrai labyrinthe ou un vrai labyrinthe)

Imaginez un grand cube solide de 5x5x5 composé de cubes unitaires distincts. Ce qui suit commence sans cubes unitaires à {1,1,1} et {5,5,5}, car nous savons qu'ils doivent faire partie de la solution. Ensuite, il supprime des cubes aléatoires jusqu'à ce qu'il y ait un chemin libre de {1,1,1} à {5,5,5}.

Le "labyrinthe" est le chemin le plus court (si plus d'un est possible) étant donné les cubes unitaires qui ont été retirés.

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]

Exemple:

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

Techniquement, ce n'est pas encore un vrai labyrinthe, car il n'y a pas de mauvais virages que l'on puisse faire. Mais je l'ai trouvé intéressant pour commencer car il repose sur la théorie des graphes.

La routine fait en fait un labyrinthe mais j'ai bouché tous les emplacements vides qui pourraient donner lieu à des cycles. Si je trouve un moyen de supprimer les cycles, j'inclurai ce code ici.