Tracks that come to rest

The fitter who cleans a hotel lobby's rolling-ball sculpture has to drop a test ball somewhere it will stop. Some tracks never let go of one.

The problem

Steel balls run along numbered tracks. A flip-gate at the foot of a track tips the ball onto any one of the tracks it lists; a track with no gate ends in a catch-bowl, where the ball comes to rest.

A ball that enters a loop circles for ever. Call a track settling if a ball placed on it comes to rest however the gates fall; a bowl track settles by definition. List the settling tracks.

Input. gates — one list per track. gates[t] holds the tracks the gate on track t can tip a ball onto; an empty list means a bowl.

Output. The settling tracks, in ascending order.

Example.

gates = [[4], [3, 5], [0, 1], [2], [], [4], [5], []]   ->  [0, 4, 5, 6, 7]

Tracks 1, 2 and 3 form a loop. Track 2 can also reach bowl 4 through 0, but one bad route disqualifies it. Tracks 0, 5 and 6 end in bowl 4; 7 is a bowl.

A second example, where a track never stops without sitting on a loop:

gates = [[1], [2, 3], [1], [], [4, 3], [3]]   ->  [3, 5]

Track 0 is on no loop but feeds 1 and 2, which trade the ball back and forth. Track 4 lists itself.

Constraints.

• 1 <= len(gates) <= 10^4
• the lists hold at most 3 * 10^4 entries in total
• 0 <= gates[t][j] < len(gates); a track may list a track twice, or itself

Hints

Approach

Brute force

Walk every route from each track with a set of tracks seen; a repeat means a reachable loop. That is n walks of O(n + e): around 4·10⁸ steps for 10⁴ tracks and 3·10⁴ gate entries.

The insight

Turn every arrow round and peel from the bowls: keep one count of unsettled targets per track, and a track settles the moment its count reaches zero.

Reversing the arrows lets Hint 2's recurrence run forwards. Declaring a track settling retires one route from each track that tips onto it; at zero, every route out ends on a settling track. A track on a loop, or feeding one, keeps a live route for ever. This is the topological peel, reversed: what never sorts never settles.

Algorithm

1. For each target u in gates[t], record t as a feeder of u; set pending[t] = len(gates[t]).
2. Queue every track whose count is zero: the bowls.
3. Pop a track, mark it settling, and subtract one from each feeder's count; a feeder reaching zero joins the queue.
4. When the queue empties, return the marked tracks in ascending order.

Complexity

Time O(n + e) — each track is queued at most once, each gate entry subtracted once. Space O(n + e) for the reversed lists, counts and queue.

Solution

"""Tracks that come to rest — turn the arrows round and peel from the bowls."""

from collections import deque


def solve(gates):
    n = len(gates)
    feeders = [[] for _ in range(n)]      # feeders[u]: tracks whose gate can tip onto u
    pending = [0] * n                     # pending[t]: routes out of t not yet known to settle
    for track, targets in enumerate(gates):
        pending[track] = len(targets)     # repeats count twice here and are retired twice below
        for target in targets:
            feeders[target].append(track)

    # The bowls settle by definition; everything else has to earn it.
    queue = deque(t for t in range(n) if pending[t] == 0)
    settling = [False] * n
    while queue:
        # Invariant: every track in the queue has had all of its routes retired,
        # so every route out of it ends on a track already known to settle.
        track = queue.popleft()
        settling[track] = True
        for feeder in feeders[track]:
            pending[feeder] -= 1
            if pending[feeder] == 0:
                queue.append(feeder)

    # A track on a loop, or feeding one, keeps a live route for ever and stays False.
    return [t for t in range(n) if settling[t]]


CHAIN = [[t + 1] for t in range(9999)] + [[]]    # 10^4 tracks in a straight line

TESTS = [
    (([[4], [3, 5], [0, 1], [2], [], [4], [5], []],), [0, 4, 5, 6, 7]),
    (([[1], [2, 3], [1], [], [4, 3], [3]],), [3, 5]),
    (([[]],), [0]),                                  # one track, one bowl
    (([[0]],), []),                                  # one track tipping onto itself
    (([[1], [2], [0]],), []),                        # every track on the loop
    (([[1, 1], []],), [0, 1]),                       # the same target listed twice
    (([[1], [0], [], [2], [3, 0]],), [2, 3]),        # a loop and a chain side by side
    ((CHAIN,), list(range(10000))),                  # deep enough to break recursion
]

Pitfalls

• Settling a track because one route reaches a bowl. Track 2 in the first example reaches bowl 4 through 0 and the loop still catches it.
• Flagging only the tracks on a loop. Track 0 in the second example sits on none and still never stops; the peel catches feeders too.
• Peeling the right way round. Counting how many tracks tip onto each track, and starting from those nobody feeds, retires 6 and 7 in the first example and stalls short of bowl 4. Count routes out, from the bowls.
• Marking the routes recursively. A chain of 10⁴ tracks overflows Python's default recursion limit; the peel is a loop over a queue.

Variants

• Winters on the cut — the same peel forwards, counting layers.
• The tunnel to seal — undirected, with the loop found by union-find.