Skip to content
Create a gist now

Instantly share code, notes, and snippets.

anonymous /paulmckibbin.rb secret
Created Jan 2, 2010

Breadth first search of a maze for the exit for RPCFN quiz 5
class Maze
def initialize(map)
def build
def walk
unless start_pos.nil? || !(@m_aMap.join=~/B/) #unless no start or end
width=@m_aMap.collect {|x| x.size}.max #should have boundary wall anyway
queue=[[start_pos/width,start_pos%width,0]] #initialize stack with start x,y and depth
while !queue.empty?
visited[hash_index].nil? ? visited[hash_index]=true : next
case @m_aMap[x][y].chr
when ' ','A'
queue.push([x,y-1,depth+1]) if y>0 #checks are redundant if boundary wall completely
queue.push([x,y+1,depth+1]) if y<width #surrounds the maze, but add to flexibility if there
queue.push([x-1,y,depth+1]) if x>0 #is a start position on the boundary.
queue.push([x+1,y,depth+1]) if x<height
when 'B'
return [true,depth]
return [false,0] #fail if we got to here
def solvable?
@m_bSolvable || build
def steps
solvable? ? @m_iPathLength : 0
#There were lots of choices for this particular test, but I thought that I'd go for brevity and meeting
#the stated requirement rather than leave in all of the extra code I had (printing the final solution, by
#storing a parent in the visited and passing it to the stack, etc.) The code first converts the map to
#an array of strings and finds the start position. From this it then adds in all of the boxes bounding
#this to a stack and examines them in turn, adding other bounding squares to the stack of places to
#be examined as it goes on. If a cell has been previously visited, or doesn't contain a path, it is
#skipped and the next one in the stack is examined. In addition to the cell location, the distance from
#the starting square is passed to the stack, which means, when the final cell is reached, this variable
#(called depth) contains the shortest distance from the start to the end. The fail condition happens
#when there are no start or end squares, or when all possibilities have been traced from the start
#and have resulted in only dead ends without reaching the end point.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.