-
-
Save anonymous/0ff485999bc8be8f7fc4 to your computer and use it in GitHub Desktop.
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
require 'test/unit' | |
=begin | |
Assumptions: Paths given as input should always indicate the flow of current. | |
For eg: [A, B, 50] should mean current flowing from A to B in circuit. If the above is | |
indicated by [B, A, 50] then the program wont give the desired output. | |
=end | |
# this function takes as input an array of paths, a source node and a destination node | |
def find_redundant_resistors(input, src, dest) | |
nodes = [] | |
weight_nodes = Hash.new(1<<32) | |
prev_node = {} | |
# convert the input to form {"node1"=>{"neighbour1"=>7, "neighbour2"=>9}, "node2"=>{"neighbour1"=>5, "neighbour2"=>7,}} | |
graph = input.inject({}) do |hash, path| | |
hash[path[0]] ||= Hash.new | |
hash[path[0]][path[1]] = path[2] | |
hash | |
end | |
nodes = graph.keys | |
# follow the dijkstra algorithm and find least weight and best predecessor of all the nodes | |
weight_nodes[src] = 0 | |
until (nodes.empty?) | |
# find the node with the minimum weight | |
min = nil | |
nodes.each do |node| | |
min = node if weight_nodes[node] < weight_nodes[min] | |
end | |
break if min.nil? | |
# update the weight and predecessor of nodes | |
nodes = nodes - [min] | |
graph[min] and graph[min].keys.each do |v| | |
total = weight_nodes[min] + graph[min][v] | |
if total < weight_nodes[v] | |
weight_nodes[v] = total | |
prev_node[v] = min | |
end | |
end | |
end | |
# find the shortest path and create an array of arrays similar to the format of input | |
path = [] | |
until prev_node[dest].nil? | |
path << [prev_node[dest], dest, weight_nodes[dest] - weight_nodes[prev_node[dest]]] | |
dest = prev_node[dest] | |
end | |
# return the paths which do not form the shortest path | |
input - path | |
end | |
# Some testcases | |
class TestRedundantResistors < Test::Unit::TestCase | |
def test_redundant_resistors | |
assert_equal( | |
find_redundant_resistors( | |
[['A','B',50]], | |
'A','B'), | |
[]) | |
assert_equal( | |
find_redundant_resistors( | |
[['A','B',50], | |
['B', 'C', 50], | |
['A', 'C', 110]], | |
'A','C'), | |
[['A', 'C', 110]] ) | |
assert_equal( | |
find_redundant_resistors( | |
[[ 'A', 'B', 50], | |
[ 'A', 'D', 150], | |
[ 'B', 'C', 250], | |
[ 'B', 'E', 250], | |
[ 'C', 'E', 350], | |
[ 'C', 'F', 100], | |
[ 'D', 'C', 50], | |
[ 'D', 'F', 400], | |
[ 'E', 'G', 200], | |
[ 'F', 'G', 100]], | |
'A', 'G' ), | |
[["A", "B", 50], | |
["B", "C", 250], | |
["B", "E", 250], | |
["C", "E", 350], | |
["D", "F", 400], | |
["E", "G", 200]] ) | |
assert_equal( | |
find_redundant_resistors( | |
[[ 'A', 'B', 7], | |
[ 'A', 'C', 9], | |
[ 'A', 'F', 14], | |
[ 'B', 'C', 10], | |
[ 'B', 'D', 15], | |
[ 'C', 'D', 11], | |
[ 'C', 'F', 2], | |
[ 'D', 'E', 6], | |
[ 'F', 'E', 9]], | |
'A', 'E' ), | |
[[ 'A', 'B', 7], | |
[ 'A', 'F', 14], | |
[ 'B', 'C', 10], | |
[ 'B', 'D', 15], | |
[ 'C', 'D', 11], | |
[ 'D', 'E', 6]] ) | |
assert_equal( | |
find_redundant_resistors( | |
[[ 'A', 'B', 1], | |
[ 'A', 'H', 50], | |
[ 'B', 'I', 60], | |
[ 'B', 'C', 7], | |
[ 'C', 'I', 100], | |
[ 'C', 'D', 2], | |
[ 'D', 'I', 4], | |
[ 'D', 'E', 3], | |
[ 'E', 'I', 10], | |
[ 'E', 'F', 200], | |
[ 'F', 'I', 50], | |
[ 'F', 'G', 80], | |
[ 'G', 'I', 70], | |
[ 'G', 'H', 90], | |
[ 'I', 'H', 5], | |
[ 'I', 'A', 15]], | |
'A', 'H' ), | |
[["A", "H", 50], | |
["B", "I", 60], | |
["C", "I", 100], | |
["D", "E", 3], | |
["E", "I", 10], | |
["E", "F", 200], | |
["F", "I", 50], | |
["F", "G", 80], | |
["G", "I", 70], | |
["G", "H", 90], | |
["I", "A", 15]]) | |
assert_equal( | |
find_redundant_resistors( | |
[[ 'A', 'B', 50], | |
[ 'D', 'A', 150], | |
[ 'B', 'C', 250], | |
[ 'B', 'E', 250], | |
[ 'C', 'E', 350], | |
[ 'C', 'F', 100], | |
[ 'D', 'C', 50], | |
[ 'D', 'F', 400], | |
[ 'G', 'E', 200], | |
[ 'F', 'G', 100]], | |
'D', 'E' ), | |
[["A", "B", 50], | |
["D", "A", 150], | |
["B", "C", 250], | |
["B", "E", 250], | |
["C", "F", 100], | |
["D", "F", 400], | |
["G", "E", 200], | |
["F", "G", 100]]) | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment