w3resource

Python Challenges: Compute the person's itinerary from a given unordered list of flights

Python Challenges - 1: Exercise-55 with Solution

Given an unordered list of flights taken by someone, each represented as (origin, destination) pairs, and a starting airport.
Write a Python program to 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.

Sample Solution:

Python Code:

def intinerary(llist, start):
    #Ref.https://bit.ly/2Pb67Bk    
    itinerary_list = []
    itinerary_list.append(start)

    while len(llist) >= 1:
        current = None
        directions = {}

        for item in llist:
           
            if item[0] == start:
                directions[item[0]] = item[1]

        if len(directions) >= 1:
            current = min(directions.values())
            remove_tuple = (start, current)

        try:
            llist.remove(remove_tuple)
            itinerary_list.append(current)
            start = current
        except:
            return "not valid intinerary"

    return itinerary_list


print(intinerary([('SFO', 'HKO'), ('YYZ', 'SFO'), ('YUL', 'YYZ'), ('HKO', 'ORD')], 
    'YUL'))

print(intinerary([('SFO', 'COM'), ('COM', 'YYZ')], 
    'COM'))

print(intinerary([('A', 'B'), ('A', 'C'), ('B', 'C'), ('C', 'A')], 
    'A'))

Sample Output:

['YUL', 'YYZ', 'SFO', 'HKO', 'ORD']
not valid intinerary
['A', 'C', 'A', 'B', 'C']

Flowchart:

Python Flowchart: Compute the person's itinerary from a given unordered list of flights.

Python Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a Python program to find the largest palindrome made from the product of two 4-digit numbers.
Next: Write a Python program to print a truth table for an infix logical expression.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Become a Patron!

Follow us on Facebook and Twitter for latest update.

It will be nice if you may share this link in any developer community or anywhere else, from where other developers may find this content. Thanks.

https://198.211.115.131/python-exercises/challenges/1/python-challenges-1-exercise-55.php