The itinerary in the tickets

Problem

Ruth inherited an envelope with the train tickets from a trip her grandmother took sixty years ago, and she wants to piece the route back together. Each ticket says which city it leaves from and which city it arrives at, but inside the envelope they ended up all shuffled.

Write a function that takes tickets, a list of lists of two strings:

the first one is the city that ticket leaves from and the second one the city it arrives at. There are 1 to 20 tickets and they come in any order. Her grandmother's trip never repeated a city: each city is the departure of a single ticket or of none, and the arrival of a single ticket or of none. All the tickets together make one single trip in a row: none is left over and there are no two separate trips.

Names are compared whole: two cities are the same one only if the name is the same from beginning to end. "Newport" and "Newport News" are two different cities, even though one starts like the other.

And since the trip is one single trip in a row, there is exactly one city that is not the arrival of any ticket: that is the one her grandmother left from.

Return the list of the cities of the trip in order, starting with the city her grandmother left from and ending at the last one she arrived at. With one ticket there are two cities, with two tickets there are three, and so on.

With [["Lyon", "Turin"], ["Paris", "Lyon"], ["Turin", "Rome"]] you return ["Paris", "Lyon", "Turin", "Rome"]. Check it: the Paris ticket arrives at Lyon, the Lyon one at Turin and the Turin one at Rome; all three are used and no city is repeated.

Examples

• The example

  [["Lyon", "Turin"], ["Paris", "Lyon"], ["Turin", "Rome"]] → ["Paris", "Lyon", "Turin", "Rome"]

• A single ticket

  [["Dover", "Canterbury"]] → ["Dover", "Canterbury"]

• The tickets already came in order

  [["Oxford", "Reading"], ["Reading", "Bath"], ["Bath", "Exeter"]] → ["Oxford", "Reading", "Bath", "Exeter"]

Besides these, the challenge has hidden tests that are revealed when you submit your solution.

You start with this

def itinerary(tickets):
    pass

function itinerary(tickets) {
}