secret
Last active — forked from himansudesai/himansudesai.rb

  • Download Gist
himansudesai.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 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221
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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.