The Travel Tickets Problem

Question

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.

Must you go through all of the cities? Must you use all of the tickets? — IVlad, Jun 23 '10 at 12:10
Are you a lazy travel agent with too many tickets at hand? ;-) — kasperjj, Jun 23 '10 at 12:18
@NV, if it's a job interview, are you allowed to get outside help? I mean, you're the one who's applying for the job, right? — Bart Kiers, Jun 23 '10 at 12:21
Probably easiest done by sorting the tickets after start time of the flight. Although that would sort of cheating ;) — Dirk Vollmar, Jun 23 '10 at 12:32
@NV: why don't you add the `job-interview` and/or the `interview-questions` tags? — MarcoS, Jun 23 '10 at 12:52
I actually voted for closing before I realized it's not the same question. Can't undo it. — NVI, Jun 23 '10 at 15:17

score 8 · Accepted Answer · answered Jun 23 '10 at 12:21

8

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.

answered Jun 23 '10 at 12:21

IVlad

43,099
13
111
179

score 1 · Answer 2 · answered Jun 23 '10 at 12:17

1

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.

answered Jun 23 '10 at 12:17

Eight-Bit Guru

9,756
2
48
62

That only holds if you're guaranteed that each City is visited at most once. – Chowlett Jun 23 '10 at 12:41
True - my suggestion is based on the example given, rather than accomodating further unspecified conditions. – Eight-Bit Guru Jun 23 '10 at 14:37

score 1 · Answer 3 · edited May 23 '17 at 12:07

1

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.

edited May 23 '17 at 12:07

Community

1
1

answered Jun 23 '10 at 12:17

kasperjj

3,632
27
25

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 Jun 23 '10 at 12:23
2

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 Jun 23 '10 at 12:24
@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 Jun 23 '10 at 12:37
@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 Jun 23 '10 at 12:44

score 1 · Answer 4 · answered Jun 23 '10 at 12:23

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.

score 0 · Answer 5 · answered Mar 21 '16 at 08:18

The following is a sample of the javascript implementation.

var un  =
[
 { from:'c',to:'d'},
 { from:'a',to:'b'},
 { from:'b',to:'c'},
 { from:'z',to:'a'},
 { from:'d',to:'m'},
]

function buildTable( un ){
return un.reduce(function(previousValue, currentValue, currentIndex ){

//build the table.
    previousValue.from[currentValue['from']] = currentValue;
    previousValue.to[currentValue['to']] = currentValue;

//to find start and end.    
    if( !previousValue.from[currentValue['to']] )  previousValue.from[currentValue['to']]= false;
    if(!previousValue.to[currentValue['from']])  previousValue.to[currentValue['from']]= false;

    return previousValue;

},{to:{},from:{}} );


}

function getStart(nodes){
//find start node indx.
    for(var i  in nodes)
    if( !nodes[i] )return i;
}


function print(start,nodes ){


var sorted = [];
//while detecting false from buildTable structure.
    while(start){
        var  node = nodes[start];
        sorted.push(node)
        start = node['to'];
//console.log(start)
    }

return sorted;
}

var sorted = buildTable(un);
console.log(print(getStart(sorted.to),sorted.from));

score 0 · Answer 6 · answered Jun 24 '22 at 10:19

There wouldn't be a ticket to a beginning destination. So at 1st I would find the beginning destination by comparing entries of "from" with entries of "to". So we get the 1st ticket
add 1st ticket to a new list (aka sortedList)
in a while loop add ticketList ticket where "from" equals to sortedList last ticket "to" until you get the same length of ticketList and sortedList

Here is the code in Dart for a similar task:

  Map<String, String> ticket1 = {'from': 'st_p','to':'msc'}; //1
  Map<String, String> ticket2 = {'from': 'izh','to':'sam'}; //3
  Map<String, String> ticket3 = {'from': 'kzn','to':'sch'}; //5
  Map<String, String> ticket4 = {'from': 'sam','to':'kzn'}; //4
  Map<String, String> ticket5 = {'from': 'msc','to':'izh'}; //2
  
  List<Map<String, String>> tickets = [ticket1,ticket2,ticket3,
                                       ticket4,ticket5];
  
  List<String> citiesFrom = [];
  List<String> citiesTo = [];
  
  for (var ticket in tickets) {
    citiesFrom.add(ticket['from']!);
    citiesTo.add(ticket['to']!);
  }
  
  String beginDestination = citiesFrom.firstWhere(
    (element) => !citiesTo.contains(element));
  
  List<Map> sortedTickets = [];
  
  sortedTickets.add(tickets.firstWhere(
    (element) => element['from']==beginDestination));
  
  while(sortedTickets.length != tickets.length) {
    sortedTickets.add(
      tickets.firstWhere(
        (element) => element['from']==sortedTickets.last['to'])
    );
  }
  
  print(sortedTickets);

score -1 · Answer 7 · edited Jun 10 '21 at 06:59

    function fullPath(path) {
    let startingPoints = [];
    let endingPoints = [];
    let result = [];

    for (let i = 0; i < path.length; i++) {
        startingPoints.push(path[i].from);
        endingPoints.push(path[i].to);
    }

    for (let i = 0; i < path.length; i++) {
        if (!endingPoints.includes(path[i].from)) {
            result.push(path[i].from);
            break;
        }
    }

    for (let i = 0; i < path.length; i++) {
        if (startingPoints.includes(result[i])) {
            let indexOfPoint = startingPoints.indexOf(result[i]);
            result.push(endingPoints[indexOfPoint]);
        }
    }
    return result;

}

The Travel Tickets Problem

7 Answers7