DCP41 - Destinations

'''
This problem was asked by Facebook.
Given an unordered list of flights taken by someone, each represented as (origin, destination) pairs, and a starting airport, compute the person's itinerary.
If no such itinerary exists, return null. If there are multiple possible itineraries, return the lexicographically smallest one.
All flights must be used in the itinerary.
For example, given the list of flights [('SFO', 'HKO'), ('YYZ', 'SFO'), ('YUL', 'YYZ'), ('HKO', 'ORD')] and starting airport 'YUL',
you should return the list ['YUL', 'YYZ', 'SFO', 'HKO', 'ORD'].
Given the list of flights [('SFO', 'COM'), ('COM', 'YYZ')] and starting airport 'COM', you should return null.
Given the list of flights [('A', 'B'), ('A', 'C'), ('B', 'C'), ('C', 'A')] and starting airport 'A', you should return the list
['A', 'B', 'C', 'A', 'C'] even though ['A', 'C', 'A', 'B', 'C'] is also a valid itinerary. However, the first one is lexicographically smaller.
'''

# 1st Function
def isThisCityFirst(flights, city):
    flag = False
    for i in range(len(flights)):
        if city == flights[i][0]:
            flag = True
            break
    return flag

# 2nd Function
def solve(flights, destination):
    flightsCopy = flights.copy()
    result = list()
    result.append(destination)

    while len(flightsCopy) > 0:
        # I have to check if the last city in my result exists as a first city in a flight
        flag = isThisCityFirst(flightsCopy, result[len(result)-1])
        if flag == False:
            print("There is not a solution with beginning city = '" + str(destination) + "'")
            return False
        else:
            # Now, that I know this city exists as first one of a trip, I have to search the next destination
            for flight in flightsCopy:
                if result[len(result)-1] == flight[0]:
                    result.append(flight[1])
                    flightsCopy.remove(flight)
                    break
    return result


# MAIN FUNCTION
flights1 = [('SFO', 'HKO'), ('YYZ', 'SFO'), ('YUL', 'YYZ'), ('HKO', 'ORD')]
destination1 = 'YUL'
print(str(flights1) + " and " + str(destination1) + " ----> " + str(solve(flights1, destination1)))
flights2 = [('A', 'B'), ('A', 'C'), ('B', 'C'), ('C', 'A')]
destination2 = 'A'
print(str(flights2) + " and " + str(destination2) + " ----> " + str(solve(flights2, destination2)))
flights3 = [('Thess', 'Athens'), ('Syros', 'Tinos'), ('Athens', 'Syros'), ('Larissa', 'Thess'), ('Falani', 'Larissa')]
destination3 = 'Falani'
print(str(flights3) + " and " + str(destination3) + " ----> " + str(solve(flights3, destination3)))