Reconstruct an itinerary with Eulerian paths

To reconstruct an itinerary from a pile of used tickets is to find an Eulerian path: a route through a graph that uses every edge exactly once. Stations are the nodes and tickets the directed edges. Such a route exists only when every station has as many tickets in as out, except that the start may have one more out and the end one more in. Hierholzer’s algorithm then builds the route in linear time, and taking each station’s alphabetically smallest ticket first makes it the alphabetically first itinerary.

The problem: a trip rebuilt from its ticket stubs

A traveller kept the stub of every ticket of a rail trip. Each stub names the station the leg left from and the station it reached, as three-letter codes. The trip began at a known station and used every ticket exactly once. Rebuild the stations in order. When several orders are possible, return the one that comes first alphabetically, comparing station by station. A trip always exists, and the same ticket may appear twice. Limits: 1 to 10,000 tickets.

1. AMB → BRK, BRK → CAS, CAS → AMB, AMB → DAL from AMB gives AMB BRK CAS AMB DAL.
2. AMB → BRK, AMB → CAS, CAS → AMB from AMB gives AMB CAS AMB BRK, although BRK comes before CAS.
3. AMB → BRK, BRK → AMB, AMB → BRK from AMB gives AMB BRK AMB BRK: the repeated ticket is used twice.

The brute force, and why it fails at these sizes

Try every order of the tickets, keep the orders in which each leg starts where the one before it ended, and return the alphabetically first trip among them.

"""The brute force: every order of the tickets, keeping the alphabetically first one that makes a trip. The work is
counted, not timed, so every computer prints the same."""
from itertools import permutations


def first_trip(tickets, start):
    tried, best = 0, None
    for order in permutations(tickets):
        tried += 1
        here, stations = start, [start]
        for a, b in order:
            if a != here:
                break
            stations.append(b)
            here = b
        else:  # every ticket was used, each leg starting where the last one ended
            best = stations if best is None else min(best, stations)
    return best, tried


print("example 1:", " ".join(first_trip([("AMB", "BRK"), ("BRK", "CAS"), ("CAS", "AMB"), ("AMB", "DAL")], "AMB")[0]))
print("example 2:", " ".join(first_trip([("AMB", "BRK"), ("AMB", "CAS"), ("CAS", "AMB")], "AMB")[0]))
print("example 3:", " ".join(first_trip([("AMB", "BRK"), ("BRK", "AMB"), ("AMB", "BRK")], "AMB")[0]))
print("tickets   orders tried")
for n in (6, 7, 8):
    loop = [(f"S{i}", f"S{(i + 1) % n}") for i in range(n)]  # one round trip through n stations
    print(f"{n:>7}   {first_trip(loop, 'S0')[1]:>12,}")
print("one more ticket multiplies the orders: 10 give 3,628,800, 20 about 2.4 x 10^18, 10,000 a number of 35,660 digits")

example 1: AMB BRK CAS AMB DAL
example 2: AMB CAS AMB BRK
example 3: AMB BRK AMB BRK
tickets   orders tried
      6            720
      7          5,040
      8         40,320
one more ticket multiplies the orders: 10 give 3,628,800, 20 about 2.4 x 10^18, 10,000 a number of 35,660 digits

It is right on the examples, but n tickets have n! orders: 40,320 for 8 tickets, 3,628,800 for 10, and for 10,000 tickets a number with 35,660 digits. Most of those orders break at the first leg, and still the count alone rules the method out.

What to notice

• It is a graph problem. A trip that uses every ticket once is a path that uses every edge once.
• Counting decides where it ends. A station the trip passes through is left as often as it is entered, so only the start can have an extra ticket out and only the end an extra ticket in.
• The smallest ticket is not always the next leg. In example 2, AMB → BRK leads to the station where the trip must end, so it has to be used last.

Four techniques follow from these signals, and two variants use them:

• Degree counting compares tickets in and out of every station, to check that a trip exists and where it ends.
• Hierholzer’s algorithm walks along unused tickets and writes a station down once it has no ticket left.
• Sorted ticket lists make the trip it builds the alphabetically first one.
• An explicit stack replaces the recursion, so 10,000 tickets in a row need no deep call stack.
• The variants walk two-way streets with numbered edges and build the shortest string that holds every lock code.

When a trip exists: tickets in and out Pro: opens with a Pro, Premium or Ultimate pass