README

Ruby Programming Challenge For Newbies: Mazes (#5)

Author:    René Scheibe
Email:     rene.scheibe@gmail.com
Date:      January 7, 2010
Runs with: Ruby 1.9.1, JRuby 1.4
Algorithm: BFS (breadth-first search)

The implementation is based on the ordered Hash of Ruby 1.9.
It also assumes that the "each" method takes notice of new elements that are added during the enumeration.

maze.rb

class Maze
  def initialize maze_as_string
    @input_string = maze_as_string
    @input_string.extend(MazeString)
    @waypoints = @input_string.extract_waypoints
  end

  def solvable?
    steps != 0
  end

  def steps
    return 0 unless valid?

    waypoints = {@waypoints.start_position => 0}

    waypoints.each do |current_waypoint, path_length|
      return path_length if current_waypoint == @waypoints.end_position
      new_waypoints = spot_new_waypoints(current_waypoint, waypoints)
      new_waypoints.each{ |waypoint| waypoints[waypoint] = path_length + 1 }
    end

    0
  end

  protected
  def valid?
    @input_string.valid?
  end

  def spot_new_waypoints current_waypoint, visited_waypoints
    row, col = current_waypoint
    candidate_waypoints = [[row-1, col], [row+1, col], [row, col-1], [row, col+1]]
    candidate_waypoints.select{ |waypoint| @waypoints[waypoint] && !visited_waypoints[waypoint] }
  end
end

module MazeString
  SYMBOLS = {:wall => '#', :space => ' ', :start => 'A', :end => 'B'}

  def valid?
    has_valid_symbols? and has_one_start? and has_one_end?
  end

  def extract_waypoints
    waypoints = WaypointStore.new
    self.split($/).each_with_index do |line, row|
      line.split('').each_with_index do |char, col|
        waypoints[[row, col]] = char unless char == SYMBOLS[:wall]
      end
    end
    waypoints
  end

  protected
  def has_valid_symbols?
    (self =~ /^[#{SYMBOLS.values.join}]*$/) != nil
  end

  def has_one_start?
    self.count(SYMBOLS[:start]) == 1
  end

  def has_one_end?
    self.count(SYMBOLS[:end]) == 1
  end
end

class WaypointStore < Hash
  def start_position
    @start_position ||= invert[MazeString::SYMBOLS[:start]]
  end

  def end_position
    @end_position ||= invert[MazeString::SYMBOLS[:end]]
  end
end

tests.rb

require 'test/unit'
require 'maze'

class MazeUnitTest < Test::Unit::TestCase
  Maze.send :public, *Maze.protected_instance_methods

  def test_input_symbols
    assert_equal true,  Maze.new("# A # B").valid?
    assert_equal true,  Maze.new("# A \nB").valid?
    assert_equal false, Maze.new("# A + B").valid?
  end

  def test_start_count
    assert_equal true,  Maze.new("B A ").valid?
    assert_equal false, Maze.new("B   ").valid?
    assert_equal false, Maze.new("B AA").valid?
  end

  def test_end_count
    assert_equal true,  Maze.new("A B ").valid?
    assert_equal false, Maze.new("A   ").valid?
    assert_equal false, Maze.new("A BB").valid?
  end

  def test_extract_waypoints
    actual_waypoints = extract_waypoints("# A\n# B")
    expected_waypoints = {[0, 1] => ' ', [0, 2] => 'A', [1, 1] => ' ', [1, 2] => 'B'}
    assert_equal expected_waypoints, actual_waypoints
  end

  def test_waypoint_spotting
    maze = Maze.new("# A\n# B")
    actual_waypoints = maze.spot_new_waypoints([0, 1], {[0, 2] => 0, [0, 1] => 1})
    expected_waypoints = [[1, 1]]
    assert_equal expected_waypoints, actual_waypoints
  end

  def test_start_position
    assert_equal [0, 2], extract_waypoints("##A\nB##").start_position
    assert_equal nil,    extract_waypoints("").start_position
  end

  def test_end_position
    assert_equal [1, 0], extract_waypoints("##A\nB##").end_position
    assert_equal nil,    extract_waypoints("").end_position
  end

  def test_solvability
    assert_equal false, Maze.new("A").solvable?
    assert_equal true,  Maze.new("#A \n#  \n  B").solvable?
  end

  def test_steps
    assert_equal 0, Maze.new("").steps
    assert_equal 0, Maze.new("A").steps
    assert_equal 0, Maze.new("A#B").steps
    assert_equal 1, Maze.new("AB").steps
    assert_equal 2, Maze.new("#A \n# B").steps
  end

  def extract_waypoints maze_string
    maze_string.extend(MazeString)
    maze_string.extract_waypoints
  end
end