1
\$\begingroup\$

I came across the following problem (found on the SO link below): https://stackoverflow.com/questions/2991950/one-way-flight-trip-problem

Given a flight trip that includes a number of transfers: we have a ticket for each part of the trip; we do not stop twice in the same airport; each ticket contains source and destination airport; all the tickets we have are randomly sorted, and we forgot the original departure airport and the last destination. We want to design an algorithm to reconstruct the trip with minimum big-O complexity.

I tried to solve the problem in python in O(n) time complexity. Here is my solution:

L = [('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'E'), ('E', 'F'), ('F', 'G'), ('G', 'H'), ('H', 'I')]
# Note: the input L should normally be shuffled.

def getDepartureArrival(L):
    sources, destinations = zip(*L)
    sources = set(sources)
    destinations = set(destinations)

    for s in sources:
        if s not in destinations:
            depart = s
            break
    for d in destinations:
        if d not in sources:
            arriv = d
            break
    return depart, arriv
#

def getTrip(H):
    trip = [depart]
    k = depart
    while k != arriv:
        k = H[k]
        trip.append(k)
    return trip
#

depart, arriv = getDepartureArrival(L)
H = {s:d for (s,d) in L}
print getTrip(H)

I would like to know if it is possible to have a clearer and more compact Python code than the one I wrote with more than 4 consecutive loops.

\$\endgroup\$

migrated from stackoverflow.com Jan 6 '17 at 17:39

This question came from our site for professional and enthusiast programmers.

1
\$\begingroup\$

You should not use global variables when not necessary. You can just directly pass depart and arriv to getTrip.

You should strive to have readable variable names. Just use arrival and departure.

Python has an official style-guide, PEP8, which recommends using lower_case_with_underscore for variables and functions.

You can use map to cast both sources and destinations to sets directly. You can also use set subtraction to get the difference value only in one of them.

The dict constructor can directly take an iterable of pairs to build a dictionary.

You can make get_trip a generator, which simplifies the logic slightly.

I would add a if __name__ == "__main__": guard to allow importing stuff from this module without running the whole code.

import random


def get_departure_arrival(flights):
    """
    Find departure and arrival airport from chain of flights.

    Effectively the opposite of the itertools recipe pairwise:

    >>> get_departure_arrival([(s0, s1), (s1, s2), (s2, s3)])
    (s0, s3)

    Pairs do not have to be in order:

    >>> get_departure_arrival([(s0, s1), (s2, s3), (s1, s2)])
    (s0, s3)
    """
    sources, destinations = map(set, zip(*flights))

    depart = (sources - destinations).pop()
    arriv = (destinations - sources).pop()

    return depart, arriv


def get_trip(flights, depart, arriv):
    """
    Reconstruct a flight trip from pairs of departure and
    arrival airports and the first and last airport of the trip.
    """
    flight_dict = dict(flights)
    while depart != arriv:
        yield depart
        depart = flight_dict[depart]


if __name__ == "__main__":
    flights = [('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'E'),
               ('E', 'F'), ('F', 'G'), ('G', 'H'), ('H', 'I')]
    random.shuffle(flights)

    depart, arriv = get_departure_arrival(flights)
    print list(get_trip(flights, depart, arriv))
\$\endgroup\$
  • \$\begingroup\$ Thanks. Is there any improvement that can be made algorithmically speaking (to optimize runtime) ? A typo: the first arg in the definition of get_trip should be: flights. \$\endgroup\$ – eLearner Jan 6 '17 at 22:03
  • \$\begingroup\$ @eLearner Well, I already changed the algorithm slightly using the set logic. But a performance improvement we would need a bigger test sample. As it stands now, both versions take about 0.01s on my machine... \$\endgroup\$ – Graipher Jan 6 '17 at 22:14
  • \$\begingroup\$ @eLearner It is hard to make improvements without being able to profile the code to find bottlenecks, for which a realistic test sample is needed. \$\endgroup\$ – Graipher Jan 6 '17 at 22:15
  • \$\begingroup\$ It would be nice if the revised code had docstrings. \$\endgroup\$ – Gareth Rees Jan 8 '17 at 10:08
  • \$\begingroup\$ @GarethRees There you go, docstrings just for you ;-) \$\endgroup\$ – Graipher Jan 8 '17 at 10:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.