# Curiously, if you type 1.0 / 0.0 into the irb prompt, ruby returns | |
# Infinity; however if you type in Infinity directly, ruby complains | |
# about an uninitialized constant. Define it here. | |
Infinity = 1.0 / 0.0 | |
# Finding the least number of steps one would have to take within the | |
# maze to get from point A to point B can be interpreted as a problem | |
# of finding the distance between 2 vertices in a graph. We abstract | |
# it in a class Graph. A graph consists of an array of vertices, and | |
# for each vertex an array of vertices adjacent to it. | |
class Graph | |
# `vertices' is an array, `adjacent' is a hash of arrays. | |
def initialize(vertices, adjacent) | |
@vertices, @adjacent = vertices, adjacent | |
end | |
# Dijkstra's algorithm for finding the distance from a given vertex | |
# to every other vertex. Returns a hash of distances. | |
# | |
# See http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm. | |
def distances_from(source) | |
# `d' is a hash of distances to each vertex from the source. | |
d = {} | |
# Initially, set the distance to `Infinity' for each vertex... | |
@vertices.each {|vertex| d[vertex] = Infinity } | |
# ... except that the distance from the source to itself is 0. | |
d[source] = 0 | |
# `unvisited' maintains an array of unvisited vertices. Initially | |
# it contains all the vertices of the graph. | |
unvisited = @vertices | |
# The main loop. | |
until unvisited.empty? | |
# Choose a vertex with the smallest distance to the source. | |
current = unvisited.min { |v1, v2| d[v1] <=> d[v2] } | |
# If the distance from this vertex to the source is Infinity, | |
# then all remaining unvisited vertices are inaccessible from | |
# the source, hence return. | |
return d if d[current] == Infinity | |
# Otherwise, mark the current vertex as visited. | |
unvisited.delete(current) | |
# Relax each vertex adjacent to the current vertex. | |
@adjacent[current].each do |vertex| | |
if d[vertex] > d[current]+1 then d[vertex] = d[current]+1 end | |
end | |
end | |
# Finally, return `d'. | |
d | |
end | |
end | |
# Our Maze class is a subclass of Graph: @vertices is an array of all | |
# the cells in the maze (which we enumerate first), and for each cell | |
# c the value of @adjacent[c] is an array of (<= 4) adjacent cells. | |
class Maze < Graph | |
# Parse a maze (given as a string) into a graph. | |
def initialize(string) | |
@vertices, @adjacent, index = [], {}, 0 | |
# Split the given string into separate lines. Map over each char | |
# in each line, enumerate all the chars different from #, collect | |
# their indices into the @vertices array, and save the indices of | |
# the points A and B. | |
grid = string.split("\n").map do |line| | |
line.chars.map do |char| | |
if char == "#" then "#" | |
else | |
index += 1 | |
@vertices << index | |
@a = index if char == "A" | |
@b = index if char == "B" | |
index | |
end | |
end | |
end | |
# `grid' is an array of arrays, which we visualize as a matrix. | |
# Each element of it is either a number, which denotes a cell, | |
# or the character "#", which denotes a wall. Iterate over all | |
# the cells and for each cell find the cells adjacent to it. | |
# | |
# We assume that the maze is rectangular and is surrounded by a | |
# solid wall. Otherwise more careful analysis of edge cases is | |
# necessary. | |
grid.each_with_index do |line, row| | |
line.each_with_index do |cell, col| | |
unless cell == "#" | |
@adjacent[cell] = [grid[row-1][col], | |
grid[row][col-1], | |
grid[row+1][col], | |
grid[row][col+1]].reject { |cell| cell == "#" } | |
end | |
end | |
end | |
end | |
def solvable? | |
# The maze is solvable if the distance from A to B is finite. | |
distances_from(@a)[@b] < Infinity | |
end | |
def steps | |
# Slightly inconsistently, according to the test suite Maze#steps | |
# must return 0 if the maze is unsolvable. | |
d = distances_from(@a)[@b] | |
if d < Infinity then d else 0 end | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment