Code Golf: Solve the Maze

Question

Here's an interesting problem to solve in minimal amounts of code. I expect recursive solutions to be the most popular.

We have a maze, which is defined as a symbol map, where = is a wall, space is a path, + is your starting point, and # is your ending point. Incredibly simple example:

 ==== + = = == = # ==== 

Can you write a program to find the shortest way to solve the maze in this style, as little code as possible?

Bonus points if they work for all input labyrinths, for example, those that have a path that crosses themselves or with a huge number of branches. The program should be able to work on large mazes (for example, 1024x1024 - 1 MB), and also how you go through the maze in the program does not matter.

The “player” can move diagonally. The input labyrinth will never have a diagonal passage, so your basic set of movements will be up, down, left, right. The diagonal movement just looked a bit into the future to determine if it could be combined up / down and left / right.

The output should be the labyrinth itself with the shortest path indicated by the asterisk ( * ).

Answer 1

Python

387 Characters

Accepts input from stdin.

 import sys m,n,p=sys.stdin.readlines(),[],'+' R=lambda m:[r.replace(p,'*')for r in m] while'#'in`m`:n+=[R(m)[:r]+[R(m)[r][:c]+p+R(m)[r][c+1:]]+R(m)[r+1:]for r,c in[(r,c)for r,c in[map(sum,zip((m.index(filter(lambda i:p in i,m)[0]),[w.find(p)for w in m if p in w][0]),P))for P in zip((-1,0,1,0),(0,1,0,-1))]if 0<=r<len(m)and 0<=c<len(m[0])and m[r][c]in'# ']];m=n.pop(0) print''.join(R(m)) 

Answer 2

It works for any (fixed size) maze with a minimum number of processor cycles (with a sufficiently large BFG2000). The size of the source does not matter, since the compiler is incredibly efficient.

 while curr.x != target.x and curr.y != target.y: case: target.x > curr.x : dx = 1 target.x < curr.x : dx = -1 else : dx = 0 case: target.y > curr.y : dy = 1 target.y < curr.y : dy = -1 else : dy = 0 if cell[curr.x+dx,curr.y+dy] == wall: destroy cell[curr.x+dx,curr.y+dy] with patented BFG2000 gun. curr.x += dx curr.y += dy survey shattered landscape 

Answer 3

F #, not very short (72 non-empty lines), but readable. I slightly modified / honed the specification; I assume that the original labyrinth is a rectangle completely surrounded by walls, I use different characters (which do not damage my eyes), I allow orthogonal movements (not diagonal). I tried only one sample of the maze. Except for the error about the x and y pointers, this worked for the first time, so I expect it to be correct (I did nothing to check it, except for the eyeball, the solution is on the same sample that I gave it).

 open System [<Literal>] let WALL = '#' [<Literal>] let OPEN = ' ' [<Literal>] let START = '^' [<Literal>] let END = '$' [<Literal>] let WALK = '.' let sampleMaze = @"############### # # # # # ^# # # ### # # # # # # # # # # # # ############ # # $ # ###############" let lines = sampleMaze.Split([|'\r';'\n'|], StringSplitOptions.RemoveEmptyEntries) let width = lines |> Array.map (fun l -> l.Length) |> Array.max let height = lines.Length type BestInfo = (int * int) list * int // path to here, num steps let bestPathToHere : BestInfo option [,] = Array2D.create width height None let mutable startX = 0 let mutable startY = 0 for x in 0..width-1 do for y in 0..height-1 do if lines.[y].[x] = START then startX <- x startY <- y bestPathToHere.[startX,startY] <- Some([],0) let q = new System.Collections.Generic.Queue<_>() q.Enqueue((startX,startY)) let StepTo newX newY (path,count) = match lines.[newY].[newX] with | WALL -> () | OPEN | START | END -> match bestPathToHere.[newX,newY] with | None -> bestPathToHere.[newX,newY] <- Some((newX,newY)::path,count+1) q.Enqueue((newX,newY)) | Some(_,oldCount) when oldCount > count+1 -> bestPathToHere.[newX,newY] <- Some((newX,newY)::path,count+1) q.Enqueue((newX,newY)) | _ -> () | c -> failwith "unexpected maze char: '%c'" c while not(q.Count = 0) do let x,y = q.Dequeue() let (Some(path,count)) = bestPathToHere.[x,y] StepTo (x+1) (y) (path,count) StepTo (x) (y+1) (path,count) StepTo (x-1) (y) (path,count) StepTo (x) (y-1) (path,count) let mutable endX = 0 let mutable endY = 0 for x in 0..width-1 do for y in 0..height-1 do if lines.[y].[x] = END then endX <- x endY <- y printfn "Original maze:" printfn "%s" sampleMaze let bestPath, bestCount = bestPathToHere.[endX,endY].Value printfn "The best path takes %d steps." bestCount let resultMaze = Array2D.init width height (fun xy -> lines.[y].[x]) bestPath |> List.tl |> List.iter (fun (x,y) -> resultMaze.[x,y] <- WALK) for y in 0..height-1 do for x in 0..width-1 do printf "%c" resultMaze.[x,y] printfn "" //Output: //Original maze: //############### //# # # # //# ^# # # ### # //# # # # # # # //# # # # //############ # //# $ # //############### //The best path takes 27 steps. //############### //# # #....... # //# ^# #.# ###. # //# .# #.# # #. # //# .....# #. # //############. # //# $....... # //############### 

Answer 4

I did such things for an interview once (it was a challenge before the interview)

I managed to get it to work to some degree of success, and this is an interesting task.