PythonPlayground/find_itinerary.py at master · CipherCartographer/PythonPlayground · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
'''
Given a list of tickets, find itinerary in order using the given list.

Example:

Input:
"Chennai" -> "Banglore"
"Bombay" -> "Delhi"
"Goa"    -> "Chennai"
"Delhi"  -> "Goa"

Output:
Bombay->Delhi, Delhi->Goa, Goa->Chennai, Chennai->Banglore,
It may be assumed that the input list of tickets is not cyclic and there is one ticket from every city except final destination.
'''

def findItinerary(ticket_map):
    if ticket_map is None:
        return None

    reverse_map = {}
    # Reverse the ticket map
    for key in ticket_map:
        reverse_map[ticket_map[key]] = key

    start = None
    for key in ticket_map.keys():
        if key not in reverse_map.keys():
            start = key
    to = ticket_map[start]
    print "Final Itinerary: "
    print start,
    while to is not None:
        print "->" + to,
        start = to
        if to in ticket_map:
            to = ticket_map[to]
        else:
            to = None


if __name__ == "__main__":
    ticket_map = {}
    ticket_map["Chennai"] = "Banglore"
    ticket_map["Bombay"] = "Delhi"
    ticket_map["Goa"] = "Chennai"
    ticket_map["Delhi"] = "Goa"

    print "Ticket map : ",
    print ticket_map

    findItinerary(ticket_map)