Skip to content

@IndianGuru /himansudesai.rb secret forked from himansudesai/himansudesai.rb
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
WALL = 'WALL' # constant denoting a WALL (point in the maze that we can't move past)
SPACE = 'SPACE' # constant denoting a point that can be traversed
# The Point class represents a point @ x, y in the maze.
# It's value is either 'WALL' ('#' in the original string)
# or 'SPACE' (' ' in the original string).
# NOTE: The end-point (B) is also given the value SPACE
# because it is legal to move to that point.
class Point
attr_accessor :x, :y, :val
def initialize(x, y, val)
self.x = x
self.y = y
self.val = val
end
# For Hash lookup and equality comparisons, two points
# are the same if their x and y coordinates are the same
def eql?(other)
(self.x == other.x) && (self.y == other.y)
end
# The hash of two points should also computer to the same value
def hash
"#{x},#{y}".hash
end
# Print string for debugging purposes
def to_s
"(#{x},#{y})"
end
end
# A segments is given a point to start from and from there, it "crawsl"
# forward, one point at a time. As long as there is only one possibility
# of going forward (even if the segment has to turn 90 degrees), the
# segment continues to crawl and accumulate a list of points. It will
# end up hitting a 'WALL' or succeed in reaching the end-point B. However,
# if in the process of crawling, it comes across 2 or more open spaces, it
# creates 2 ore more sub-segments (starting with those open-spaces).These
# sub-segments then keep crawling until they hit a WALL or the end-point,
# or they create sub-segments of their own, and the process continues...
# Note: In order for multiple segments (in a maze) to crawl without tripping
# over each other, or "turning back", a common data-structure of "visited"
# points is kept (in the Maze object which is a common object to all the
# segments). Each time a segment crawls forward to a point, it adds that
# point to the list of visited points.
class Segment
# st_pt = the initial point from which the Segment will start crawling
# maze is the parent maze to which this segment belongs
# points is an array (first element = st_pt) of points that are crawled
# segments = sub_segments if any
attr_accessor :st_pt, :maze, :points, :segments
def initialize(st_pt, maze)
self.st_pt = st_pt
self.maze = maze
self.points = Array.new
# The array of points starts off with st_pt
self.points << st_pt
# No sub-segments in the beginning
self.segments = Array.new
end
# Try to crawl one point forward from where the segment is currently at
# (from_pt)
def crawl(from_pt)
# We've reached the end-point (success - so return)
return if from_pt == self.maze.end_pt
# Else, tell the maze that this point was just visited
self.maze.visited(from_pt)
# Ask the maze for adjacent open points next to from_pt
open_spaces = self.maze.open_spaces(from_pt)
case (open_spaces.size)
when 0 # No open spaces - we've hit a WALL
when 1 #Exactly one open spot - continue crawling after
# updating the 'points' array
next_pt = open_spaces.first
self.points << next_pt
# continue crawling unless we just hit the end-point
self.crawl(next_pt) unless next_pt == self.maze.end_pt
else
# multiple open spaces (points). Create sub segments for each
# open point with that point as the starting point.
open_spaces.each do |pt|
s = Segment.new(pt, self.maze)
self.segments << s
s.crawl(pt)
end
end
end
# How many steps in this segment?
def steps
# return -1 if this segment isn't going to succeed in reaching the end-point
return -1 unless self.solvable?
# otherwise, go ask each sub-segment for their count (if there are any
# sub-segments, that is)
sub_counts = self.segments.collect { |e| e.steps }
# y <=> x means largest number is firt element after sorting. Since non
# solvable segments return -1, the first element will now be a real
# number of steps from a solvable sub-segment
sub_counts.sort! { |x, y| y <=> x }
# just in case there are multiple segments that can succeed, choose the one
# with the smallest count
smallest_subcount = sub_counts[0] == nil ? 0 : sub_counts[0]
# add our own points array size to the sub-segment count
self.points.size + smallest_subcount
end
# Can this segment or one of it's sub-segments reach the end-point?
def solvable?
# Either the points array is already at the end-point or if there are
# sub-segments, ask them if they are solvable
(self.points.last == self.maze.end_pt) || (self.segments.detect { |s| s.solvable? })
end
end
# Maze class has a collection of points with values of 'WALL' or 'SPACE', based on
# the definition string that is passed into the constructor
class Maze
# st_pt will hold the point with value 'A'
# end_pt will hold the point with value 'B'
# width, height = maze dimensions
# initial_segments = 0 or more segments created out of the empty spaces adjacent
# to the st_pt. Things are set in motion by asking these initial segments to
# start crawling
attr_accessor :width, :height, :points, :st_pt, :end_pt, :initial_segments
# construct the maze
def initialize(maze_def)
lines = maze_def.split(/\n/) # first, break up the lines
self.height = lines.size
self.width = lines.first.size
self.points = Hash.new
(0 .. self.height-1).each do |y|
chars = lines[y].split(//) # break each line into a char
(0 .. self.width-1).each do |x|
case (chars[x])
when 'A' # record st_pt
pt = self.st_pt = Point.new(x, y, WALL)
when 'B' # record end_point, but also put it's value as SPACE
# meaning we can traverse to it.
pt = self.end_pt = Point.new(x, y, SPACE)
when '#' # this is a wall. dead-end
pt = Point.new(x, y, WALL)
else ' ' # there is still hope we might reach the end-point
pt = Point.new(x, y, SPACE)
end
self.points["#{pt}"] = pt # update the points hash
end
end
@visited = Array.new
@visited << self.st_pt # only the st_pt is initially considered
# to have been visited, before the segments start to crawl
open_spaces = self.open_spaces(self.st_pt)
self.initial_segments = Array.new
# construct an initial_segment from each open space around
# the st_pt
open_spaces.each do |pt|
s = Segment.new(pt, self)
self.initial_segments << s
s.crawl(pt) # ask the segment to crawl - see who, if any, wins
end
end
# record that a point has been visited by one of the crawling segments
def visited(pt)
@visited << pt
end
# How many steps to solve the maze
def steps
counts = Array.new
counts << 0 # if no solvable segment, then answer 0
# (expected by this quiz problem statement)
self.initial_segments.each { |s| counts << s.steps}
# since non-solvable segments answer -1, we sort so that the
# largest number is the first element (y <=> x). That way it is
# either 0 (non solvable) or the count returned by one of the
# solvable segments
counts.sort! {|x,y| y <=> x }
counts[0]
end
# All the maze can do is ask the initial_segments if they are solvable
def solvable?
self.initial_segments.detect { |s| s.solvable? } ? true : false
end
# Segments query the Maze (which has the definition of open and walled
# points), to find out what open points there are, adjacent to a given point.
# The maze only answers open points that have not yet been visited, so
# segments don't accidentally crawl backwards
def open_spaces(pt)
spaces = Array.new
pts = Array.new
# 4 adjacent points
pts << left_val(pt) << right_val(pt) << up_val(pt) << down_val(pt)
# do we have any that are SPACE and not yet visited?
pts.each { |pt| spaces << pt if (pt.val == SPACE && !@visited.include?(pt)) }
spaces
end
# value of the point to the left of the given point
def left_val(pt)
self.points["#{Point.new(pt.x-1,pt.y, nil)}"]
end
# value of the point to the right of the given point
def right_val(pt)
self.points["#{Point.new(pt.x + 1,pt.y, nil)}"]
end
# value of the point to the top of the given point
def up_val(pt)
self.points["#{Point.new(pt.x, pt.y-1, nil)}"]
end
# value of the point to the bottom of the given point
def down_val(pt)
self.points["#{Point.new(pt.x, pt.y+1, nil)}"]
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.