secret
Created — forked from Yok38/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 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
# 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
test_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 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
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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.