14
\$\begingroup\$

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)

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

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

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

###*###################
###*********#*********#
## *#########*     # *#
 # *********** #####**#
 ###############   #@##
\$\endgroup\$
  • \$\begingroup\$ Can I add a character for the endpoint, also? It would make it much easier for my program to know when to end. \$\endgroup\$ – Peter Olson Apr 25 '11 at 13:38
  • \$\begingroup\$ @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. \$\endgroup\$ – Lowjacker Apr 25 '11 at 13:47
5
\$\begingroup\$

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
\$\endgroup\$
8
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ You could use 9999 - it's the same number of characters \$\endgroup\$ – Lowjacker Apr 25 '11 at 11:38
  • \$\begingroup\$ 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. \$\endgroup\$ – Casey Apr 25 '11 at 12:14
  • \$\begingroup\$ You can also replace 0xA by 10 and != by ^. \$\endgroup\$ – Lowjacker Apr 25 '11 at 12:33
  • \$\begingroup\$ Even better: you can use the ~ operator to check for EOF: while(~(c=getchar()) \$\endgroup\$ – Lowjacker Apr 25 '11 at 13:50
  • \$\begingroup\$ I can also drop the !L&& guard on setting L, the location in the maze of the '@'. \$\endgroup\$ – Jonathan Watmough Apr 25 '11 at 14:25
4
\$\begingroup\$

Python, 339 chars

import sys
M=list(sys.stdin.read())
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:

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

###*###################
###*        #     *** #
## *######### *****#* #
 # ************#####* #
 ###############   #@##
\$\endgroup\$
  • \$\begingroup\$ Why all the additions and subtractions by N? \$\endgroup\$ – Lowjacker Apr 25 '11 at 12:05
  • \$\begingroup\$ It prevents the indexing D[i+j] in line 10 from going negative. And D[e+j] in line 12. \$\endgroup\$ – Keith Randall Apr 25 '11 at 14:45
1
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ I'm getting a * on the bottom-right corner, on the first test case (python 2.6.1). Any thoughts? \$\endgroup\$ – Lowjacker Apr 24 '11 at 23:15
  • \$\begingroup\$ @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 \$\endgroup\$ – Juan Apr 25 '11 at 0:01
  • \$\begingroup\$ 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 :) \$\endgroup\$ – Lowjacker Apr 25 '11 at 0:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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