public
Last active — forked from jamesdaniels/maze.rb

  • Download Gist
maze.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
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
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164
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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.