secret
Last active

  • Download Gist
RPCFN3.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
=begin
The solution has been generalized to support basic network structures.
The network can be for example a circuitboard as required for this challenge,
or a map of geographical locations, or a network of people, or a model of a molecule...
 
The network consists of nodes that are associated with one another via paths.
 
Any path between 2 nodes, say nodes A and B will be represented twice in the
network to support bi-directionality.
It exists once as a path leading from A to B, associated with node A, and then
as a node leading from B to A, associated with node B.
Each path has a cost attribute which generalizes the expense associated with
moving from the start node to the target node. The cost attribute could for eaxmple
refer to the distance between two nodes, or, as the challenge requires, the resistance.
 
A node may have any number of paths (0 to n) leading from it to link it to any number of
target nodes (0 to n).
The pathway traced from any node to another is referred to as a Route.
There can be many routes linking a start and destination node.
 
The network - node - path model can be useful in a large number of application
over and above the RPCFN3 challenge.
 
The solution is contained in 3 files
1. RPCFN3.rb - The main script (this file)
2. RPCFN3_classes.rb - Contains all class definitions
3. RPCFN3_tests.rb - Tests
 
=end
PATH_RPCFN3 = [
[ '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],
]
FROM = 'A'
TO = 'G'
 
def get_redundant_resistors(nw)
#
# Get a unique list of path names.
# Get the list of paths in the shortest route.
# Get the difference - this is the redundant set of paths (bi-directional).
# Remove the duplicates to get the required result (see below)
#
all_paths = (nw.path_list.collect {|p| [p.from, p.to]})
min_paths = nw.min_cost_routes.first.path_list.collect {|p| [p.from, p.to]}
#
# The difference (all_paths - min_paths) is the true list of redundant paths
# taking into account that the network is implemented as bidirectional, so
# that each path exists twice, once in each direction, from one node to the
# other.
# The reverse paths are therefore removed to arrive at the required output
# list of redundant resistors.
#
redundant_resistors = (all_paths.collect {|p| p.sort.join('_')}).uniq - (min_paths.collect {|p| p.join('_')})
redundant_resistors.collect {|r| nw.path(r).to_a}
end
def show_results(nw)
nw.routes.each {|r| puts "Route #{r.name} cost #{r.cost} pathway #{r.nodes.collect {|n| n.name + ' '}}"}
puts "Minimum cost = #{nw.min_cost}, shared by routes #{(nw.min_cost_routes.collect {|r| r.name}).join(',')}"
puts "Maximum cost = #{nw.max_cost}, shared by routes #{(nw.max_cost_routes.collect {|r| r.name}).join(',')}"
puts "Average cost = #{nw.avg_cost}"
end
 
require 'RPCFN3_classes'
 
nw = Network.new # Create an empty network
nw.import(PATH_RPCFN3) # Load the network using data as formated in RPCFN3
nw.get_routes(FROM, TO) # Do the work. Assembles an array of all possible
# routes for given start and end nodes
output = get_redundant_resistors(nw)
puts "["
output.each {|p| puts "\t[#{p.join(',')}]"}
puts "]"
 
#nw.import(PATHS_TO_ROME)
#nw.get_routes('Paris', 'Istanbul')
#show_results(nw)
 
require 'test/unit'
require 'RPCFN3_tests'
RPCFN3_classes.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 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311
=begin
Network - outer container, a collection of node objects
Node - a point in the network that can be reached via at least one pathway.
includes a collection of paths that point to neighboring nodes.
Path - a link or association between 2 nodes. A path between 2 nodes implies
that they are neighbors.
Each path has a cost attribute, a generalization of things such as
resistance, distance, weight, difficulty, traffic density,
the toll or outlay or price incurred when following the path from
one end to the other.
Route - A pathway that connects 2 nodes defined as start and destination nodes.
There can be many different routes between 2 chosen nodes.
There can be one or more routes that have the same cost
=end
###########################################
class Network ############################
###########################################
#
# The outer container.
# A collection of Node objects, hashed for easy location of specific nodes
# Synonyms: Map, CircuitBoard, ...
#
# Its behaviour includes the ability to find all the possible routes
# between any 2 nodes (the start and end nodes). see get_routes
#
attr_reader :name, # a unique identifier
:nodes, # hash of nodes where the key is the node name
:routes, # array of routes populated when start and end nodes are provided
# see method get_routes
:max_cost, # max cost incurred following a specified route
:max_cost_routes, # list of routes that share max cost
:min_cost, # min cost incurred following a specified route
:min_cost_routes, # list of routes that share min cost
:avg_cost # average cost incurred across all routes
def initialize(name = 'myMap', nodes = [])
@name = name
@nodes = {}
@routes = []
nodes.each {|n| @nodes.store(n.name, n)}
init_stats
end
def import(paths) # import RPCFN3 format map data
paths.each do |p_in|
p_to = Path.new('', p_in[0],p_in[1],p_in[2])
p_reverse = p_to.reverse
[p_to, p_reverse].each do |p|
if has_node?(p.from)
node(p.from).add_path p
else
add_node Node.new(p.from, p)
end
end
end
end
def export # export to RPCFN3 format TODO
end
def has_node?(node) # some overloading
if node.kind_of? String
@nodes.has_key?(node)
elsif node.kind_of? Node
@nodes.has_key?(node.name)
else
false
end
end
def is_empty?
@nodes.length == 0
end
def node(node)
if node.kind_of? String
@nodes[node]
elsif node.kind_of? Node
@nodes[node.name]
else
false
end
end
def add_node(node) # single Node assumed if not array of nodes
node = [node] unless node.kind_of? Array
node.each {|n| @nodes.store(n.name, n)}
end
def node_count
@nodes.length
end
 
def neighbors(node) #neighboring nodes
node = node(node) if node.kind_of? String
node.paths.keys.collect {|pk| node(pk)}
end
def path_count
nodes.values.inject(0) {|cnt, n| cnt+= n.path_count}
end
 
def path(path_name)
# TODO:
# Making shaky assumptions wrt path name format, as follows:
# 1. Format is <from_nodename>_<to_nodename>
# 2. nodenames may not contain underscores
# It works for RPCFN3 but certainly requires some
# attention for use beyond that.
node(path_name.split('_').first).path(path_name.split('_').last)
end
def path_list # array of all paths in the network
nodes.values.collect {|n| n.paths.values.collect}.flatten
end
 
def route_count
routes.length
end
 
def get_routes(from, to)
#
# The stack is processed as a LIFO queue
# Each entry includes a node identifier (name) and a tail of breadcrumbs
# that include the nodes we have traversed to get to this entry's node.
#
# The traverse_node method processes the top stack entry (index=0)
# 1. Identify all possible next steps from here
# 2. Filter out possible destinations that we have already visited
# 3. Remove the top stack entry, been there, done that.
# 4. If we have not yet reached the end node, then
# put valid next steps onto the stack, each with breadcrumbs attached
# otherwise
# create a route from the bradcrumbs and save it
#
@from = from
@to = to
@stack = [[from, []]]
@routes = []
traverse_node until @stack.empty?
calc_stats
end
private
 
def traverse_node # This is the heart of the challenge
here = @stack.first[0]
crumbs = @stack.first[1] + [here] # list of node names that show where we came from
nb = neighbors(here).collect {|n| n.name} # all possible nodes we can reach from here
next_steps = nb - crumbs # remove nodes we have already been to
@stack.delete_at(0) # remove the top stack entry
if here != @to # Not there yet..
# pile next step nodes with breadcrumbs on top of stack
next_steps.each { |nn| @stack.insert(0, [nn, crumbs])}
else # We have reached the destination node.
# The nodes traversed are in crumbs.
# Create a list of nodes traversed and hook on each the actual path followed
# Use that list to create a new route object an add it to the list of routes
rnodes = []
crumbs.each_index do |i|
rn = Node.new(crumbs[i])
rn.add_path(node(crumbs[i]).path(crumbs[i + 1])) unless i == (crumbs.length - 1)
rnodes << rn
end
routes << Route.new("#{@from}_#{@to}_#{routes.length + 1}", node(@from), node(@to), rnodes)
end
end
def calc_stats
init_stats
costs = routes.collect {|r| r.cost}
costs.each {|d| @max_cost = d if d > @max_cost}
@min_cost += @max_cost
costs.each do |d|
@min_cost = d if d < @min_cost
@avg_cost += d
end
@avg_cost /= routes.count
#finally save a list of routes that share min / max values
routes.each do |r|
@min_cost_routes << r if r.cost == @min_cost
@max_cost_routes << r if r.cost == @max_cost
end
end
 
def init_stats
# max and min stats are implemented as hash to cater
# for more than one route with min or max values
@max_cost = @min_cost = @avg_cost = 0
@max_cost_routes = []
@min_cost_routes = []
end
end
 
###########################################
class Node ##################################
###########################################
 
attr_reader :name, # a unique identifier
:paths # a list of Path objects that lead us to adjacent nodes
# *Note* as implemented here (hash where key is
# the destination node identifier) we can only have
# one path that connects any 2 nodes.
# TODO: Allow more than one path between 2 nodes, ensuring
# that there is a cost (distance/weight/resistance)
# difference between them - (otherwise it makes no sense?)
def initialize(name, paths = [])
@name = name
# paths.kind_of?(Path) ? @paths = [paths] : @paths = paths
@paths = {}
paths.kind_of?(Path) ? @paths.store(paths.to, paths) : paths.each {|p| @paths.store(p.to, p)}
end
def is_orphaned?
paths.length == 0
end
def add_path(path) #String assumed if not array of paths
path.kind_of?(Path) ? @paths.store(path.to, path) : path.each {|p| @paths.store(p.to, p)}
end
 
def path(path)
if path.kind_of? String
@paths[path]
elsif path.kind_of? Path
@paths[path.to]
else
false
end
end
def cost(node)
@paths[node.kind_of?(Node) ? node.name : node].cost
end
 
def clear_paths
@paths = []
end
def path_count
@paths.length
end
 
end
 
###########################################
class Path ##################################
###########################################
attr_reader :name, # a unique identifier
:from, :to, # connecting node names. "from" is redundant, "to" is the destination node
:cost # alias distance, resistance, weight ...
def initialize(name, from, to, cost)
@name = name == '' ? "#{from}_#{to}" : name
@from = from
@to = to
@cost = cost
end
def reverse
Path.new(@name == "#{@from}_#{@to}" ? '' : @name, @to, @from, @cost)
end
def to_a #build output format for ROCFN3
[@from, @to, @cost]
end
end
 
###########################################
class Route ##############################
###########################################
attr_reader :name, # a unique identifier
:origin, :destination, # the start and end nodes
:nodes, # list of nodes traversed en route
:cost #incurred following this route
def initialize(name, origin, destination, nodes = [])
@name = name == '' ? "#{origin.name}_#{destination.name}" : name
@origin = origin
@destination = destination
@nodes = nodes
@cost = calculate_cost
end
def add_node(node) # single Node assumed if not array of nodes
node = [node] unless node.kind_of? Array
node.each {|n| @nodes.store(n.name, n)}
end
def path_list # array of all paths in the route
nodes.collect {|n| n.paths.values.collect}.flatten
end
 
def reverse # the return route
rev = nodes.reverse
i = 0
begin
rev[i].add_path(rev[i+1].paths.values.first.reverse)
rev[i+1].clear_paths
i += 1
end until i = (rev.length - 2)
Route.new(name == "#{origin.name}_#{destination.name}" ? '' : "Reverse of #{name}", destination, origin, rev)
end
private
def calculate_cost
nodes.inject(0) {|dist, n| dist += (n.paths.count == 1 ? n.paths.values.first.cost : 0)}
end
end
 
###########################################
class String # Playing around with bits of DSL ##############
###########################################
def is_a_node_on(theMap) # the string here is the name of a node
theMap.has_node?(self)
end
end
RPCFN3_tests.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 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247
=begin
*Note* I know these tests should be refactored...
they grew into an unwieldy monster very quickly :)
=end
PATHS_TO_ROME = [
[ 'London', 'Paris', 342],
[ 'London', 'Istanbul', 2500],
[ 'London', 'Rome', 1436],
[ 'Paris', 'Rome', 1109],
[ 'Paris', 'Marseille', 660],
[ 'Paris', 'Geneva', 411],
[ 'Marseille', 'Geneva', 328],
[ 'Marseille', 'Rome', 606],
[ 'Geneva', 'Rome', 700],
[ 'Geneva', 'Istanbul', 1922],
[ 'Rome', 'Istanbul', 1378],
]
require 'test/unit'
class ChallengeTest < Test::Unit::TestCase
 
# Path tests ######################################
 
def test_path_creation
f = 'A'; t = 'B'; d = 150
p = Path.new('',f, t, d)
assert_equal(p.name, f + '_' + t)
assert_equal(p.from, f)
assert_equal(p.to, t)
assert_equal(p.cost, d)
assert_equal(["#{f}", "#{t}", d], p.to_a)
end
def test_reverse
n = 'shiningPath', f = 'A'; t = 'B'; d = 150
p = Path.new(n, f, t, d)
assert_equal(p.name, n)
assert_equal(p.reverse.name, n)
assert_equal(p.reverse.to, f)
assert_equal(p.reverse.from, t)
p = Path.new('', f, t, d)
assert_not_equal(p.reverse.name, n)
end
 
# Node tests ######################################
 
def test_node_creation
n = Node.new('myNode')
assert_equal(true, n.is_orphaned?)
end
def test_add_path_to_node
n = Node.new('myNode')
p0 = Path.new('', 'A', 'B', 23)
n.add_path(p0)
p1 = Path.new('', 'A', 'C', 150)
p2 = Path.new('', 'A', 'D', 100)
p3 = Path.new('', 'A', 'E', 50)
n.add_path([p1, p2, p3]) # test multiple path addition
assert_equal(false, n.is_orphaned?)
assert_equal(true, n.path_count == 4)
assert_equal(50, n.cost('E'))
assert_equal(100, n.cost('D'))
assert_equal(150, n.cost('C'))
assert_equal(23, n.cost('B'))
p4 = Path.new('', 'A', 'E', 550) # duplicates p3 but new cost
# expect p3 to be replaced
# to keep, use a different name
# see test_get_routes below
n.add_path p4
assert_equal(true, n.path_count == 4)
assert_equal(Hash, n.paths.class)
assert_equal(550, n.cost('E'))
assert_equal(p4, n.path('E'))
assert_equal(p4, n.path(p4))
n.clear_paths
assert_equal(true, n.path_count == 0)
end
 
# Route tests ######################################
 
def test_route_creation
# origin --150--> middle --100--> destination
# destination --100--> middle --150--> origin
o = Node.new('origin')
m = Node.new('middle')
d = Node.new('destination')
po = Path.new('', 'origin', 'middle', 150)
pm = Path.new('', 'middle', 'destination', 100)
o.add_path po
m.add_path pm
 
r66 = Route.new('', o, d, [o, m, d])
assert_equal("#{o.name}_#{d.name}", r66.name)
assert_equal(250, r66.cost)
assert_equal([o, m, d], r66.nodes)
assert_equal(o, r66.origin)
assert_equal(d, r66.destination)
#
# The route reversal tests are excluded because there is a bug in there.
# Functionality not required for RPCFN3.
#
# TODO: fix route reversal problems
#
# r66rev = r66.reverse
# assert_equal("#{d.name}_#{o.name}", r66rev.name)
# assert_equal(250, r66.cost)
# assert_equal(Array, r66.nodes.class)
# assert_equal(Hash, r66.nodes.first.paths.class)
# assert_equal(Hash, r66.nodes.last.paths.class)
# assert_equal(Hash, r66.nodes[1].paths.class)
# assert_equal([d, m, o], r66rev.nodes)
# assert_equal(d, r66rev.origin)
# assert_equal(o, r66rev.destination)
 
assert_equal(2, r66.path_list.count)
assert_equal([po, pm], r66.path_list)
 
end
 
# Network tests ######################################
 
def test_empty_Network_creation
nw = Network.new
assert_equal(true, nw.is_empty?)
assert_equal(false, nw.has_node?('blob'))
assert_equal(false, nw.has_node?(Node.new('newNode')))
assert_equal(false, 'blob'.is_a_node_on(nw))
end
 
def test_Network_creation_with_import
nw = Network.new
nw.import(PATH_RPCFN3)
assert_equal(false, nw.is_empty?)
assert_equal(true, nw.has_node?('A'))
assert_equal(7, nw.node_count)
assert_equal(20, nw.path_count)
end
 
def test_manual_build_map
p1 = Path.new('', 'A', 'B', 150)
p2 = Path.new('', 'B', 'C', 50)
p3 = Path.new('', 'A', 'C', 250)
n1 = Node.new('A', [p1])
n1.add_path(p3)
n2 = Node.new('B', p2)
n2.add_path p1.reverse
n3 = Node.new('C', p2.reverse)
n3.add_path p3.reverse
 
map = Network.new('myMap', [n1, n2])
assert_equal(true, map.has_node?(n1))
assert_equal(n1, map.node(n1))
assert_equal(true, map.has_node?(n2))
assert_equal(false, map.has_node?(n3))
map.add_node(n3)
assert_equal(true, map.has_node?(n3))
assert_equal(n3, map.nodes[n3.name])
assert_equal(3, map.node_count)
assert_equal([n1, n2, n3], map.nodes.values)
assert_equal(6, map.path_count)
assert_equal(6, map.path_list.count)
assert_equal(p1, map.path_list.first)
assert_equal(p3, map.path_list[1])
assert_equal(p2, map.path_list[3])
end
 
def test_network_node_neighbors
nw = Network.new
nw.import(PATH_RPCFN3)
assert_equal(['B', 'D'], nw.neighbors('A').collect {|n| n.name})
end
 
def test_network_paths
nw = Network.new
nw.import(PATH_RPCFN3)
path_names = nw.path_list.collect {|p| p.name}
path_names.each {|pn| assert_equal(pn , nw.path(pn).name)}
end
 
def test_get_routes
nw = Network.new
nw.import(PATH_RPCFN3)
nw.get_routes(FROM, TO)
assert_equal(12, nw.route_count)
assert_equal(400, nw.min_cost)
assert_equal(1350, nw.max_cost)
assert_equal(1, nw.min_cost_routes.count)
assert_equal(1, nw.max_cost_routes.count)
# test a different set of start/end nodes, from B to A
nw.get_routes('B', 'A')
assert_equal(7, nw.node_count)
assert_equal(20, nw.path_count)
assert_equal(8, nw.route_count)
assert_equal(50, nw.min_cost)
assert_equal(1450, nw.max_cost)
assert_equal(1, nw.min_cost_routes.count)
assert_equal(1, nw.max_cost_routes.count)
 
# add another node B2 that connects B to A
# and has a total cost of 50 i.e. minimum
p1 = Path.new('', 'B', 'B2', 20)
nw.add_node(Node.new('B2'))
nw.node('B').add_path(p1)
nw.node('B2').add_path(p1.reverse)
p2 = Path.new('', 'B2', 'A', 30)
nw.node('B2').add_path(p2)
nw.node('A').add_path(p2.reverse)
nw.get_routes('B', 'A')
assert_equal(8, nw.node_count) # an extra node
assert_equal(24, nw.path_count) # 4 new paths
assert_equal(9, nw.route_count) # new route from B to B2 to A
assert_equal(50, nw.min_cost)
assert_equal(1450, nw.max_cost)
assert_equal(2, nw.min_cost_routes.count) # got 2 routes that are cheapest
assert_equal(1, nw.max_cost_routes.count)
 
# now add a new path from C to A that will result in 4 additional
# routes, one of which also has a maximum cost (1450)
p_heavy = Path.new('', 'C', 'A', 450)
nw.node('C').add_path(p_heavy)
nw.node('A').add_path(p_heavy.reverse)
nw.get_routes('B', 'A')
assert_equal(8, nw.node_count) # no change
assert_equal(26, nw.path_count) # 2 new paths
assert_equal(13, nw.route_count) # that extra path has introduced
# 4 new routes:
# BCA, BECA, BEGFCA and BEGFDCA
#
assert_equal(50, nw.min_cost)
assert_equal(1450, nw.max_cost)
assert_equal(2, nw.min_cost_routes.count)
assert_equal(2, nw.max_cost_routes.count) # got 2 routes that are most expensive
end
 
def test_get_routes_2
nw = Network.new
nw.import(PATHS_TO_ROME)
nw.get_routes('London', 'Rome')
assert_equal(14, nw.route_count)
assert_equal(1436, nw.min_cost)
assert_equal(6519, nw.max_cost)
assert_equal(1, nw.min_cost_routes.count)
assert_equal(1, nw.max_cost_routes.count)
nw.get_routes('Paris', 'Istanbul')
assert_equal(19, nw.route_count)
assert_equal(2333, nw.min_cost)
assert_equal(5624, nw.max_cost)
end
end

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.