Skip to content

Instantly share code, notes, and snippets.

@RLGGHC
Forked from anonymous/maze.rb
Created January 5, 2010 02:17
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save RLGGHC/269084 to your computer and use it in GitHub Desktop.
require 'tree'
class Maze
WALL_CHAR = '#'
START_CHAR = 'A'
GOAL_CHAR = 'B'
def initialize(maze)
@maze = maze.lines.map { |l| l.chomp.split '' }
determine_start
@tree = build_path_tree
end
def solvable?
@tree.contains? true
end
def steps
if ! self.solvable? then
0
else
@tree.minimal_pathlength_to true
end
end
def at(x, y)
@maze[y][x]
end
def wall_at?(x, y)
@maze[y][x] == WALL_CHAR
end
def possible_directions_at(x, y, came_from = nil)
directions = []
raise ArgumentError 'y too big' if y >= @maze.size
raise ArgumentError 'x too big' if x >= @maze[0].size
raise ArgumentError "there is a wall at #{x},#{y}!" if wall_at?(x, y)
directions = Direction.all.select do |d|
# all directions where there is no wall and were we did not come from
(! wall_at?(*Direction.goto(x, y, d))) && (d != came_from)
end
end
private
def determine_start
@maze.each_with_index do |line, y|
line.each_with_index do |char, x|
if char == START_CHAR then
@start = [x, y]
end
end
end
end
# Builds a tree with all paths through the maze.
#
# The 'name' of the tree elements is a boolean variable that
# determines whether we have reached the goal ('B'). This way,
# we can later just test whether the tree contains 'true' to
# see if the maze is solvable
def build_path_tree(x = @start[0], y = @start[1], came_from = nil)
name = (at(x, y) == GOAL_CHAR)
t = Tree.new(name)
possible_directions_at(x, y, came_from).each do |d|
new_x, new_y = Direction.goto(x, y, d)
t.add_child(build_path_tree new_x, new_y, Direction.opposite(d))
end
t
end
end
class Direction
NORTH = [0, -1]
SOUTH = [0, +1]
WEST = [-1, 0]
EAST = [+1, 0]
def self.all
self.constants.map { |d| self.const_get(d) }
end
def self.opposite(dir)
dir.map { |d| -1 * d }
end
def self.goto(x, y, dir)
[x + dir[0], y + dir[1]]
end
end
class Tree
attr_reader :children, :object
def initialize(object)
@object = object
@children = []
end
def add_child(child)
if child.is_a? Tree then
@children.push child
else
@children.push Tree.new(child)
end
end
def contains?(object)
# is the root itself the object we're looking for?
contained = (@object == object)
# iterate over the tree to look for the object
children.each do |c|
contained ||= c.contains? object
end
contained
end
def pp(level = 0)
result = (" " * level) + "#{object}\n"
@children.each do |c|
result += c.pp(level + 1)
end
result
end
def depth(depth = 0, curr_max_depth = 0)
if (depth > curr_max_depth)
curr_max_depth = depth
end
@children.each do |c|
curr_max_depth = c.depth(depth + 1, curr_max_depth)
end
curr_max_depth
end
# the minimal length of a path to a certain object
def minimal_pathlength_to(object, length = 0, curr_min_length = self.depth)
if (@object == object) && (length < curr_min_length) then
curr_min_length = length
end
@children.each do |c|
curr_min_length = c.minimal_pathlength_to(object, length + 1,
curr_min_length)
end
curr_min_length
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment