Skip to content

Instantly share code, notes, and snippets.

@zliang-min
Created December 29, 2009 03:45
Show Gist options
  • Save zliang-min/265135 to your computer and use it in GitHub Desktop.
Save zliang-min/265135 to your computer and use it in GitHub Desktop.
# 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment