Skip to content

@RLGGHC /gist:222836 forked from jamesdaniels/gist:222262
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.