secret
Created

  • Download Gist
node.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
# The Nodes are the labeled points between the resistors.
# Each one has an id, total resistance value, visited flag and a route.
# The route is the path taken to get to that node from the start.
 
class Node
attr_accessor :total, :visited, :route
attr_reader :id
def initialize(id, total=1.0/0)
@id = id
@total = total
@not_visited = true
@route = []
end
def not_visited?
@not_visited
end
def visited!
@not_visited = false
end
def to_s
self.id
end
def to_a
ary = []
@route.each {|p| ary << p.to_a}
ary
end
end
path.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
# The Paths are the resistors with refrences to which Nodes surround them.
 
class Path
attr_reader :from, :to, :value
def initialize(n1, n2, value)
@from = n1
@to = n2
@value = value
end
 
def to_a
[@from, @to].sort << @value
end
end
short_circut.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 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155
# Antonio's Shortest Path program using Dijkstra's algorithm.
# Written for Gautam Rege's 'Short Circut (#3)' quiz on the RubyLearning Blog.
# Use of program from command line is as follows...
#
# => ruby short_circut.rb (text_file.txt) (starting_node) (ending_node)
#
# The text file (included) must contain one 'array of array's' in the following format.
# "[['A', 'B', 250], ...]" where the strings are nodes surrounding a resistor value (the integer).
# The 'starting_node' determines which node to start the route checking from.
# The 'ending_node' determines which node is the destination.
#
# If no starting_node is specified, the check will begin from the first node in the array.
# If no ending_node is specified, the check will simply end once all nodes have been visited
# returning the redundant paths for the last one checked (the furthest away from the start).
#
# There is no support for multiple shortest paths in this version.
 
require 'node'
require 'path'
require 'pp'
 
# The class which runs everything. Create a new instance and pass in the initial
# 'array of array's' of data, in the given text format.
 
class Controller
def initialize(input)
@ary = File.open(input) {|f| eval(f.read)}
@nodes = node_load(@ary)
@paths = path_load(@ary)
end
# The method which outputs the final redundant paths in array form.
def find_redundant_paths(start, finish=nil)
final_array = move(start, finish).to_a
@ary - final_array
end
# The default first node to use if one was not specified.
def first_node
@nodes.first.to_s
end
protected
# Loads the Path data from the file given.
# Duplicates each path with the reversed Nodes to check forwards and backwards travel.
def path_load(ary)
new_array = []
ary.each do |a|
p1 = Path.new(a[0], a[1], a[2])
p2 = Path.new(a[1], a[0], a[2])
new_array << p1 << p2
end
new_array
end
#Loads the Node data from the file given.
def node_load(a)
n = a.flatten.uniq.delete_if {|i| i.class == Fixnum}
@nodes = n.collect { |n| Node.new(n) }
end
# Searches the Paths to find a qualifying path and returns it.
def path_find(from)
@paths.find_all {|p| node_find(p.from) == from &&
node_find(p.to).not_visited?}
end
# Searches the Nodes to find one based on its id and returns it.
def node_find(s)
@nodes.find {|n| n.id == s}
end
# Searches the Nodes to find the next one for move() to use.
def smallest_unvisited
node = @nodes.find_all {|n| n.not_visited? == true}
ns = node.sort_by {|n| n.total}
return nil if ns.empty?
ns.first
end
private
 
# The driving force behind the algorithm. Details inside.
def move(start, finish)
# Find the node to use. Works with a Node's id or a Node itself.
current = node_find(start.to_s)
# Make the value 0 if it is Infinity
current.total = 0 if current.total == 1.0/0
# Find the appropriate paths to move. Will be an array.
paths = path_find(current)
# Check if the new movement total will be higher than the previous.
# If so, change the node's total and route values.
paths.each do |p|
check = p.value + current.total
if node_find(p.to).total > check ||
node_find(p.to).total == 1.0/0
# Change the total value.
node_find(p.to).total = check
# Change the new node's route to the current's one and append the new path to it.
node_find(p.to).route = current.route + [p]
end
end
# Mark the current node as visited, never to be checked again.
current.visited!
# Find the next node to use. Will be the 'closest', unvisited node to the start.
next_up = smallest_unvisited
# Keep moving through until there are no more nodes to check (all visited)
# or until the specified ending node is reached.
if next_up.nil? || current.to_s == finish
# When the looping is done, return the final node containing the route taken.
return current
else
# Do the next move
move(next_up, finish)
end
end
end
 
### Program Begins ###
 
if __FILE__ == $0
 
a = Controller.new(ARGV.shift)
 
begin
case ARGV.size
when 0
pp a.find_redundant_paths(a.first_node)
when 1..2
pp a.find_redundant_paths(*ARGV)
else
raise
end
rescue
puts <<-EOF
Useage:
=> ruby short_circut.rb (text_file.txt) (starting_node) (ending_node)
 
The 'text_file' must contain one 'array of array's' in the following format...
=> "[['A', 'B', 250], ...]"
The strings are nodes which surround a resistor value (the integer).
 
The 'starting_node' determines which node to start the route checking from.
The 'ending_node' determines which node is the destination.
If no starting_node is specified, the check will begin from the first node in the array.
If no ending_node is specified ,the check will simply end once all nodes have been visited,
returning the redundant paths for the last one checked (the furthest away from the start).
EOF
end
 
end
test_array.txt
1 2 3 4 5 6 7 8 9 10 11 12
[
[ '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],
]

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.