secret
Created — forked from manzyuk/oleksandrmanzyuk.rb

  • Download Gist
oleksandrmanzyuk.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
# 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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.