maze.rb

class Maze
	
	Cardinals = Proc.new{|(x,y)| [[x-1,y],[x,y+1],[x+1,y],[x,y-1]].select{|c| c.min >= 0}}
	MazeSeperator, MazeStart, MazeWall, MazeEnd, MazeOOB = "\n", 'A', '#', 'B', nil
	Infinity = 1.0/0
	X, Y = 0, 1
	
	def initialize(maze)
		raise ArgumentError, 'No end point'          unless maze.include? MazeEnd
		raise ArgumentError, 'No start point'        unless maze.include? MazeStart
		raise ArgumentError, 'Multiple start points' unless maze.count(MazeStart) == 1
		raise ArgumentError, 'Multiple end points'   unless maze.count(MazeEnd)   == 1
		@maze = maze.split(MazeSeperator).map{|row| row.each_char.to_a} # Make a 2-d array of characters, [Y][X] (I could transpose)
		(@start = (map = @maze.map{|a| a.index MazeStart}).compact) << map.index(@start.first) # [X,Y]
	end
	
	def solvable?
		@solvable ||= (solution(false) != Infinity) # solution(false) doesn't continue searching for the shortest route, it's happy with just one solution
	end
	
	def steps
		@steps ||= (solvable? && solution(true) || 0) # look for the shortest solution, if solvable? then memoize
	end
	
private

	def solution(shortest_path, path = [@start])
		# Check to see where we are, being mindful of "out of bounds"
		case (point = path.last) && (@maze[point[Y]][point[X]] rescue MazeOOB)
		when MazeWall, MazeOOB
			Infinity    # If we have hit a wall or gone out of bounds, no good can come of it
		when MazeEnd
			path.size-1 # Don't count the first node
		else
			if path.count(point) > 1
				Infinity # If we've doubled back, we are done for
			else
				# While adding some complexity, breaking out when a solution is found (if not looking for the shortest route) 
				# makes testing for solvability quicker
				Cardinals.call(point).inject([]) do |collection, new_location|
					(shortest_path || collection.empty? || collection.min == Infinity) &&  # If we haven't already found a solution, or we are looking for the shortest route
						(collection << solution(shortest_path, path.dup << new_location)) || #   Use the force Luke
					collection                                                             # Else GTFO
				end.min # Grab the shortest route
			end
		end
	end

end

maze_spec.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

SOLVABLE = {
	:one   => 'AB',
	:two   => 'A B',
	:three => 'A  B',
	:four  => 'A   B',
	:five  => 'A    B',
	:six   => 'A     B',
	:simple => %{####
# A#
# ##
# B#
####},
	:less_simple => %{####
#A #
## #
#  #
# ##
# B#
####},
	:shortest => %{#####
#B  #
# # #
#A# #
# # #
# # #
#   #
#####}
}

FAILURE = {
	:no_start => 'B',
	:no_end   => 'A',
	:multiple_end => 'ABB',
	:multiple_start => 'AAB'
}

UNSOLVABLE = {
	:stop_oob => 'A#B',
	:fool_bad_array_implementation => %{ # 
A#B
 # },
	:stop_wall => %{###
#A#
###
B  },
	:stop_loop => %{#####
#   #
# A #
#   #
#####
#B   }
}

class MazeTest < Test::Unit::TestCase
	def test_good_mazes
		SOLVABLE.keys.each {|key| assert_equal true, Maze.new(SOLVABLE[key]).solvable?}
		assert_equal true, Maze.new(MAZE1).solvable?
		assert_equal true, Maze.new(MAZE2).solvable?
	end

	def test_bad_mazes
		UNSOLVABLE.keys.each {|key|	assert_equal false, Maze.new(UNSOLVABLE[key]).solvable?}
		assert_equal false, Maze.new(MAZE3).solvable?
	end

	def test_failure
		assert_match(/No start point/,        assert_raise(ArgumentError) {Maze.new(FAILURE[:no_start])       }.message)
		assert_match(/No end point/,          assert_raise(ArgumentError) {Maze.new(FAILURE[:no_end])         }.message)
		assert_match(/Multiple end points/,   assert_raise(ArgumentError) {Maze.new(FAILURE[:multiple_end])   }.message)
		assert_match(/Multiple start points/, assert_raise(ArgumentError) {Maze.new(FAILURE[:multiple_start]) }.message)
	end
	
	def test_start_point
		assert_equal [0, 0], Maze.new(SOLVABLE[:one]  ).instance_eval('@start')
		assert_equal [0, 0], Maze.new(SOLVABLE[:two]  ).instance_eval('@start')
		assert_equal [0, 0], Maze.new(SOLVABLE[:three]).instance_eval('@start')
		assert_equal [0, 0], Maze.new(SOLVABLE[:four] ).instance_eval('@start')
		assert_equal [0, 0], Maze.new(SOLVABLE[:five] ).instance_eval('@start')
		assert_equal [0, 0], Maze.new(SOLVABLE[:six]  ).instance_eval('@start')
		assert_equal [2, 1], Maze.new(SOLVABLE[:simple]).instance_eval('@start')
		assert_equal [1, 1], Maze.new(SOLVABLE[:less_simple]).instance_eval('@start')
		assert_equal [1, 3], Maze.new(SOLVABLE[:shortest]   ).instance_eval('@start')
		assert_equal [13, 1], Maze.new(MAZE1).instance_eval('@start')
		assert_equal [7, 4],  Maze.new(MAZE2).instance_eval('@start')
		assert_equal [15, 5], Maze.new(MAZE3).instance_eval('@start')
	end
	
	def test_cardinals
		assert_equal [[0, 1], [1, 2], [2, 1], [1, 0]], Maze::Cardinals.call([1,1])
		assert_equal [[0, 1], [1, 0]],                 Maze::Cardinals.call([0,0])
	end
	
	def test_recursive_stop_cases
		maze = Maze.new(SOLVABLE[:simple])
		assert_equal Maze::Infinity, maze.send(:solution, false, [[-1,-1]])     # Testing out of bounds
		assert_equal Maze::Infinity, maze.send(:solution, false, [[0,0]])       # Testing wall hit
		assert_equal Maze::Infinity, maze.send(:solution, false, [[1,1],[1,1]]) # Testing circling
		assert_equal 0,              maze.send(:solution, false, [[2,3]])       # Testing end of maze
	end

	def test_maze_steps
		assert_equal 1,  Maze.new(SOLVABLE[:one]).steps
		assert_equal 2,  Maze.new(SOLVABLE[:two]).steps
		assert_equal 3,  Maze.new(SOLVABLE[:three]).steps
		assert_equal 4,  Maze.new(SOLVABLE[:four]).steps
		assert_equal 5,  Maze.new(SOLVABLE[:five]).steps
		assert_equal 6,  Maze.new(SOLVABLE[:six]).steps
		assert_equal 4,  Maze.new(SOLVABLE[:simple]).steps
		assert_equal 7,  Maze.new(SOLVABLE[:less_simple]).steps
		assert_equal 2,  Maze.new(SOLVABLE[:shortest]).steps # Test the shortest path
		assert_equal 12, Maze.new(SOLVABLE[:shortest]).send(:solution, false) # Test the long route
		assert_equal 44, Maze.new(MAZE1).steps
		assert_equal 75, Maze.new(MAZE2).steps
		assert_equal 0,  Maze.new(MAZE3).steps
	end
end