The branch van rota

A library service books its van a day at a time. Each booking is one run from one branch to another, and the driver has to do all of them in one day.

The problem

runs is a list of pairs [pick_up, drop_off]: one booked run, one way only. The same pair may be booked more than once.

The van starts at store, and every run it makes has to begin where the last one ended. The rota uses every booking exactly once; at least one such rota exists. When several work, the service takes the one whose branch names read smallest, compared branch by branch from the start.

Input. runs — a list of [pick_up, drop_off] name pairs. store — the branch the van starts at.

Output. The branches in order, one more of them than there are runs.

Example.

runs = [["STORE", "BEECH"], ["STORE", "ASH"], ["BEECH", "ASH"],
        ["ASH", "STORE"], ["ASH", "BEECH"]]
store = "STORE"
  ->  ["STORE", "ASH", "BEECH", "ASH", "STORE", "BEECH"]

Five runs, six stops. ASH is taken first because it reads smaller, and the day ends at BEECH with nothing booked out of it.

A second example, where taking the smaller name first strands the van:

runs = [["STORE", "ASH"], ["STORE", "BEECH"], ["BEECH", "STORE"]]
store = "STORE"
  ->  ["STORE", "BEECH", "STORE", "ASH"]

ASH is the earlier name, but nothing is booked out of it, so a van that drives there first ends the day with two bookings unused. Only a rota finishing at ASH works.

Constraints.

• 1 <= len(runs) <= 5000
• branch names are short strings of capital letters
• at least one rota using every booking exists
• store is the pick-up of at least one booking

Hints

Approach

Brute force

Try the bookings in every order and keep the smallest that joins up. Ten runs is already 3.6 million orders, and the van does up to 5000.

The insight

Drive greedily until the van sticks, and the branch it sticks at can only be the last stop of the day: write it down, step back one branch and carry on, so the rota is built from its end backwards.

Every branch other than the start and the finish has as many bookings in as out, because the van leaves each time it arrives and a rota is guaranteed to exist. So arriving at such a branch always leaves a way out, and the only place the van can strand is the finish. Stepping back fills in the loops the greedy drive drove past, and each booking is used once because it is removed as it is taken.

Algorithm

1. Group the bookings by pick-up branch, each group sorted so the earliest name comes off first.
2. Push store on a stack.
3. While the branch on top still has a booking, remove it and push its drop-off.
4. When the branch on top has none left, pop it onto the rota.
5. Reverse the rota once the stack empties.

Complexity

Time O(R log R) — the sort dominates; each booking is taken once and each branch popped once. Space O(R) for the grouping, the stack and the rota.

Solution

"""The branch van rota — Hierholzer's walk, stitched on from the far end."""

from collections import defaultdict


def solve(runs, store):
    onward = defaultdict(list)
    for pick_up, drop_off in sorted(runs, reverse=True):
        onward[pick_up].append(drop_off)   # descending, so pop() takes the earliest name

    rota = []
    stack = [store]
    while stack:
        while onward[stack[-1]]:
            stack.append(onward[stack[-1]].pop())   # drive on while a run is left here
        rota.append(stack.pop())    # nothing left: this branch can only be the last one
    return rota[::-1]


_CHAIN = [["STORE", "B0000"]] + [["B%04d" % i, "B%04d" % (i + 1)] for i in range(999)]

TESTS = [
    (([["STORE", "BEECH"], ["STORE", "ASH"], ["BEECH", "ASH"],
       ["ASH", "STORE"], ["ASH", "BEECH"]], "STORE"),
     ["STORE", "ASH", "BEECH", "ASH", "STORE", "BEECH"]),
    (([["STORE", "ASH"], ["STORE", "BEECH"], ["BEECH", "STORE"]], "STORE"),
     ["STORE", "BEECH", "STORE", "ASH"]),      # the earliest name first would strand the van
    (([["STORE", "ASH"]], "STORE"), ["STORE", "ASH"]),
    (([["STORE", "ASH"], ["ASH", "BEECH"], ["BEECH", "STORE"], ["STORE", "CEDAR"]], "STORE"),
     ["STORE", "ASH", "BEECH", "STORE", "CEDAR"]),
    (([["STORE", "ASH"], ["ASH", "STORE"]], "STORE"), ["STORE", "ASH", "STORE"]),
    # 1000 runs in a line: the walk keeps its own stack.
    ((_CHAIN, "STORE"), ["STORE"] + ["B%04d" % i for i in range(1000)]),
]

Pitfalls

• Driving greedily and never backing up. The second example ends at BEECH with a booking unused, and no rota starts STORE, ASH.
• Writing branches down as the van drives rather than as it sticks. That records the order they were entered, not the order the runs join up in: the second example comes out STORE, ASH, BEECH, STORE.
• Leaving a booking in the group after taking it. The van drives the same run for ever and the rota never ends.

Variants

• The cold store keyring — a walk asked only what it can reach, with no duty to use every edge.
• BFS and DFS — the same stack, popping in the same order, answering a different question.