find_itinerary.rb

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)