Create a gist now

Instantly share code, notes, and snippets.

anonymous /maze.rb
Created Jan 13, 2010

class Maze
attr_reader :maze_array
def initialize(maze)
@maze_array = maze.split("\n") #create array of lines of the string! { |line| line.chars.to_a } #converts array to 2-d array of characters in maze
raise ArgumentError, "All lines must be of the same length", caller if !@maze_array.all? {|line| line.length == @maze_array[0].length}
@height = @maze_array.length #store the height of the maze in an instance variable
@width = @maze_array[0].length #store the length of the maze in an instance variable (assumes each line is the same length - should really test for this if being thorough)
@maze_array.each_with_index do |line, index1| #search array to find start and end of maze
line.each_with_index do |char, index2|
@start_row, @start_col = index1, index2 if char == "A" #start is denoted by A
@end_row, @end_col = index1, index2 if char == "B" #end is denoted by B
raise ArgumentError, "Maze must contain a start point \"A\"", caller if !@start_row
raise ArgumentError, "Maze must contain an end point \"B\"", caller if !@end_row
def solvable?
@solvable = false #This will be set to true if map is solvable
map = Marshal.load(Marshal.dump(@maze_array)) #Create a working duplicate of @maze_array
map.each { |line|! { |char| [char, false] }} #Add a 3rd dimension to array to account for locations having been visited already
explore(map, @start_row, @start_col) #explore function to determine if map is solvable
def steps
return 0 unless solvable? #If not solvable, don't bother trying!
map = Marshal.load(Marshal.dump(@maze_array)) #Create a working duplicate of @maze_array
node_list = []
#Step 1. Create an array of all coordinates on the map that will function as nodes for shortest path search (node_list)
#A coordinate is a node if it contains "A" or "B", or is a " " that has at least 2 adjacent spaces " " on non-opposite sides
#i.e. is either a corner or an intersection
#Can just check for corners as all intersections will test positive with the corner test used here.
map.each_with_index do |line,index1|
line.each_with_index do |char,index2|
node = false
dirs = {up: false, down: false, left: false, right: false} #won't work with Ruby 1.8
if char == " "
up, down, left, right = up (map,index1,index2), down (map,index1,index2), left (map,index1,index2), right (map,index1,index2)
dirs[:up] = true if up[0]==" " or up[0]=="A" or up[0]=="B" if up
dirs[:down] = true if down[0]==" " or down[0]=="A" or down[0]=="B" if down
dirs[:left] = true if left[0]==" " or left[0]=="A" or left[0]=="B" if left
dirs[:right] = true if right[0]==" " or right[0]=="A" or right[0]=="B" if right
node = true if (dirs[:up] and dirs[:left]) or (dirs[:up] and dirs[:right]) or (dirs[:down] and dirs[:left]) or (dirs[:down] and dirs[:right])
node_list << [index1, index2] if char == "A" or char == "B" or node #Add co-ords of current position to node_list if it is indeed a node
#Step 2, create a hash linking each node to all other nodes that can be directly reached from that node with the distance between them
search_list = {}
node_list.each do |source|
potentials = {up: {}, down: {}, left: {}, right: {}}
#First find all nodes in the same row or column as current (source) node and store them in potentials hash (key is direction of nodes, value is hash of nodes/distances in that direction)
node_list.each do |target|
if distance = reachable?(source,target) #first, determine if target node is reachable from source node and collect these in potentials hash with direction as key
potentials[:up][target] = distance if source[0]>target[0]
potentials[:down][target] = distance if source[0]<target[0]
potentials[:left][target] = distance if source[1]>target[1]
potentials[:right][target] = distance if source[1]<target[1]
#next find only the nearest target node in each direction
short_list = []
potentials.each do |direction, nodes|
sorted_nodes = []
sorted_nodes = nodes.sort{|a,b| b[0][0] <=> a[0][0]} if direction == :up && nodes != {}
sorted_nodes = nodes.sort{|a,b| a[0][0] <=> b[0][0]} if direction == :down && nodes != {}
sorted_nodes = nodes.sort{|a,b| b[0][1] <=> a[0][1]} if direction == :left && nodes != {}
sorted_nodes = nodes.sort{|a,b| a[0][1] <=> b[0][1]} if direction == :right && nodes != {}
#potential nodes in each direction are sorted so nearest node is in position 0 of array
#If there is a node in this direction, add it to the short_list array
short_list << sorted_nodes[0] if sorted_nodes != []
#short_list is now an array of hashes, each has containing the node co-ordinates in an array as the key, and the distance to that node as the value
#Now, add these to the search_list hash for the current source node
short_list.each do |value|
if search_list.has_key?(source)
search_list[source][value[0]] = value[1]
search_list[source] = {value[0] => value[1]}
#search_list now contains a hash containing all nodes in map as keys and a hash of all nodes reachable
#from that node, along with the distance to that node, as the hash value
#Step 3, determine length of shortest path between A and B using Dijkstra algorithm
#Implementation heavily borrowed from RPCFN#3 answer provided by Valério Farias
distance = {}
node_list.each {|x| distance[x] = 1.0/0}
distance[[@start_row,@start_col]] = 0
while (!node_list.empty?)
smallest = nil
node_list.each do |min|
smallest = min if (!smallest) or (distance[min] and distance[min] < distance[smallest])
break if distance[smallest] == 1.0/0
break if smallest[0] == @end_row && smallest[1] == @end_col #Shortest path to "B" has been found so can stop execution
node_list -= [smallest]
search_list[smallest].each do |node,dist|
alt = distance[smallest] + dist
distance[node] = alt if alt < distance[node]
def explore(map,row,col)
#explore recursively searches through map. Given a starting row/col, will sequentially look in each direction.
#If the map square in that direction is a space, explore will call itself to continue exploration from the new map square
#Map if marked solvable if the end square is encountered.
#This method could possibly be a little bit DRYer
#look left
if left = left(map,row,col) #Get character in map to left up current row/col (evaluates false if off the map)
if left[0] == " " && left[1] == false #Test if character to the left is a previously unvisited space
map[row][col-1][1] = true #If so, mark that space as visited
explore(map,row,col-1) #and iteratively explore that space
@solvable = true if left[0] == "B" #Declare the map solvable if the space to the left of the current row/col is the end character
#look right
if right = right(map,row,col)
if right[0] == " " && right[1] == false
map[row][col+1][1] = true
@solvable = true if right[0] == "B"
#look up
if up = up(map,row,col)
if up[0] == " " && up[1] == false
map[row-1][col][1] = true
@solvable = true if up[0] == "B"
#look down
if down = down(map,row,col)
if down[0] == " " && down[1] == false
map[row+1][col][1] = true
@solvable = true if down[0] == "B"
def up(map,row,col) #returns the 3rd dimension of array for map location up from row and col
return false if row == 0 #at top of map so nothing up
def down(map,row,col)
return false if row == @height-1
def left(map,row,col)
return false if col == 0
def right(map,row,col)
return false if col == @width-1
def reachable?(source,target) #Check if there is an uninterrupted line between 2 points and return distance between them
if source[0] == target[0] #Source and target are in the same row
distance = (source[1]-target[1]).abs
return 1 if distance == 1 #Source and target are adjacent so must be connected
flag = true
source[1] < target[1] ? (s, t = source[1], target[1]) : (s, t = target[1], source[1])
(s+1...t).to_a.each { |col| flag = false if @maze_array[source[0]][col] == "#" } #Unset flag if any point on the path between source and target is blocked
return (flag ? distance : false)
if source[1] == target[1] #Source and target are in the same column
distance = (source[0]-target[0]).abs
return 1 if distance == 1 #Source and target are adjacent so must be connected
flag = true
source[0] < target[0] ? (s, t = source[0], target[0]) : (s, t = target[0], source[0])
(s+1...t).to_a.each { |row| flag = false if @maze_array[row][source[1]] == "#" } #Unset flag if any point on the path between source and target is blocked
return (flag ? distance : false)
false #Source and target are in different rows and columns so return false
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment