# Tag Info

## Hot answers tagged maze

39

C++, 97 95 93 91 86 83 82 81 79 characters My strategy is fairly simple - an evolution algorithm that can grow, shrink, swap elements of and mutate valid sequences. My evolution logic is now nearly the same as @Sp3000's, as his was an improvement over mine. However, my implementation of the maze logic is rather nifty. This allows me to check if strings are ...

36

Hexagony, 2437 bytes The long-awaited program is here: (.=$>({{{({}}{\>6'%={}{?4=$/./\_><./,{}}{<$<\?{&P'_("'"#<".>........_..\></</(\.|/<>}{0/'$.}_.....><>)<.$)).><$./$\))'"<$_.)><.>%'2{/_.>(/)|_>}{{}./..>#/|}.'/$|\})'%.<>{=$_.\<))<>(|\4?<.{.%.|/</{=...... 34 Mathematica, 144 132 bytes Since Inception, we all know the most efficient way to draw a maze. c=0;Graphics@Most[Join@@{Circle[{0,0},i,{a=c-(r=Random[](d=2Pi-1/i)&)[],a+d}],Line[{{i},{i+1}}.{{Cos[c=a+r[]],Sin@c}}]}~Table~{i,9}] Ungolfed and example output: Of course, the lines are the walls. You're the minotaur who starts in the centre and needs to ... 33 C: 364 Bytes #define I int m[1600],i=0,r;f(I x,I y,I l){m[80*y+x]|=l;I d[]={x-1,y,2,1,x+1,y,1,2,x,y-1,8,4,x,y+1,4,8}, s[]={5,5,5,5},j=0;for(;j<4;){L:r=rand()%4;for(I k=0;k<4;)if(s[k++]==r)goto L;s[j]=r;I*p=d+ 4*s[j++],X=p[0],Y=p[1];if(!(X<0|X>79|Y<0|Y>19|m[80*Y+X])){f(X,Y,p[2]);m[80*y+x]|=p[3];}}} main(){f(0,0,4);m[9]|=4;for(;i<1600;)... 31 Python 2, 81 bytes def f(M,k=1,r='',b=0): for c in M[k][k::6]:b^=c>' ';r+=' #'[b] print r;f(M,k+3) Try it online! Takes input as a list of strings (or a list of lists of characters). Prints the output, terminating with error. The idea is similar to tsh's. We look at the characters marked as ? below to see which are spaces and which are \: +---------... 24 Mathematica, 134 130 chars Graph[Range@273,Reap[Do[c@n/._c:>#0[Sow[#<->n];n],{n,RandomSample@AdjacencyList[g=GridGraph@{13,21},c@#=#]}]&@1][[2,1]],Options@g] In fact, we can use this algorithm to generate a maze from any (undirected) graph. For example, generate a maze from the 8*8 knight's tour graph (KnightTourGraph[8,8]): Graph[Range@64,... 21 C# - 423 375 bytes Complete C# program, accepts input via STDIN, outputs "True" or "False" to STDOUT as appropriate. I could not bare to leave that Linq in there... thankfully its removal paid off! It now keeps track of seen and visited cells in an array (given it only ever looks at a finite number of them anyway). I also re-wrote the directional code, ... 20 Perl, 216 215 bytes Includes +2 for -0p Give input on STDIN. Use % for external walls, # for internal walls, 0 for empty spaces, 8 for mice and r for the starting position. The whole boards must be padded so it forms a rectangle. You can transform and run the examples as: cat dynamite.txt | perl -p0e 's/.+/a^=&/egr;s//sprintf"%-*s",lengtha,&/... 19 Python 2, 291 bytes def f(M): Y=map(max,M).index("S");X=M[Y].find("S");V={()};Q=[(0,0,0,1,"")] while Q: try:x,y,u,v,p=s=Q.pop(0);c=(Y>=y<=X-2*x)*ord(M[Y-y][X-2*x-y]) except:c=0 if c==69:return p if{c%2*s[:4]}-V:V|={s[:4]};Q+=(x+u,y+v,u,v,p+"F"),(x,y,-v,u+v,p+"R"),(x,y,u+v,-u,p+"L") return"Invalid maze!" A function, f, taking the ... 19 Befunge, 344 bytes &v>>>#p_:63p:43g\!+v>/*53g+\01g:2%2*1-\2/!*63g+\0\:v 40 v++!\g14:p35:\<^2\-1*2%2p10::%4+g00:\g36\g35-1_v #11^_83p73v >1+:41g!#v_,1+:43g!#v_@>->2>+00p+141^_ <p1^ vp< ^,g+7g36:<<<<1+55p36:<<<< ^1?0^#7g36g35* 8&p|!++!%9#2g+7g10\*!-g38g10!-g37:g00!!*<>3^ 443>:... 19 JavaScript (Node.js), 85 bytes a=>a.flatMap(u=(l,y)=>y%3?[]:[l.flatMap((c,x)=>x<y|(x-=y+3)%6?[]:' #'[u[x]^=c+1<0])]) Try it online! Basic idea is: we only care about the characters on$ (6x+3y+3,3y) \$. If it is a dash (-), current cell has the different value with the one on its top, and if it is a space (), current cell has the same ...

17

Python 3 + PyPy, 82 80 characters SWWNNSENESESWSSWSEENWNWSWSEWNWNENENWWSESSEWSWNWSENWEENWWNNESENESSWNWSESESWWNNESE I've been hesitant to post this answer because I've basically taken orlp's approach and put my own spin on it. This string was found by starting with a pseudorandom length 500 solution - quite a number of seeds were tried before I could break ...

15

Java, 1,843 My first try of solving this puzzle with Java. I know, that there are a lot of improvements to make it shorter. But in the end it works for now. To try it, you have to create a class C and paste the code. args[0] (strictly speaking a[0]) is for input. The print method of the map is not included since it's not necessary for the puzzle output. ...

13

Bash, 53 bytes w=(╱ ╲);while true;do echo -n ${w[RANDOM%2]};done Similar idea to the C64 code. Uses Unicode characters as the slashes because they look much nicer in a terminal that supports Unicode. Sample output on OS X Terminal (Menlo font): 13 JavaScript, 863 834 785 781 bytes Saved 29 bytes thanks to ETHproductions Saved 53 bytes thanks to Jordan L=[] f=(S,r="",R="",p=0,s=S.replace(RegExp(r),R),l=((.|\n){${s.split [0].length}}),q=p+1,o=p+2,n=p+50)=>s in L|p>999?1e3:!/M/.test(s,L[s]=0)&/E/.test(s)?p:Math.min(...[[/ E/,"me",q],[/ E/,"de",o],[/ME/,"ce",q],[/E /,"em",q],[/E /,"ed",o],[...

13

Perl 6, 259 295 bytes {my \a=S:g/(.)$0+/{$0 x($/.comb+.5)*2/3}/;sub f (\c,\v,*@p) {with (c ne any v)&&a.lines».comb[+c[0];+c[1]] ->$_ {for (/\s/??10011221!!/I/??a~~/^\N*I|I\N*$/??2101!!1012!!'').comb X-1 {f [c Z+$^a,$^b],(|v,c),@p,chr 8592+$++} take @p if /U/}} [~] (gather f a~~/(\N+\n)*(.)*I/,[]).min(+*)[1,3...*]} How it works my \a = S:g/ (.) ...

12

Python 3, 1491 Bytes I found this to be a fun project and very interesting (and somewhat lengthy). When I saw this, I was reminded of the summer I spent exclusively writing and improving a maze generation algorithm and instantly got to work on this. After a while, I had an initial draft around 6000 bytes long and I spent the next couple of hours condensing ...

11

JavaScript (ES6), 186 201 f=([...s])=>(g=(i,l,c=k=" ")=>s[i]!=k&&s[i]!="@"?0:(i-130)?(s[i]=c,([..."/-\\"].some((c,j)=>!((--j&l&&j!=l)||!g(i+33*(l||j)+1,j,c)))||!(s[i]=k))):(s[i]="@",!console.log(s.join(""))))(99) Runnable snippet: <script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></...

11

MATLAB, 316 305 300 293 bytes function P=f(a,b);z(a,b)=0;P=z;c=@(X)conv2(+X,[0,1,0;1,1,1;0,1,0],'s');B=1;while B;P=z;P(1)=1;for K=1:a*b;S=z;S(a,b)=1;for L=2:a*b;S(~S&c(S)&~P)=L;end;[i,j]=find(S&c(P==K));if i;r=randi(nnz(i));else;break;end;P(i(r),j(r))=K+1;if P(a,b);break;end;end;B=any(any(c(P>0)>3));end;P(P>0)=35;P=[P,''] Thanks @...

11

No dead ends near the entrance, 21,477,560 21,485,005 Try it online! Yay, 21 million. The giant horizontal segments up to row 19 are also removed, so about 20% of the entire grid is just an open space. Also, as the "real maze" starts at the leftmost column, moving the entrance to the top right gives a slight bump to the score. (Thanks to @Neil) ...

11

Tridents, score 21,947,177 21,951,598 UEsDBBQAAAAIAAAAIQAL/+yrSgAAAIgAAAAJABQAYXJyXzAubnB5AQAQAIgAAAAAAAAASgAAAAAAAACb7BfqGxDJyFDGUK2eklqcXKRupaBuk2mirqOgnpZfVFKUmBefX5SSChJ3S8wpTgWKF2ckFqQC+RpGOpo6CrUKFACuFAYGBhAGAFBLAwQUAAAACAAAACEAlmPInE8AAACQAAAACQAUAGFycl8xLm5weQEAEACQAAAAAAAAAE8AAAAAAAAAm+wX6hsQychQxlCtnpJanFykbqWgbpNpoq6joJ6WX1RSlJgXn1+...

10

(why doesn't bash let me do that?) I just had to now. Bash, 12743 chars #!/bin/bash IFS= declare -a term typeset -i term[0] term[1] IFS=' ' read -a term <<< stty size front[0]='\e[2;2H██████████████ \e[3;2H██████████████ \e[4;2H██████████████ \e[5;2H██████████████ \e[6;2H██████████████ \e[7;2H██████████████ \e[8;2H██████████████ \e[9;2H█████████...

10

Commodore 64 Basic Man, that was fun. And hard. C64 Basic is almost undebuggable, you can't even use print debugging because the screen is already taken for rendering the dungeon. You know you're having fun when you're writing code like 55250 goto 55110. Dijkstra will kill me. The program uses two colors, and diagonal characters. Needless to say I didn't ...

10

C: 265 253 Bytes #define f(v)for(v=0;v<k;++v) #define d(q,n)case q:r(c+n,c+2*n); z[4225],i,j,k=65;r(p,c){if(!z[c]){z[p]=z[c]=1;f(p)switch(rand()%4){d(0,-k)d(1,k)d(2,-1)d(3,1)}}}main(){f(i)z[i]=z[i+4160]=z[i*k]=z[i*k+64]=z[4157]=1;r(67,132);f(i)f(j)putchar(33-z[i*k+j]);} (Requires 65-character terminal) Generates a relatively random 31x31 maze with one ...

10

Python 2 - 258 210 244 bytes Recursively check paths, if stack overflow return 1 (truthy) else return None (falsey). import sys def k(s): a=len(s);m=[[c=='.'for c in b]*999for b in s.split('\n')]*999;sys.setrecursionlimit(a) for x in range(a*a): try:p(m,x/a,x%a) except:return 1 def p(m,x,y): if m[x][y]:m[x][y]=0;map(p,[m]*4,[x,x,x+1,x-1],[y+1,y-1,y,...

10

Jelly, 36 35 34 33 32 bytes 2*×5H_2Bị⁾ | _3”-ẋ”+;;Çsẋ2U3¦ṁµY TryItOnline! Builds a nighter™ the other way around to the examples like: +---- | | | | ----+ | | +---- | | | | ----+ How? 2*×5H_2Bị⁾ | - Link 1, pipes & spaces: n e.g. 7 2* - 2 raised to the nth power e.g. 128 ×5 - multiply by 5 ...

10

Slip, 2 + 1 = 3 bytes +1 byte for the p flag. Code: # Explanation: The p-flag returns the position of each occurence of the following: # // The character '#' Try it here!

10

Pyth, 356 345 + 1 = 346 bytes The code contains some unprintables, so here is the reversible xxd hexdump. 0000000: 4a4b 304c 2c3d 2b4b 4062 4a58 624a 3041 JK0L,=+K@bJXbJ0A 0000010: 2c63 6a43 2201 e120 49b4 efbc e267 27f4 ,cjC".. I....g'. 0000020: a11b f5d5 7f79 d1a0 ab8a 7689 449f 0c50 .....y....v.D..P 0000030: b2d4 7c30 99c3 368e aa67 4213 ab9b d276 .....

10

Score: 8066 8065 walls I found an 8066 wall solution using dynamic programming over solutions that can be recursively decomposed by splitting on a row or column consisting entirely of floors or entirely of walls. The implementation of this apparently simple idea was rather more complicated than its description, since there are 17 different types of ...

9

JavaScript (ES6), 174 This is the maze builder I used in this other challenge, just golfed. It's a function with 2 parameters: rows and columns. The maze is totally connected with no loops, so any location can be the starting or ending point. (r,c,o=2*c+2,i=2*r*o+o,z=[],F=(p,i=Math.random()*4)=>[o,1,-o,-1].map((s,j,d)=>z[s=p+2*d[j+i&3]]>0&&...

Only top voted, non community-wiki answers of a minimum length are eligible