Create a gist now

Instantly share code, notes, and snippets.

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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment