The Travel Tickets Problem

views:

338

answers:

+6 Q:

The Travel Tickets Problem

You are given a stack of travel tickets for various transportations that will take you from a point A to point B via several stops on the way. All of the tickets are out of order and you don't know where your journey starts, nor where it ends. Sort the tickets in the right order to complete your journey.
tickets = [
  {from: "Barcelona", to: "New York"}
  {from: "Barcelona", to: "Gerona"},
  {from: "Madrid",    to: "Barcelona"},
  {from: "Gerona",    to: "Barcelona"}
]

I suppose, the right order is that one:

tickets = [
  {from: "Madrid",    to: "Barcelona"},
  {from: "Barcelona", to: "Gerona"},
  {from: "Gerona",    to: "Barcelona"},
  {from: "Barcelona", to: "New York"}
]

Because there is no ticket to Madrid, and no ticket from New York.

What would be the best algorithm for that task?

The language is JavaScript, but language-agnostic solution would be good enough.

Update: I changed sample data to be not confused with One-way flight trip problem.

+1 A:

Isn't this just a doubly-linked list? Add each item to the list, linking each as appropriate; when you're done, you'll have two entries with unconnected links (one with nothing connected to its' "from" node, one without a connection at its' "to" node. These are the start- and end-points of the chain, and you read them out in sequence by starting with the entry lacking a "from" link, and following the link from one entry to the next.

Jonners 2010-06-23 12:17:35

That only holds if you're guaranteed that each City is visited at most once.

Chris 2010-06-23 12:41:34

True - my suggestion is based on the example given, rather than accomodating further unspecified conditions.

Jonners 2010-06-23 14:37:58

+1 A:

Create a directed graph from your tickets.
Find the node that has has indegree 0
Iterate over all nodes through graph edges to create your result

Update: With the added information in the original post, this solution does not solve the right problem. Look instead at IVLad's response.

kasperjj 2010-06-23 12:17:52

Some questions: are you thinking of a topological sort? if so how do you use all the edges? if not, can you detail 3.? **how** do you iterate?

IVlad 2010-06-23 12:23:27

Is that them there fancy tech talk for "find city in `from` list that doesn't appear in `to` list, then start tracing your route"? ;-)

scunliffe 2010-06-23 12:24:16

@IVlad I might have been assuming too much from the sample data in the post, but if there are more than one ticket sharing the same source node, then yes it would require a topological sort which would make my step 3 much less obvious :-)

kasperjj 2010-06-23 12:37:13

@scunliffe almost... I would probably build the directed graph using hashes giving me an O(n) solution instead of O(n^2) for a nested loop.

kasperjj 2010-06-23 12:44:34

I'm curious about what @scunliffe said, because I'd do the same thing.

Ionuț G. Stan 2010-06-23 12:45:05

+7 A:

If you can visit a node (a city) more than once, this is the eulerian path problem.

Here are two simple algorithms for solving it, depending on what type of graph you have. You have a recursive implementation on page 3 here.

IVlad 2010-06-23 12:21:46

+1 A:

What you've got is a directed graph, and you wish to find an Eulerian Path in it. The linked article describes the algorithm for finding one, which is basically:

Find a City with fewer routes in than out (if there are none, start anywhere)
Travel by a ticket (edge) which won't leave the graph disconnected if it isn't there; unless no such ticket exists, in which case use that ticket.
Delete the ticket (edge) and repeat

You should end up having used all the tickets, and at the end destination.

Chris 2010-06-23 12:23:10

ansaurus

tags:

views:

answers:

The Travel Tickets Problem

related questions