IndianGuru / maze.rb secret
Created — forked from Yok38/maze.rb

Embed URL

HTTPS clone URL

SSH clone URL

You can clone with HTTPS or SSH.

Download Gist
View maze.rb
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
View maze.rb
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.