secret
Last active

Solution to RPCFN challenge 3

  • Download Gist
paulsmith.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
# Challenge solution. Doesn't handle multiple shortest paths (just picks first
# one found, i.e. a node has a single predecessor on the shortest path, only
# overwritten when a shorter path is found).
#
# Assumes connections are bidirectional. Probably better to assume connections
# are directional, and double them up if they happen to be bidirectional.
#
# Problem statement consists of a graph with a start node and and end node.
# Node names are abitrary, so Start_node and End_node must be specified
 
 
Connections = [
[ :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]
]
 
Start_node = :A
End_node = :G
 
#Node class tracks a nodes name, shortest distance calcualted so far from Start_node, and
#the node's predecessor on that shortest path
class Node
attr_accessor :name, :distance, :predecessor
 
def initialize(name)
@name = name
end
end
 
class Graph
def initialize(connections)
@connections = connections
end
def shortest_path(from, to)
#Create a new node if we haven't seen that name before
nodes=Hash.new {|h, k| h[k] = Node.new(k)}
#queue consists of nodes to analyse. New nodes will be queued only if not previously on the queue
queue = [Start_node]
#queued is those nodes previously analysed
queued = []
nodes[from].distance = 0
while(!queue.empty?)
working_node = queue.shift
connections_from(working_node).each do |connection|
#Connections are bi-directional and may be specified either way around
if connection[0] == working_node
target = connection[1]
else
target = connection[0]
end
#shortest path length to target is shortest path length to here, plus final connection
#if that's shorter than anything discovered so far, store new shortest path and predecessor
path_distance = nodes[working_node].distance + connection[2]
if (nodes[target].distance.nil? || path_distance < nodes[target].distance)
nodes[target].distance = path_distance
nodes[target].predecessor = working_node
end
#queue any new neighbor nodes we haven't seen before
unless queued.include?(target)
queue.push(target)
queued.push(target)
end
end
end
# Nodes now labelled with minimal distance
# i.e. shortest path has been calculated if it exists
# if end node not discovered by now, there is no route from start to end
return nil unless nodes.has_key?(to)
 
# Backtrack from end node until we reach the start node
# (which we will do, as the end node was discovered)
shortest = []
working_node=to
until working_node == from
predecessor = nodes[nodes[working_node].predecessor]
# Again, connections are bidirectional and may be specified in either order.
shortest << @connections.select do |connection|
(connection[0] == working_node && connection[1] == predecessor.name) ||
(connection[1] == working_node && connection[0] == predecessor.name)
end[0]
working_node = predecessor.name
end
 
shortest
end
def connections_from(node_name)
@connections.select{|r| r[0] == node_name || r[1] == node_name}
end
def redundant_connections(from, to)
#Assumes all paths are redundant if shortest path does not exist
if (shortest = shortest_path(from, to)).nil?
return @connections
else
return @connections - shortest
end
end
end
 
g = Graph.new(Connections)
p g.redundant_connections(Start_node, End_node)

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.