public
Last active — forked from Gimi/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 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 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191
# RPCFN #5: Mazes
# @author 梁智敏(Gimi Liang) [gimi.liang at gamil dot com]
# @date 2009/12/29
class Maze
START_POINT_MARKER = 'A'.freeze
END_POINT_MARKER = 'B'.freeze
INFINITE = (1.0 / 0.0).freeze
 
class Cell
WALL = '#'.unpack('c').first.freeze
 
attr_reader :maze, :x, :y, :type
 
def initialize(maze, x, y)
@maze = maze
@x, @y = x, y
@type = maze.at(x, y)
end
 
def east; @east ||= maze.cell(self.x + 1, self.y) end
 
def south; @south ||= maze.cell(self.x, self.y + 1) end
 
def west; @west ||= maze.cell(self.x - 1, self.y) end
 
def north; @north ||= maze.cell(self.x, self.y - 1) end
 
# returns all neighbors of this cell.
# @param [Boolean] navigable_only if it's true, only returns neighbors that are navigable.
def neighbors(navigable_only = true)
[:east, :south, :west, :north].inject([]) do |neighbors, direction|
(cell = send direction) &&
(!navigable_only || cell.navigable?) &&
neighbors << cell || neighbors
end
end
 
def navigable?
type != WALL
end
 
def eql?(other)
other.is_a?(Cell) &&
maze == other.maze &&
x == other.x &&
y == other.y
end
 
def to_s
"(#{x}, #{y})"
end
 
alias inspect to_s
end # Cell
 
# Create a maze with a maze string.
def initialize(maze_string)
@cells = {}
parse maze_string
end
 
def solvable?
steps != 0
end
 
def steps
@steps ||= (step = process) == INFINITE ? 0 : step
end
 
def cell(x, y)
@cells.has_key?([x, y]) ? @cells[[x, y]] :
@cells[[x, y]] = exists?(x, y) ? Cell.new(self, x, y) : nil
end
 
# Returns the value of a cell by its axes.
def at(x, y)
x < 0 || y < 0 ? nil : (row = @maze[y]) && row[x]
end
 
def exists?(x, y)
not at(x, y).nil?
end
 
private
# Turns a maze string into a 2-dimension array and marks the start point and the end point.
def parse(maze_string)
y = -1
start_axes = end_axes = nil
@maze = maze_string.each_line.map do |line|
y += 1
(x = line.index(START_POINT_MARKER)) && start_axes = [x, y]
(x = line.index(END_POINT_MARKER)) && end_axes = [x, y]
line.unpack 'c*'
end
@start_point = cell *start_axes if start_axes
@end_point = cell *end_axes if end_axes
end
 
# Figure out the least steps from start point to end point using Dijkstra's algorithm.
# @return [Integer] steps if the maze is unsolvable, return Infinite.
def process
return INFINITE unless @start_point && @end_point
sources = [@start_point]
next_sources = @start_point.neighbors
(steps = Hash.new { |h, k| h[k] = INFINITE })[@start_point] = 0
until next_sources.empty?
source = next_sources.first
next_sources.concat(
source.neighbors.each do |neighbor|
step = steps[neighbor] + 1
steps[source] = step if step < steps[source]
end
)
return steps[@end_point] if source == @end_point
sources << source
next_sources -= sources
end
steps[@end_point]
end
 
end
 
# --- TESTS -------------------------------------------------------------------
if $0 == __FILE__
require 'test/unit'
 
MAZE1 = <<MAZE_1 # should SUCCEED
#####################################
# # # #A # # #
# # # # # # ####### # ### # ####### #
# # # # # # # # #
# ##### # ################# # #######
# # # # # # # # #
##### ##### ### ### # ### # # # # # #
# # # # # # B# # # # # #
# # ##### ##### # # ### # # ####### #
# # # # # # # # # # # #
# ### ### # # # # ##### # # # ##### #
# # # # # # #
#####################################
MAZE_1
 
MAZE2 = <<MAZE_2 # should SUCCEED
#####################################
# # # # # #
# ### ### # ########### ### # ##### #
# # # # # # # # # #
# # ###A##### # # # # ### ###########
# # # # # # # # #
####### # ### ####### # ### ####### #
# # # # # # # #
# ####### # # # ####### # ##### # # #
# # # # # # # # # # #
# ##### # # ##### ######### # ### # #
# # # # #B#
#####################################
MAZE_2
 
MAZE3 = <<MAZE_3 # should FAIL
#####################################
# # # # #
# ### # ####### # # # ############# #
# # # # # # # # # #
### ##### ### ####### # ##### ### # #
# # # # A # # # # #
# ######### ##### # ####### ### ### #
# ### # # # # #
# ### ### ####### ####### # # # # ###
# # # # # #B# # # # # # #
# # # ##### ### # # # # ### # ##### #
# # # # # #
#####################################
MAZE_3
 
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
end
end

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.