Created
October 30, 2009 10:56
-
-
Save jamesdaniels/222262 to your computer and use it in GitHub Desktop.
Short Circuit ~ http://rubylearning.com/blog/2009/10/30/rpcfn-short-circuit-3/
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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