Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

The aim of this challenge is to create the shortest code (in characters) that successfully do the following:

Specifications:

  • Must create a 5x5x5 labyrinth with exactly 1 possible solution (no more, no less)
  • The labyrinth must be created randomly It must be able to generate every existing solution if left running for years
  • The start and finish must be placed in *opposite corners
  • The map output must in one of the following formats:

Option output format 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

Option output format 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]]

Output Notes:

  • Use 0 for empty and 1 for squares

  • Break lines are NOT necessary

  • You decide what index is what, but just make sure to explain it well


*Here is an example of what I mean by opposite corners:

enter image description here

Clarifications:

  • Can NOT move in diagonal
  • Can NOT pass twice on the same path
  • Having inaccessible areas is allowed
  • You can go up/down more than one level in a row

Tips:

  • Don't see them as walls, instead see them as a 5x5x5 stack of squares that some of them are missing and you can go through the missing ones
share|improve this question
    
If something is unclear, just ask me :) –  ajax333221 Mar 25 '12 at 18:43
3  
However, there's one detail I'd like a clarification on: are walls placed between squares, or does a wall fill a whole square? –  Ilmari Karonen Mar 25 '12 at 18:56
1  
you say 5x5 (a 2D array) in a few places, yet the code samples and image suggest 5x5x5 (a 3D array). I assume the 3D array is what's meant? –  Kae Verens Mar 25 '12 at 21:01
1  
how is it decided that the solution is a valid labyrinth? I mean, is it the number of offshoots that the right path has? is it something to do with the ratio of 1s to 0s? –  Kae Verens Mar 25 '12 at 21:16
2  
When you say "The labyrinth must be created randomly", what limitations should we infer? I presume, for example, that you don't intend to allow, as a literal reading of the rules currently does, a program which chooses between two hard-coded outputs at random. –  Peter Taylor Mar 25 '12 at 21:41
show 13 more comments

3 Answers

up vote 8 down vote accepted

C++ C, about 1000 670 643 395 297 248 chars

Sample output:

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,

How it works: The program uses Brownian Motion to generate solutions. The start point is set. Then, a random point is selected and repeatedly moved randomly until it touches one and only one point on the start branch. The point is then set, and if it also touches the end point, the program exits and the matrix displayed. Since no point can join two branches, there is only one path through the labyrinth. The program uses the rand function, and a command line integer argument as the seed, so with a sufficient rand function it should be possible to eventually generate all valid labyrinths (this algorithm will not create unconnected areas however, so it won't generate all possible labyrinths).

Brownian motion was dropped since it turned out to be unneeded and it's removal simplifies the code significantly. I do think it made nicer labyrinths though. Likewise, the seed argument was dropped, since requiring a stateless random number generator makes more sense to me than a 128-bit seed.

It is possible for the program to get stuck in an infinite loop, since it is possible for situations where any point added to the branches would create multiple paths. This is fixable, but I think that it is rare enough to not be a concern for code golf.

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

I've added newlines and indentation to the displayed code for readability.

share|improve this answer
    
I think you win this one ;-) there's no way I could shrink mine that far –  Kae Verens Mar 27 '12 at 21:46
    
I really enjoyed the competition :-) I'm a bit surprised we're still the only answers, I expected a golf scripter or similar would have beaten us both by now. –  Sir_Lagsalot Mar 28 '12 at 14:36
    
+1, great golfing. –  Griffin Mar 29 '12 at 21:47
    
Somehow, a simple path, with no forks or decision nodes, doesn't seem to qualify as a true labyrinth. Try adding some blind alleys. –  David Carraher Apr 8 '12 at 15:25
    
@David Carraher The algorithm does generate dead ends and branching paths as shown in the sample. Not allowing a new point to connect two already existing branches simply prevents multiple solutions or cycles in the labyrinth. –  Sir_Lagsalot Apr 9 '12 at 14:35
show 1 more comment

JavaScript, 874 816 788 686 682 668 637 characters

sample output:

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

this one works by starting from point [0,0,0] and randomly adding attaching one more 0 next to an 0 wherever allowed (allowed==the new 0 is not next to any other 0s except the originator) until there are no more possible additions.

if any new 0 is next to the exit point (x*y*z == 48) then we open up the exit.

golfed

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"));
share|improve this answer
add comment

Mathematica: True Labyrinth (827 chars)

Originally, I produced a path from {1,1,1} to {5,5,5} but because there were no possible wrong turns to be made, I introduced forks or "decision points" (vertices of degree >2) where one would need to decide which way to go. The result is a true maze or labyrinth.

The "blind alleys" were far more challenging to solve than finding a simple, direct path. The most challenging thing was to eliminate cycles within the path while allowing cycles off the solution path.

The following two lines of code are only used for rendering the drawn graphs, so the code does not count, as it is not employed in the solution.

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

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

Code used:

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]

Sample output

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

Under the hood

The picture below shows the labyrinth or maze that corresponds to the solution ({{"ooxoo",...}} displayed above:

solution1

Here is the same labyrinth inserted in a 5x5x5 GridGraph. The numbered vertices are nodes on the shortest path out of the labyrinth. Note the forks or decision points at 34, 64, and 114. I'll include the code used for rendering the graph even though it is not part of the solution:

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

solution2

And this graph shows only the solution to the labyrinth:

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

solution3

Finally, some definitions that may help reading the code:

definitions


Original solution (432 char, Produced a path but not a true maze or labyrinth)

Imagine a 5x5x5 large solid cube made up of distinct unit cubes. The following begins without unit cubes at {1,1,1} and {5,5,5}, since we know they must be part of the solution. Then it removes random cubes until there is an unimpeded path from {1,1,1} to {5,5,5}.

The "labyrinth" is the shortest path (if more than one is possible) given the unit cubes that have been removed.

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]

Example:

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

Technically this is not yet a true labyrinth, since there are no wrong turns that one can make. But I thought it interesting as a start since it relies on graph theory.

The routine actually makes a labyrinth but I plugged up all empty locations that could give rise to cycles. If I find a way to remove cycles I will include that code here.

share|improve this answer
    
Nice update, I like that your updated solution allows cycles on non-solution paths, it makes for a more confusing labyrinth. –  Sir_Lagsalot Apr 9 '12 at 14:46
    
Thanks. I would still like to have the solution path itself be more likely to veer away from the final node from time to time. This is presently discouraged (but not fully prevented) by FindShortestPath. –  David Carraher Apr 9 '12 at 15:58
    
I'm not too familiar with matlab, but could you do something like FindShortestPath, add a bias against each node in the shortest path, and then run FindShortestPath again taking into account the bias so that it will avoid nodes in the shortest solution? This could be done iteratively too. I'd be interested in seeing what type of path that would produce. –  Sir_Lagsalot Apr 9 '12 at 17:13
    
@Sir_Lagsalot I posted this as a question for the Mathematica SE group here (mathematica.stackexchange.com/questions/4084/… ) –  David Carraher Apr 9 '12 at 20:40
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.