public
Created

  • Download Gist
Circuits.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
#!/usr/bin/env ruby
 
class CircuitSegment
attr_accessor :startNode, :endNode, :ohmage
def initialize(startNode, endNode, ohmage)
@startNode=startNode
@endNode=endNode
@ohmage=ohmage
end
end
 
class Circuit
attr_accessor :segments, :start, :end
def initialize(start,cEnd)
@start = start
@end = cEnd
@segments=[]
end
def addSegment(segment)
@segments.push(segment) unless @segments.include?(segment)
end
end
 
class Tracer
attr_accessor :circuit
def initialize(circuit)
@circuit=circuit
end
# Clear our possibleRoutes array and start findRoutes
def findPossibleRoutes
@possibleRoutes=[]
currNode=circuit.start
@possibleRoutes.push([currNode])
findRoutes
end
# Find the routes available based on the current
# value for possibleRoutes.
# Basically, this goes through all the possibleRoutes
# that have been built so far, takes the last letter
# and selects the segments that have that letter as a
# startNode.
def findRoutes
@possibleRoutes.each do |a|
currNode = a.last
next if (currNode==@circuit.end)
currentNodes = @circuit.segments.select { |c| c.startNode==currNode}
currentRoutes = @possibleRoutes.select { |r| r.last==currNode}
next if currentRoutes.empty?
for i in 1..currentNodes.length
newArray=currentRoutes[0].dup
for i in 1..currentNodes.length-1
newArray.push(currentNodes[i].endNode)
end
@possibleRoutes.push(newArray) unless @possibleRoutes.include?(newArray)
end
currentRoutes[0].push(currentNodes[0].endNode)
findRoutes
end
end
# The workhorse. For each possibleRoute, calculate the ohmage
# and pass the winning route (with the lowest ohmage) to be
# printed
def pathOfLeastResistance
findPossibleRoutes
winningRoute=nil
winningOhmage=0
path=[]
@possibleRoutes.each do |rt|
currentOhmage = calculateOhmageForRoute(rt)
if currentOhmage < winningOhmage or winningOhmage==0
currentOhmage=winningOhmage
winningRoute=rt
end
end
printRedundant(winningRoute) unless winningRoute.nil?
end
# Calculate the ohmage for the given route
# The route is expected to be an array of
# letters representing nodes.
def calculateOhmageForRoute(rt)
sum=0
getNodesForRoute(rt) do |n|
sum = sum + n.ohmage
end
sum
end
# Print the route. The passed in route is the route
# we want to KEEP. The redundant nodes will be derived
# from this route.
def printRedundant(rt)
segsToKeep =[]
getNodesForRoute(rt) do |n|
segsToKeep.push(n)
end
(@circuit.segments-segsToKeep).map do |s|
[s.startNode, s.endNode, s.ohmage]
end
end
# Helper method to get segments for the supplied route
# and run the block on each segment
def getNodesForRoute(rt,&code)
rt.each_with_index do |node,index|
if node!=rt.last
segs=@circuit.segments.select do |n|
n.startNode==node && n.endNode==rt[index+1]
end
code.call(segs[0])
end
end
end
end
 
def doIt
circ= Circuit.new("A","G")
circ.addSegment(CircuitSegment.new("A","B",50))
circ.addSegment(CircuitSegment.new("A","D",150))
circ.addSegment(CircuitSegment.new("B","C",250))
circ.addSegment(CircuitSegment.new("B","E",250))
circ.addSegment(CircuitSegment.new("C","E",350))
circ.addSegment(CircuitSegment.new("D","C",50))
circ.addSegment(CircuitSegment.new("C","F",100))
circ.addSegment(CircuitSegment.new("D","F",400))
circ.addSegment(CircuitSegment.new("E","G",200))
circ.addSegment(CircuitSegment.new("F","G",100))
tr=Tracer.new(circ)
tr.pathOfLeastResistance
end
 

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.