-
-
Save manzyuk/4bec4e877f8024746a29 to your computer and use it in GitHub Desktop.
solution to Ruby quiz
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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