-
-
Save RLGGHC/33a2fc37cd23c9a163ec 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
#In this problem we have to identify the circuit with the least weight between A and G. We cab start traversing from A and moving towards G or starting with G and moving backwards towards A | |
# | |
# The ciruit can be represted as follows assuming the flow to be in any direction. | |
@circuits = [ | |
['A','B',50], | |
['A','D',150], | |
['B','C',250], | |
['D','C',50], | |
['B','E',250], | |
['D','F',400], | |
['C','F',100], | |
['C','E',350], | |
['F','G',100], | |
['E','G',200] | |
] | |
@redundant_resistors = [] #to store all the redundant resistors | |
@start_node = 'A' #to store the startt node | |
@end_node = 'G' #to store the end node | |
@traversal_array = [] #to store all the possible circuits | |
@minimal_circuit = '' #to store the minimum resistance circuit | |
@minimum_total = -1 #to store the total resistance | |
#A recursive function that identifies all the possible circuits. | |
#Calculates the minimum possible circuit and stores it in @minimal_circuit. | |
#The function accepts three parameters in the order starting node of circuit, first node traversed and the total resistance which is 0 at the start | |
def all_circuits(current_node,traversed,total) | |
traversed | |
@circuits.each do |link| | |
if current_node == link[0] | |
next_node = link[1] | |
elsif current_node == link[1] | |
next_node = link[0] | |
end | |
if next_node != nil | |
if traversed.include? next_node | |
next | |
elsif next_node == @end_node | |
total = total + link[2] | |
if @minimum_total > total || @minimum_total == -1 | |
@minimum_total = total | |
@minimal_circuit = traversed + next_node | |
end | |
@traversal_array.push([traversed+next_node,total]) | |
next | |
else | |
total = total + link[2] | |
all_circuits(next_node,traversed+next_node,total) | |
end | |
end | |
end | |
end | |
all_circuits(@start_node,'A',0) | |
#Calculate all the redundant resistors | |
@circuits.each_index do |index| | |
if first_occurence = @minimal_circuit.index(@circuits[index][0]) | |
if (first_occurence+1) == @minimal_circuit.index(@circuits[index][1]) | |
next | |
end | |
end | |
@redundant_resistors.push(@circuits[index]) | |
end | |
#Display the result | |
puts "Minimal circuit: " + @minimal_circuit | |
puts "Minimal Total: " + @minimum_total.to_s | |
print "Result is ---> " | |
p @redundant_resistors | |
@redundant_resistors |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment