Showing posts with label airline. Show all posts
Showing posts with label airline. Show all posts

Wednesday, June 10, 2015

Reconstruct the itinerary in order


Given an bunch of airline tickets with [from, to], for example [MUC, LHR], [CDG, MUC], [SFO, SJC], [LHR, SFO]
please reconstruct the itinerary in order, 
[ CDG, MUC, LHR, SFO, SJC ]. 
Note: tickets can be represented as nodes

#!/usr/bin/env python

import sys

# Reads the given file which contains airline tickets
# and returns 2 hash,
#  * (1) with all the ticket info
#  * (2) wth the starting and ending points
def getTicketsFromFile(filename):
    lines = []

    # Read the file
    with open(filename, "r") as fp:
        lines = lines = fp.readlines()

    lines = map(lambda s: s.strip(), lines)

    tickets = {}
    points = {}
    for line in lines:
        if line !="":
            point = map(lambda s: s.strip(), line[1:-1].split(","))
            tickets[point[0]] = point[1]

            # create 2 nodes for each ticket (start, end) and
            # do this for all the tickets
            for p in point:
                try:
                    # Delete the key from the points if it exists to find the start and end
                    # points for the entire trip.
                    del points[p]
                except:
                    points[p] = ""

    # Find the starting point
    for k in points.keys():
        if k in tickets.keys():
            startPoint = k
            break
        
    return (tickets, startPoint)


if __name__ == "__main__":
    (tickets, startPoint) = getTicketsFromFile(sys.argv[1])

    # print the order
    point = startPoint
    while True:
        print point,
        
        try:
            point = tickets[point]
        except:
            break