public
Last active

  • Download Gist
gistfile1.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
class Circuit
 
def initialize(resistors)
@resistors = resistors
@final_node = 0
 
@resistors.each do |(source, destination, resistance)|
@final_node = [@final_node, source, destination].max
end
 
@circuit = Array.new(@final_node+1){Array.new(@final_node+1)}
 
@resistors.each do |(source, destination, resistance)|
@circuit[source][destination] = resistance
@circuit[destination][source] = resistance
end
end
 
def shortest_path(destination = nil, path = nil, resistance = 0)
if path
if path.last == destination
[resistance, path]
else
@circuit[path.last].to_enum(:each_with_index).map {|x, i|
x && !path.include?(i) && shortest_path(destination, path.dup << i, resistance+x) || nil
}.compact.sort.first
end
else
shortest_path(@final_node, [0])
end
end
 
def unused_resistors
unused = @resistors.dup
(0...(path = shortest_path[1]).size-1).each do |i|
unused.delete([path[i], path[i+1], @circuit[path[i]][path[i+1]]])
unused.delete([path[i+1], path[i], @circuit[path[i+1]][path[i]]])
end
unused
end
def unused_resistors_with_alpha_labels
unused_resistors.map do |(source, destination, resistance)|
[(65+source).chr, (65+destination).chr, resistance]
end
end
end
 
A = 0; B = 1; C = 2; D = 3; E = 4; F = 5; G = 6;
test = Circuit.new([
[ A, B, 50],
[ A, D, 150],
[ B, C, 250],
[ B, E, 250],
[ C, E, 350],
[ C, D, 50],
[ C, F, 100],
[ D, F, 400],
[ E, G, 200],
[ F, G, 100]
])
if test.unused_resistors_with_alpha_labels == [
[ 'A', 'B', 50 ],
[ 'B', 'C', 250],
[ 'B', 'E', 250],
[ 'C', 'E', 350],
[ 'D', 'F', 400],
[ 'E', 'G', 200],
]
puts "It works!"
else
puts "Broken :0("
end

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.