-
-
Save RLGGHC/b19a4f95fd09e2a5bed3 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
=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' |
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
=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 | |
#format key is the cost, value is an array of matching routes | |
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 |
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
=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 | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment