Instantly share code, notes, and snippets.

# anonymous/harshadwankhede.rbSecret Created Oct 30, 2009

 #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