Create a gist now

Instantly share code, notes, and snippets.

@IndianGuru /maze.rb Secret forked from Yok38/maze.rb
Created Jan 19, 2010

# cf. http://rubylearning.com/blog/2009/12/27/rpcfn-mazes-5/
class Coord
attr_accessor :x, :y
def initialize(x, y)
@x, @y = x, y
end
def +(coord)
return Coord.new(@x+coord.x, @y+coord.y)
end
end
WALL = '#'
FREE = ' '
STARTPOINT = 'A'
ENDPOINT = 'B'
INSPECTED = '*'
DIRECTIONS = {:No => Coord.new(0,-1), :We => Coord.new(-1,0), :So => Coord.new(0,1), :Ea => Coord.new(1,0)} # North, West, South, East
class Maze
attr_reader :maze
attr_accessor :solutions
def initialize(maze, display=false)
@display = display
@maze = maze.split(/\n/).collect{|line| line.split(//)} # @maze[line][column]
@solutions = []
Explorer.new(self, self.start_coord, []).explore
end
def start_coord
start_line = @maze.index(@maze.find{|line| line.include?(STARTPOINT)})
start_column = @maze[start_line].index(STARTPOINT)
return Coord.new(start_column, start_line) # Coord(x,y)
end
def to_s
if @display
sleep 0.05
(@maze.collect {|row| row.join(' ')} + ['-'*40]).join("\n")
end
end
def solvable?
not @solutions.empty?
end
def steps
@solutions.collect {|s| s.size}.min || 0
end
def [](coord)
@maze[coord.y][coord.x]
end
def []=(coord, value)
@maze[coord.y][coord.x] = value
end
end
class Explorer
def initialize(maze, coord, path)
@maze, @coord, @path = maze, coord, path
end
def explore
DIRECTIONS.each_pair do |direction, step_coord|
spot_coord = @coord+step_coord
case @maze[spot_coord]
when FREE
puts @maze
@path << direction
@maze[spot_coord] = INSPECTED
Explorer.new(@maze, spot_coord, @path).explore
@maze[spot_coord] = FREE
@path.pop
when ENDPOINT
@path << direction
@maze.solutions << @path.dup
return
end
end
return false
end
end
if __FILE__ == $0
MAZE4 = %{#####################################
# # # # # #
# ### ### # ########### ### # ##### #
# # # # # # # # # #
# # ###A##### # # # # ### ###########
# # # # # # # # #
####### # ### ####### # ### ####### #
# # # # # # # #
# ####### # # # ####### # ##### # # #
# # # # # # # # # #
# ##### # # ##### ######### # ### # #
# # # # #B#
#####################################}
m = Maze.new(MAZE4, true)
puts m.steps
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
MAZE4 = %{#####################################
# # # # # #
# ### ### # ########### ### # ##### #
# # # # # # # # # #
# # ###A##### # # # # ### ###########
# # # # # # # # #
####### # ### ####### # ### ####### #
# # # # # # # #
# ####### # # # ####### # ##### # # #
# # # # # # # # # #
# ##### # # ##### ######### # ### # #
# # # # #B#
#####################################}
# Maze 4 should provide TWO solutions
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
def test_maze_solutions
assert_equal 1, Maze.new(MAZE1).solutions.size
assert_equal 1, Maze.new(MAZE2).solutions.size
assert_equal 0, Maze.new(MAZE3).solutions.size
assert_equal 2, Maze.new(MAZE4).solutions.size
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment