Skip to content

Instantly share code, notes, and snippets.

@cpjk
Created February 16, 2016 22:31
Show Gist options
  • Save cpjk/9ceecc9c98f0f301ea62 to your computer and use it in GitHub Desktop.
Save cpjk/9ceecc9c98f0f301ea62 to your computer and use it in GitHub Desktop.
def find_itinerary(pairs=[])
nodes = {} # hash with name as key and node as val
start_node = nil
pairs.each do |pair|
source_node = nodes[pair[0]] || Node.new(pair[0])
dest_node = nodes[pair[1]] || Node.new(pair[1])
source_node.add_dest(dest_node)
nodes[pair[0]] = source_node
nodes[pair[1]] = dest_node
start_node = source_node if source_node.val == "JFK"
end
return -1 unless start_node
nodes.values.each do |node|
node.outgoing_edges = node.outgoing_edges.sort_by { |edge| edge.dest_node.val }
end
visited = {}
path = []
curr_node = start_node
while true
path << curr_node.val
next_edge = find_next_edge(curr_node, visited)
visited[next_edge] = true
break unless next_edge
curr_node = next_edge.dest_node
end
path.empty? ? ["JFK"] : path
end
def find_next_edge(node, visited)
node.outgoing_edges.each do |edge|
if !visited[edge]
return edge
end
end
nil
end
class Node
attr_accessor :outgoing_edges, :val
def initialize(val)
@val= val
@outgoing_edges = []
end
def add_dest(dest_node)
outgoing_edges << Edge.new(dest_node)
end
end
class Edge
attr_accessor :dest_node
def initialize(dest_node="")
@dest_node = dest_node
end
end
pairs = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
puts find_itinerary(pairs)
puts ""
pairs = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
puts find_itinerary(pairs)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment