secret
Last active

  • Download Gist
RobisonSantoa.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
#!/usr/bin/ruby -w
 
=begin
AUTHOR: Robison ER Santos
EMAIL: rwrsantos@gmail.com
COUNTRY: Brazil
 
 
Short Circuit - Redundant Paths
This is a solution for the Ruby Programming Challenge For Newbies #3.
This solution takes a circuit description in array format and creates a
directed graph. In this directed graph it's possible to get the weight
of a path (resistance) and the node father of a given node.
The circuit description should follow the pattern:
[father_node, son_node, path_weight]
e.g.
[
[ :A, :B, 50 ],
[ :A, :D, 150],
[ :B, :C, 250],
[ :B, :E, 250],
[ :C, :E, 350],
[ :D, :C, 50 ],
[ :C, :F, 100],
[ :D, :F, 400],
[ :E, :G, 200],
[ :F, :G, 100],
]
for the circuit:
50 150
[B]----------[A]----------[D]
|\ /|
| \_________ _________/ |
| 250 \ / 50 |
250 | [C] | 400
| ________/ \________ |
| / 350 100 \ |
|/ \|
[E]----------[G]----------[F]
200 100
It assumes the previous node as father and the next node as son in the
direction of the last node - in this case, the node 'G'.
In order to find the minimum path - short path - between the first node and
the last node in the circuit, the solution tries to follow the path from the
last node to the first node, always thru the vertex with least weight.
This path is stored into a variable, following the same pattern as asked for
the circuit descriton: [[father_node, son_node, path_weight]...]. When the
first node is reached, then the computation ends and the solution is holded.
To get the redundant path, all we have to do now is to remove the minimum path
from the circuit. What remains is the answer.
For the given circuit, the minimum path is:
[
[:A, :D, 150],
[:D, :C, 50 ],
[:C, :F, 100],
[:F, :G, 100]
]
And the redundant path is:
[
[:A, :B, 50 ],
[:B, :C, 250],
[:B, :E, 250],
[:C, :E, 350],
[:D, :F, 400],
[:E, :G, 200],
]
For simplicity, it was created a simple module with two classes: DirectedGraph,
for a better representation of the circuit, and Circuit, which can easily solve
the redundant path problem, given the graph description, the first node and the
last node.
Also, to keep simplicity, it wasn't implemented command line parameters.
=end
 
module ShortCircuit
INF = 10**10
# This class takes a circuit array representation and transforms it in a
# directed graph representation.
class DirectedGraph
def initialize(graph_array)
@weights = Hash.new{|k,v| k[v] = {}} # hash of hashes.
@fathers = Hash.new{|k,v| k[v] = []} # hash of arrays.
# grab weights(u,v)
# grab fathers(u)
graph_array.each do |array|
@weights[array[0]][array[1]] = array[2] # create the matrix of weights
@fathers[array[1]] << array[0] # create the matrix of fathers
end
end
# Returns the fathers of an node as an array
def fathers(node)
@fathers[node]
end
# Returns the weight of a given vertex [u,v]
def weight(u,v)
@weights[u][v]
end
end
 
# This class can solve redundant path by calculating the minimum path of a
# directed graph, then removing it from the graph array representation.
class Circuit
def self.solve_redundant_path(graph,first, last)
solution = [] # minimum path solution
dgraph = ShortCircuit::DirectedGraph.new(graph) # directed graph
look = last # current node
alt = nil # auxiliar variable
# If the first node was not reached yet, keep looking
while look != first
min_weight = ShortCircuit::INF # Now, the minimum weight is infinit
# For each father node of the current node,
# get the weight of their vertex and, if it is the least one, store it.
dgraph.fathers(look).each do |n|
n_weight = dgraph.weight(n,look)
min_weight, alt = n_weight, n if n_weight && min_weight > n_weight
end
# Store the minimum path
solution.unshift [alt,look,min_weight]
# Get the next node
look = alt
end
# Remove the minimum path form yhe graph description and return the
# redundant path.
graph.delete_if {|path| solution.include? path}
end
end
end
 
################# Test ###########################
 
circuit = [
[ :A, :B, 50 ],
[ :A, :D, 150],
[ :B, :C, 250],
[ :B, :E, 250],
[ :C, :E, 350],
[ :D, :C, 50 ],
[ :C, :F, 100],
[ :D, :F, 400],
[ :E, :G, 200],
[ :F, :G, 100],
]
ShortCircuit::Circuit.solve_redundant_path(circuit,:A,:G).each {|path| p path}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.