-
-
Save TestingBytes/5ed31a447fb4c03a40fc 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
# Ruby Programming Challenge For Newbies: Short Circuit (#3) | |
# | |
# | |
#Author: Sam Johnson | |
#Date: November 20, 2009 | |
#email: samuel.johnson@gmail.com | |
def find_paths(node,path_array) | |
prior_node = path_array[path_array.length] unless path_array.length == 0 | |
path_array.push(node) # add the current node to the path | |
if( node[1] == 'G') | |
@Paths[0].push( Array.new(path_array) ) # Save the Path | |
@Paths[1].push( path_array.inject(0){|sum,x| sum+x[2]} ) # Save the Path cost | |
else # find a node that is connected, and hasn't been used yet, then call find_paths again | |
#If this node-end hasn't been visited twice, find one connected to it: Left-Side | |
if path_array.flatten.select{ |n| n == node[0] }.length < 2 | |
@CIRCUIT.select { |n| (n[0] == node[0] || n[1] == node[0]) && path_array.index(n) == nil }. | |
each{|n| find_paths(n,Array.new(path_array))} | |
end | |
#If this node-end hasn't been visited twice, find one connected to it: Right-Side | |
if path_array.flatten.select{ |n| n == node[1] }.length < 2 | |
@CIRCUIT.select{ |n| (n[0] == node[1] || n[1] == node[1]) && path_array.index(n) == nil }. | |
each{|n| find_paths(n,Array.new(path_array))} | |
end | |
end | |
end | |
def node_to_s(node) | |
"\[ \'#{node[0]}\', \'#{node[1]}\', #{node[2]}\]," | |
end | |
@CIRCUIT = [ | |
[ '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], | |
] | |
@Paths = Array.new() | |
@Paths[0] = Array.new() # For the paths | |
@Paths[1] = Array.new() # For the costs | |
@CIRCUIT.select { |n| n[0] == 'A'}.each{ |n| find_paths(n, Array.new() ) } | |
@Paths[1].each_with_index do |cost,index| | |
if cost == @Paths[1].min | |
# puts "Min Cost Path [#{cost}]:" | |
# puts "\[" | |
# @Paths[0][index].each{ |p| puts " #{node_to_s(p)}"} | |
# puts "\]" | |
puts "Redundant Paths: " | |
puts "\[" | |
@CIRCUIT.each{ |node| puts " #{node_to_s(node)}" if @Paths[0][index].index(node) == nil} | |
puts "\]" | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment