• Download Gist
short-circuit-samjohnson.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
# 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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.