maze.rb

class String
  alias_method :is_a, :==
  alias_method :is_an, :==
end

class Maze
  
  NAVIGABLE   = ' '
  WALL        = '#'
  POINT_A     = 'A'
  POINT_B     = 'B'
  
  def initialize(input)
    # builds a multidimensional representation of the input string
    @labyrinth = input.split("\n").map { |line| line.scan(/./) }

    # finds the POINT_A coordinates
    line = @labyrinth.detect { |l| l.include?(POINT_A)}
    y = @labyrinth.index(line)
    x = line.index(POINT_A)
    @start_point = [y, x]
  end
  
  def solvable?(position = init_steps_taken_and_return_first, &block)
    # checks wheter we found the target position
    if at(position).is_an(POINT_B)
      # avoids unnecesary iterations when we only want to know if a maze is solvable
      return true unless block_given?
      #yields the amount of steps for this particular solution
      steps_amount = caller.grep(/solvable/).length / 2
      yield steps_amount
    end
    
    # "Steps"
    #   can only be taken up, down, left or right
    #   cannot be taken throught walls :-)
    #   shouldn't be taken more than once
    y, x = *position
    steps_available = [             [y - 1, x],
                       [ y, x - 1],             [ y, x + 1],
                                    [y + 1, x]               ]
    steps_available.reject! do |p|
      at(p).is_a(WALL) || @steps_taken.include?(p)
    end
    @steps_taken.concat(steps_available)
    
    # recursively looks for the POINT_B from each step available
    steps_available.any? { |step| solvable?(step, &block) }
  end
  
  def steps
    amounts = []
    solvable? do |amount|
      amounts << amount
    end
    amounts.min || 0
  end
  
  private
  
  def at(position)
    y, x = *position
    @labyrinth[y][x]
  end
  
  def init_steps_taken_and_return_first
    @steps_taken = [ @start_point ]
    @start_point
  end

end

maze_test.rb

require 'test/unit'
require 'maze'

MAZE1 = %{#####################################
# #   #     #A        #     #       #
# # # # # # ####### # ### # ####### #
# # #   # #         #     # #       #
# ##### # ################# # #######
#     # #       #   #     # #   #   #
##### ##### ### ### # ### # # # # # #
#   #     #   # #   #  B# # # #   # #
# # ##### ##### # # ### # # ####### #
# #     # #   # # #   # # # #       #
# ### ### # # # # ##### # # # ##### #
#   #       #   #       #     #     #
#####################################}
# Maze 1 should SUCCEED

MAZE2 = %{#####################################
# #       #             #     #     #
# ### ### # ########### ### # ##### #
# #   # #   #   #   #   #   #       #
# # ###A##### # # # # ### ###########
#   #   #     #   # # #   #         #
####### # ### ####### # ### ####### #
#       # #   #       # #       #   #
# ####### # # # ####### # ##### # # #
#       # # # #   #       #   # # # #
# ##### # # ##### ######### # ### # #
#     #   #                 #     #B#
#####################################}
# Maze 2 should SUCCEED

MAZE3 = %{#####################################
# #   #           #                 #
# ### # ####### # # # ############# #
#   #   #     # #   # #     #     # #
### ##### ### ####### # ##### ### # #
# #       # #  A  #   #       #   # #
# ######### ##### # ####### ### ### #
#               ###       # # # #   #
# ### ### ####### ####### # # # # ###
# # # #   #     #B#   #   # # #   # #
# # # ##### ### # # # # ### # ##### #
#   #         #     #   #           #
#####################################}
# Maze 3 should FAIL

class MazeTest < Test::Unit::TestCase
  def test_good_mazes
    assert_equal true, Maze.new(MAZE1).solvable?
    assert_equal true, Maze.new(MAZE2).solvable?
  end

  def test_bad_mazes
    assert_equal false, Maze.new(MAZE3).solvable?
  end

  def test_maze_steps
    assert_equal 44, Maze.new(MAZE1).steps
    assert_equal 75, Maze.new(MAZE2).steps
    assert_equal 0, Maze.new(MAZE3).steps
  end
end