Reassembling the tower clock

A church tower clock has been stripped to the frame for cleaning. The restorer's notebook says which part has to be back in before which, and nothing else.

The problem

The clock came apart into parts numbered pieces, 0 to parts - 1: great wheel, escapement, bushings, motion work, hands. Some physically block others — the pendulum cannot hang until the crutch is on.

The notebook records these as pairs. A pair [a, b] means piece a must go back before piece b. A piece with no pair pointing at it can go in whenever the restorer likes.

Produce one order in which every piece goes back into the frame without breaking a pair; any order that respects the notebook is acceptable. If the notebook contradicts itself — some piece is, through a chain of pairs, required before itself — return an empty list.

Input. parts — the number of pieces. before — a list of [a, b] pairs, each meaning a goes in before b.

Output. A list of all parts piece numbers in a valid reassembly order, or [] if no such order exists.

Example.

parts = 4
before = [[2, 0], [0, 3], [3, 1]]   ->  [2, 0, 3, 1]

Nothing points at piece 2, so it goes in first. That frees 0, which frees 3, which frees 1.

A second example, with two loose pieces, then stuck:

parts = 4
before = [[0, 1], [1, 2], [2, 1]]   ->  []

Pieces 0 and 3 go in without trouble. Then 1 waits for 2 and 2 waits for 1. Two pieces are still on the bench, so the answer is the empty list — not [0, 3].

Constraints.

• 1 <= parts <= 2000
• 0 <= len(before) <= 5000
• 0 <= a, b < parts and a != b
• the same pair may appear more than once

Hints

Approach

Brute force

Try every permutation of the pieces and check each against every pair. At parts = 2000 the number of orders has more digits than the notebook has pairs.

The insight

A piece with no unmet pair pointing at it can always go in next, and fitting it can only free other pieces, never block them.

Choosing such a piece cannot be wrong: nothing waits on it, so putting it in early breaks no pair. Repeat, and either every piece is eventually freed — that is the order — or the queue runs dry while pieces remain, each waiting on another remaining piece: a cycle, so no order exists.

Algorithm

1. Build frees[a], the pieces a unblocks, and waiting[b], the number of pairs pointing at b. Count duplicates twice on both sides.
2. Put every piece with waiting == 0 into a queue.
3. Pop a piece, append it to the order, and for each b in frees[piece] decrement waiting[b]; when it reaches zero, push b.
4. When the queue empties, return the order if it holds all parts pieces, otherwise [].

Complexity

Time O(parts + pairs) — each piece is queued once and each pair decrements one counter once. Space O(parts + pairs) for the lists, counts and queue.

Solution

"""Reassembling the tower clock — peel off the pieces nothing is waiting on."""

from collections import deque


def solve(parts, before):
    frees = [[] for _ in range(parts)]
    waiting = [0] * parts
    for a, b in before:
        frees[a].append(b)
        waiting[b] += 1             # one unit per pair, duplicates included

    ready = deque(p for p in range(parts) if waiting[p] == 0)
    order = []
    while ready:
        # Invariant: every piece in `order` has all its pairs satisfied, and
        # `ready` holds exactly the pieces whose every blocker is already in.
        piece = ready.popleft()
        order.append(piece)
        for b in frees[piece]:
            waiting[b] -= 1
            if waiting[b] == 0:
                ready.append(b)

    # A piece on a cycle keeps a positive count forever and is never appended,
    # so a short order is the whole cycle test.
    return order if len(order) == parts else []

TESTS = [
    ((4, [[2, 0], [0, 3], [3, 1]]), [2, 0, 3, 1]),
    ((4, [[0, 1], [1, 2], [2, 1]]), []),           # two loose pieces, then stuck
    ((1, []), [0]),                                 # a single piece
    ((3, [[0, 1], [1, 2], [2, 0]]), []),            # every piece on the cycle
    ((5, [[4, 3], [3, 2], [2, 1], [1, 0]]), [4, 3, 2, 1, 0]),   # chain against the numbering
    ((3, [[0, 1], [0, 1], [1, 2]]), [0, 1, 2]),     # the same pair written twice
    ((2, [[1, 0]]), [1, 0]),                        # the shortest possible chain
    ((2000, [[i, i + 1] for i in range(1999)]), list(range(2000))),   # the longest allowed chain
]

Pitfalls

• Returning the partial order on a cycle. Compare the length against parts; a short list such as [0, 3] looks like a valid answer and is not.
• Storing frees[a] as a set while counting waiting[b] per pair. A duplicated pair adds two to the count but subtracts one, so b never reaches zero and a sound notebook reports a cycle. Count pairs on both sides, or dedupe both.

Variants

• Winters on the cut — the same peeling, but a whole layer at a time, and the question is how many layers.
• Dye house shade index — the pairs are not given; they have to be read out of a sorted list first.