RLGGHC / oleksandrmanzyuk.rb secret

Created December 28, 2009 — forked from manzyuk/oleksandrmanzyuk.rb

# 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