public
Last active — forked from /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
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
tree.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
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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.