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
No comments :
Post a Comment