The pasted slips

A novelist wrote on loose slips and pasted new ones onto old. The typesetter has to read them in the order the pasting implies, which is not the order the archive filed them in.

The problem

An archive holds a working manuscript made of numbered slips. Each slip has two flaps: onto the first the novelist pasted the slip to be read before it, onto the second the slip to be read after it. Those pasted slips have flaps of their own, and either flap may be empty.

Accession numbers were given as the slips came out of the box, so they carry no reading order. Produce the numbers in the order a typesetter must set them.

The manuscript arrives in compact level-order form — the top slip, then each layer of pasted slips, before-flap first, with None for an empty flap. An empty flap has no flaps of its own, and trailing empties are trimmed.

Input. slips — the manuscript in compact level-order form.

Output. A list of accession numbers in reading order.

Example.

slips = [41, 8, 27, None, 63]   ->  [8, 63, 41, 27]

Slip 41 has slip 8 pasted before it and slip 27 after it. Slip 8 has an empty before-flap and slip 63 after it. So the typesetter reads 8, then 63, then 41, then 27.

A second example, where the filing order is exactly backwards:

slips = [50, 36, None, 19]   ->  [19, 36, 50]

Each slip here carries only a before-flap, so every slip is read ahead of the one it is pasted to. The archive lists 50 first; the typesetter sets it last.

Constraints.

• 0 <= slips <= 10^4
• 1 <= accession number <= 10^6, all distinct and in no particular order
• the pasting may form a single chain, so it can be 10^4 slips deep
• an empty manuscript returns an empty list

Hints

Approach

Brute force

Give every slip an address: the sequence of flaps followed from the top. Reading order is a rule about addresses — everything under a before-flap sorts ahead of the slip itself, everything under an after-flap behind it — so build all n addresses and sort the slips by them. Building costs O(n · h) and each comparison costs up to O(h): for a 10^4-slip chain, on the order of 10^8 character comparisons to recover an order the pasting already stores.

The insight

The manuscript already holds the reading order in its shape: read the whole before-branch, then the slip, then the whole after-branch, and every slip comes out exactly once, in order.

That walk is the pasting rule unrolled: true at the top slip by definition, true inside each branch for the same reason, so induction on the number of slips finishes it. The precondition is that the manuscript is a tree — each slip is pasted to at most one flap, so none is reachable two ways or written down twice.

Algorithm

1. Rebuild the manuscript, queueing only real slips so an empty flap claims no slots.
2. Start with an empty stack and the top slip in hand.
3. Push the slip in hand and follow its before-flap, pushing as you go, until the flap is empty.
4. Pop. Everything before that slip is already on the list, so write its number down.
5. Take its after-flap as the slip in hand and go back to step 3.
6. Stop when the stack is empty and there is no slip in hand.

Complexity

Time O(n) — each slip is pushed once and popped once. Space O(h) for the stack, where h is the deepest chain of pasting: about 14 for a balanced manuscript of 10^4 slips, and 10^4 for the chain in the second example.

Solution

"""The pasted slips — inorder walk of the manuscript with an explicit stack."""

from collections import deque


class Slip:
    """One slip: an accession number, the slip read before it and the one after."""

    __slots__ = ("number", "before", "after")

    def __init__(self, number):
        self.number = number
        self.before = None
        self.after = None


def build(level_order):
    """Rebuild the manuscript from its compact level-order form."""
    if not level_order or level_order[0] is None:
        return None
    root = Slip(level_order[0])
    queue = deque([root])
    i = 1
    while queue and i < len(level_order):
        # invariant: only real slips are queued, so an empty flap claims no slots
        node = queue.popleft()
        if i < len(level_order):
            value = level_order[i]
            i += 1
            if value is not None:
                node.before = Slip(value)
                queue.append(node.before)
        if i < len(level_order):
            value = level_order[i]
            i += 1
            if value is not None:
                node.after = Slip(value)
                queue.append(node.after)
    return root


def solve(slips):
    reading = []
    stack = []
    slip = build(slips)
    while stack or slip is not None:
        while slip is not None:
            # invariant: the stack holds slips whose own number is not yet written,
            # because everything pasted before them is still unread
            stack.append(slip)
            slip = slip.before
        slip = stack.pop()
        reading.append(slip.number)   # a pop means its before-branch is fully read
        slip = slip.after
    return reading

TESTS = [
    (([41, 8, 27, None, 63],), [8, 63, 41, 27]),
    (([50, 36, None, 19],), [19, 36, 50]),
    (([41, 8, 27, None, 63, 15, None, 5, 2],), [8, 5, 63, 2, 41, 15, 27]),
    (([],), []),
    (([7],), [7]),
    (([2, None, 4, None, 6, None, 9],), [2, 4, 6, 9]),
]

Pitfalls

• Writing the number down on the push. Recording a slip as it goes onto the stack gives [41, 8, 63, 27] for the first example — the top slip first, which is the one order the pasting rules out.
• Reading the level-order list straight through. The list is a storage layout, not a reading order: it answers [50, 36, 19] for the second example, exactly backwards.
• Recursing. The three-line recursive walk is fine on a balanced manuscript, but the constraints allow a 10^4-slip chain, and Python's default recursion limit is 1000, so it raises RecursionError.
• Letting an empty flap claim slots while rebuilding. A None has no flaps of its own; queueing it shifts every later number onto the wrong flap and the tail of the manuscript drops out of the reading.

Variants

• Refiling the drawer cabinet — the same walk used as a test: on an ordered index it has to come out increasing.
• Traversal families — the three walk orders side by side, and why moving one line changes which one you get.