public
Last active — forked from /maze.rb

  • Download Gist
maze.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190
class Maze
attr_reader :maze_array
def initialize(maze)
@maze_array = maze.split("\n") #create array of lines of the string
@maze_array.map! { |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
end
end
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
end
 
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| line.map! { |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
@solvable
end
 
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])
end
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
end
end
#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]
end
end
#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 != []
end
#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]
else
search_list[source] = {value[0] => value[1]}
end
end
end
#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])
end
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]
end
end
distance[[@end_row,@end_col]]
end
 
#protected
 
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
end
@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
end
#look right
if right = right(map,row,col)
if right[0] == " " && right[1] == false
map[row][col+1][1] = true
explore(map,row,col+1)
end
@solvable = true if right[0] == "B"
end
#look up
if up = up(map,row,col)
if up[0] == " " && up[1] == false
map[row-1][col][1] = true
explore(map,row-1,col)
end
@solvable = true if up[0] == "B"
end
#look down
if down = down(map,row,col)
if down[0] == " " && down[1] == false
map[row+1][col][1] = true
explore(map,row+1,col)
end
@solvable = true if down[0] == "B"
end
end
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
map[row-1][col]
end
def down(map,row,col)
return false if row == @height-1
map[row+1][col]
end
def left(map,row,col)
return false if col == 0
map[row][col-1]
end
def right(map,row,col)
return false if col == @width-1
map[row][col+1]
end
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)
end
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)
end
false #Source and target are in different rows and columns so return false
end
end

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.