# Textual maze solver

Given a maze on stdin and an entry point, write a program that prints a path to the exit on stdout. Any path is acceptable, as long as your program does not generate the trivial path (passing through every point in the maze) for every maze.

In the input, walls are marked by a # and the entry point by a @. You may use any characters to draw the maze and the path in the output, as long as they're all distinct.

You may assume that:

• The entry and exit points are on the edges of the input
• Every line of the input has the same length
• The maze is solvable and has no cycles
• There is only one exit point

Shortest solution by (Unicode) character count wins.

## Examples

(note that the inputs are padded with spaces)

####
#  #
@ #####
#     #
#
#######

####
#  #
@*#####
#*    #
#******
#######

### ###################
###         #         #
##  #########      #  #
#             #####  #
###############   #@##

###*###################
###*********#*********#
## *#########*     # *#
# *********** #####**#
###############   #@##

• Can I add a character for the endpoint, also? It would make it much easier for my program to know when to end. Apr 25 '11 at 13:38
• @Peter Of The Corn: Sure. You don't have to use the same character to draw the entire path, it just has to be distinguishable from the rest of the output. Apr 25 '11 at 13:47

ANSI C (384 373 368 characters)

Here's my C attempt. Compiled and run on Mac OS X.

m[9999],*r=m,*s=m,c,R=0,*a,L;
P(){while(*s++)putchar(*(s-1));}
C(int*l){if((l-s+2)%R==0||(l-s)%R==0||l-s<R||l>r-R)*l=42,P(),exit(0);}
e(int*l){if(*l==32)C(l),*l=42,e(l-1),*l=32,*l=42,e(l-R),*l=32,*l=42,e(l+1),*l=32,*l=42,e(l+R),*l=32;}
main(){while(~(c=getchar()))*r++=c,R=!R&&c==10?r-s:R,L=c==64?r-s-1:L;L%R==0&&e(s+L+1);(L+2)%R==0&&e(s+L-1);L<R&&e(s+L+R);e(s+L-R);}


Sample output for a couple of tests:

####
#  #
@*#####
#*****#
#    *#
#####*#

###*###################
###*        #******** #
##**#########**    #* #
#*************#####* #
###############   #@##


Limitations: Only works for mazes up to 1000 characters, but this can easily be increased. I just picked an arbitrary number rather than bother to malloc/remalloc.

Also, this is the most warning-laden code I've ever written. 19 warnings, though it looks like even more with the XCode code highlighting. :D

EDITS: Edited and tested to drop int from main, to use ~ instead of !=EOF and putchar instead of printf. Thanks for the comments!

• You could use 9999 - it's the same number of characters Apr 25 '11 at 11:38
• Good job! Omit the "int " before main and save 4 characters. Also use putchar(*(s-1)) instead of printf("%c",*(s-1)) to save 4 more. Apr 25 '11 at 12:14
• You can also replace 0xA by 10 and != by ^. Apr 25 '11 at 12:33
• Even better: you can use the ~ operator to check for EOF: while(~(c=getchar()) Apr 25 '11 at 13:50
• I can also drop the !L&& guard on setting L, the location in the maze of the '@'. Apr 25 '11 at 14:25

## Ruby 1.9, 244 characters

l=*$< i=l*"" e=[] d=[1,-1,x=l[0].size,-x] r=[f=9e9]*s=x*b=l.size;r[i=~/@/]=0 r.map{i.gsub(/ /){r[p=$.size]=d.map{|u|p>-u&&r[u+p]||f}.min+1;e<<p if p%x%~-~-x*(p/-~x%~-b)<1}}
r[g=e.find{|i|r[i]<f}].times{i[g]=?*;g+=d.find{|l|r[g]>r[g+l]}}
puts i


Output for the two examples:

####
#  #
@*#####
#*    #
#******
#######

###*###################
###*        #     *** #
## *######### *****#* #
# ************#####* #
###############   #@##


Edits:

• (247 -> 245) Inlined e and renamed it to g
• (245 -> 249) Fix a bug when the exit is directly above the entrance
• (249 -> 246) Inlining + simplifications
• (246 -> 244) Shorter way to iterate over every field

## Python, 339 chars

import sys
L=len(M)
R=range(L)
N=M.index('\n')+1
D=2*L*[9e9]
D[M.index('@')+N]=0
J=(1,-1,N,-N)
for x in R:
for i in[N+i for i in R if' '==M[i]]:D[i]=min(1+D[i+j]for j in J)
e=[i+N for i in R[:N]+R[::N]+R[N-2::N]+R[-N:]if 0<D[i+N]<9e9][0]
while D[e]:M[e-N]='*';e=[e+j for j in J if D[e+j]<D[e]][0]
print''.join(M)


Generates a shortest path through the maze.

Output for example mazes:

####
#  #
@*#####
#*    #
#******
#######

###*###################
###*        #     *** #
## *######### *****#* #
# ************#####* #
###############   #@##

• Why all the additions and subtractions by N? Apr 25 '11 at 12:05
• It prevents the indexing D[i+j] in line 10 from going negative. And D[e+j] in line 12. Apr 25 '11 at 14:45

Python - 510 421 chars

m=[]
i=raw_input
l=i()
x=y=-1
while l:
if y<0:x+=1;y=l.find('@')
m.append(list(l));l=i()
s=(x,y)
t={}
q=[s]
v={s:1}
while 1:
try:(i,j),q=q[0],q[1:];c=m[i][j]
except:continue
if c==' 'and(i*j==0)|(i+1==len(m))|(j+1==len(m[0])):break
for d,D in(-1,0),(0,-1),(1,0),(0,1):
p=(i+d,j+D)
if not p in v and'#'!=c:v[p]=0;q.append(p);t[p]=(i,j)
while(i,j)!=s:m[i][j]='*';i,j=t[(i,j)]
print'\n'.join(''.join(l)for l in m)

• I'm getting a * on the bottom-right corner, on the first test case (python 2.6.1). Any thoughts? Apr 24 '11 at 23:15
• @Lowjacker Thanks, it seems that while golfing I added a bug that made it look like it worked, but just for the test cases, and even then barely :P
– Juan
Apr 25 '11 at 0:01
• Good, it works now. But you forgot to take out the print b,r and the print (i,j), which I presume were for debugging :) Apr 25 '11 at 0:11

# 05AB1E (legacy), 23 22 bytes

[¾#4Føí„ *„@*δJ:¬'*¢½


Try it online!

### Modern 05AB1E, 26 bytes

[¾#4F€SøíJ„ *„@*â2ô:¬'*¢½


Try it online!

# Python 3, 270 bytes

import sys
def q(g,*s):w=len(g[0])+1;k='@'.join(g)+w*'@';*p,x=s or[k.find('#')];return'@'>k[x]and{x}-{*p}and[p,min((q(g,*s,x+a)or k for a in(-1,1,-w,w)),key=len)]['*'>k[x]]

Uses '#' for start, '*' for end, '@' for wall and ' ' for empty space. In this, the function q is a helper function which returns a one-dimensional array with the shortest path in the maze. Function f can be shortened 4 bytes by not assigning the variable s`. This is incredibly inefficient and will likely time out, since it calls the path-finding function for each character in the maze.