Instantly share code, notes, and snippets.

# IndianGuru/maze.rb forked from jamesdaniels/maze.rb Created Jan 17, 2010

What would you like to do?
 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
 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