secret
anonymous / patharty.rb
Last active

Description: Objects were created for each resistor and the end points that it connected (e.g. A B 50). These objects were kept in an Array. Traversed the circuit by taken the start point of A searching for ResistorLink objects that contained that val

  • Download Gist
patharty.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 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315
#!/usr/bin/env ruby
 
class ResistorLink
def initialize(link1,link2,rs)
# takes in the two endpoints and the
# resistor value that connects the two points
@linkends = Array.new
@linkends.push(link1)
@linkends.push(link2)
@resistorvalue = rs
@used = 0
end
 
def printInfo()
# Prints to the screen the two points
# that this object is connected to and
# the value of the resistor connecting the
# points
info = nil
@linkends.each do |linkend|
info = "#{info} " << "#{linkend}"
end
info = "#{info} " << "#{@resistorvalue}"
puts "#{info}"
end
 
def getOtherEnd(searchvalue)
# takes in a point on the circuit
# and if that point matches one of the points
# in this object it returns the other point
# that it is connected to. If the first
# point is not a part of this object then
# a -1 is returned to indicate this object does
# not connect to the searched point
otherend = 0
foundit = 0
@linkends.each do |linkend|
if linkend.eql? searchvalue
foundit = 1
else
otherend = linkend
end
end
if foundit == 0
otherend = -1
end
otherend
end
 
def getResistor
@resistorvalue
end
 
def setUsed(flag)
@used = flag
end
def getUsed
@used
end
 
def matchEnds(ends)
# takes in two points from the circuit
# and if those points match the points
# of this object it returns a 1 otherwise
# it returns a 0
isMatch = 0
end1 = ends[0,1]
end2 = ends[1,2]
if (@linkends[0].eql? end1) || (@linkends[1].eql? end1)
if (@linkends[0].eql? end2) || (@linkends[1].eql? end2)
isMatch = 1
end
end
isMatch
end
 
end
if __FILE__ == $0
@allPathsTaken = 0
@resistorsum = Array.new()
@linkarray = Array.new()
@startposition = 'A'
@endposition = 'G'
@pathtaken = Array.new()
@pathtaken.push(@startposition)
@completePaths = Array.new()
@completeResistance = Array.new()
@deadendlist = Array.new()
@lasthop = nil
 
@linkarray[0]=ResistorLink.new('A','B',50)
@linkarray[1]=ResistorLink.new('A','D',150)
@linkarray[2]=ResistorLink.new('B','C',250)
@linkarray[3]=ResistorLink.new('B','E',250)
@linkarray[4]=ResistorLink.new('C','E',350)
@linkarray[5]=ResistorLink.new('C','D',50)
@linkarray[6]=ResistorLink.new('C','F',100)
@linkarray[7]=ResistorLink.new('D','F',400)
@linkarray[8]=ResistorLink.new('E','G',200)
@linkarray[9]=ResistorLink.new('F','G',100)
 
def findUnneededResistors(path)
# uses the path of least resistance
# to find the ResistorLink objects
# that make up that path. If the
# object was a part of the least resistant
# path mark it as Used. Then when completed
# create a list of unused ResistorLink objects
# and have them print their values
puts "Unneeded Resistor List:"
numofchars = path.length
count = 0
while count < (numofchars-1) do
hop = path[count,2]
count = count + 1
@linkarray.each do |link|
if link.matchEnds(hop) == 1
link.setUsed(1)
end
end
end
@linkarray.each do |link|
if link.getUsed() == 0
link.printInfo()
end
end
end
 
def beenThereDoneThat(searchvalue)
# this is to keep from crossing the
# same point twice in one route
beenThere = 0
@pathtaken.each do |taken|
if taken.eql? searchvalue
beenThere = 1
end
end
beenThere
end
 
def storeValues()
# when a start to finish route is found
# this stores the route and resistance
# total away so when we have exhausted
# all paths we can easily check the start to
# finish paths along with total resistance of the path
tempsum = 0
temppath = nil
@pathtaken.each do |hop|
temppath = "#{temppath}" << "#{hop}"
end
@completePaths.push(temppath)
@resistorsum.each do |rvalue|
tempsum = tempsum + rvalue
end
@completeResistance.push(tempsum)
end
 
def popOff()
# used to move back when we have either
# reached the finish or a deadend
@lasthop = @pathtaken.pop()
#puts "Setting #{@lasthop} to lasthop"
poppedvalue = @resistorsum.pop()
if @lasthop == nil
@allPathsTaken = 1
end
#puts "Moving Back to #{@pathtaken.last}"
#puts "Removing #{poppedvalue} from Sum"
end
 
def printPath()
# Prints the route taken for a successful
# start to finish route. Also sums the
# resistors to give us total resistance
# Both will be used to check for path of
# least resistance when all paths are exhausted
hoplist = nil
sum = 0
@pathtaken.each do |hop|
hoplist = "#{hoplist}" << "#{hop}"
end
@resistorsum.each do |rvalue|
sum = sum + rvalue
end
puts "Successful Path Found: #{hoplist} Resistance was: #{sum}"
end
 
def addToDeadend(deadendpath)
# if a route is deadended it has been
# found to not have any other working paths
# that branch off from it. This is used
# to stop us from going down a route a second
# time for a given path
hoplist = nil
deadendpath.each do |hop|
hoplist = "#{hoplist}" << "#{hop}"
end
@deadendlist.push(hoplist)
#puts "Added Deadend Path: #{hoplist}"
end
 
def isDeadend(path,nexthop)
# compares the route we are looking to take
# to the deadend list to save us a redundant
# trip
isDeadend = 0
hoplist = nil
path.each do |hop|
hoplist = "#{hoplist}" << "#{hop}"
end
hoplist = "#{hoplist}" << "#{nexthop}"
@deadendlist.each do |deadend|
if deadend.eql? hoplist
isDeadend = 1
#puts "Path: #{hoplist} is a Deadend!"
end
end
isDeadend
end
 
def printCurrentRoute(path)
# prints the route that is currently
# being traveled. Used mainly for
# debugging
hoplist = nil
path.each do |hop|
hoplist = "#{hoplist}" << "#{hop}"
end
#puts "CurrentPath: #{hoplist}"
end
 
def findLeastResistance()
# goes through list of all complete
# start point to end point paths to
# find the path of least resistance
loopcount = 0
tempsum = nil
tempindex = nil
leastpath = nil
@completeResistance.each do |totalr|
if tempsum == nil
tempsum = totalr
end
if (totalr < tempsum)
tempsum = totalr
tempindex = loopcount
end
loopcount = loopcount + 1
end
leastpath = @completePaths[8]
puts "Path of Least Resistance: #{leastpath} Resistance: #{tempsum}"
leastpath
end
def findRoute(searchvalue)
# uses a start point to find connections
# to other points. Searches through the array
# of ResistorLink objects to find possible next hops
if @allPathsTaken == 1
leastresistance = findLeastResistance()
findUnneededResistors(leastresistance)
else
#puts "Searching for #{searchvalue}"
foundUntraveledLink = 0
if searchvalue.eql? @endposition
else
@linkarray.each do |linko|
otherEnd = linko.getOtherEnd(searchvalue)
if otherEnd == -1
else
#puts "Otherend is: #{otherEnd}"
# don't go to points we have already been to
if (beenThereDoneThat(otherEnd) == 0)
# want to avoid bouncing between two points
if (otherEnd != @lasthop)
if (isDeadend(@pathtaken,otherEnd) == 0)
foundUntraveledLink = 1
@lasthop = nil
#puts "Adding #{linko.getResistor()} to Sum"
@resistorsum.push(linko.getResistor())
@pathtaken.push(otherEnd)
#puts "Traveling to #{@pathtaken.last}"
printCurrentRoute(@pathtaken)
if otherEnd.eql? @endposition
#puts "Found the End!"
storeValues()
printPath()
# popOff()
end
findRoute(@pathtaken.last)
break
end
end
end
end
end # end position search if
end
if foundUntraveledLink == 0
#puts "Didn't find an untraveled link"
addToDeadend(@pathtaken)
popOff()
findRoute(@pathtaken.last)
end
end
end
 
# start us off by searching for
# points connected to the starting point
findRoute(@startposition)
 
end

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.