Two dead-end sidings

A depot can only reach one end of a siding, yet the yard master has promised to release wagons in the order they arrived.

The problem

The depot has two dead-end sidings. A wagon rolls on at the open end and leaves from that same end, so the one that went on last is the only one you can take off: each siding alone is last in, first out. A wagon at the top of one siding can be rolled across to the top of the other. The contract with the freight line, though, is first in, first out. Simulate a shift and report the depot log.

Input. ops — a list of tuples, in order:

• ("arrive", w) — wagon w rolls into the depot.
• ("depart",) — the wagon that has waited longest leaves; log its number.
• ("front",) — log which wagon would leave next, moving nothing out.
• ("waiting",) — log how many wagons are still in the depot.

Output. The logged numbers, in the order they were logged.

Example.

ops = [("arrive", 7), ("arrive", 4), ("front",), ("depart",),
       ("arrive", 9), ("depart",), ("waiting",), ("depart",)]
  ->  [7, 7, 4, 1, 9]

Wagons 7 and 4 land on the arrival siding, and front needs the bottom one, so the siding is poured across to the second, which reverses it and leaves 7 on top. Wagon 9 arrives while 4 still sits on the release siding — it must not join it there, or it would leave first.

A second example, where the depot empties and refills:

ops = [("arrive", 2), ("depart",), ("arrive", 5), ("arrive", 8),
       ("front",), ("depart",), ("front",), ("depart",), ("waiting",)]
  ->  [2, 5, 5, 8, 8, 0]

Wagon 2 empties the release siding on its way out, so 5 and 8 cross later as a fresh batch.

Constraints.

• 1 <= len(ops) <= 10^5
• 1 <= w <= 10^6
• depart and front never appear while the depot is empty.
• Wagon numbers need not be distinct.

Hints

Approach

Brute force

Keep every wagon on one siding and use a spare track: to release the bottom wagon, roll the k above it onto the spare, take it, roll all k back. That is 2k moves per departure, so a half-full depot serving 10^5 departures costs on the order of 10^10 wagon-moves.

The insight

Reversing a last-in-first-out siding once turns it into first-in-first-out, and if you pour only when the release siding is empty, every wagon is reversed exactly once.

The wagons on the release siding are already in departure order, and everything on the arrival siding arrived after them, so nothing may be poured on top while any remain. The moment it empties that constraint lifts and one pour orders the whole batch. Each wagon is then pushed on, pulled off, pushed across and pulled off: four moves, whatever the shift does around it.

Algorithm

1. Keep inbound (arrivals, newest on top) and outbound (departures, oldest on top).
2. arrive pushes onto inbound.
3. depart and front check outbound; if it is empty, pour all of inbound across one wagon at a time.
4. depart pops outbound; front reads its top.
5. waiting logs the two sizes added.

Complexity

Time O(1) amortised per operation, O(n) for a shift of n operations — one departure can move k wagons, but the k arrivals that put them there already paid for it. Space O(n) for the wagons on the two sidings.

Solution

"""Two dead-end sidings — a first-in-first-out depot built from two stacks."""


def solve(ops):
    inbound, outbound = [], []      # inbound: newest wagon on top. outbound: oldest on top.
    log = []

    def spill():
        # Invariant: outbound is empty, or its top is the wagon that has waited
        # longest. Pouring only into an empty outbound reverses each batch once,
        # so no wagon is ever moved backwards and every wagon crosses at most once.
        if not outbound:
            while inbound:
                outbound.append(inbound.pop())

    for op in ops:
        move = op[0]
        if move == "arrive":
            inbound.append(op[1])
        elif move == "depart":
            spill()
            log.append(outbound.pop())
        elif move == "front":
            spill()
            log.append(outbound[-1])
        else:                       # "waiting"
            log.append(len(inbound) + len(outbound))

    return log

TESTS = [
    (
        (
            [
                ("arrive", 7), ("arrive", 4), ("front",), ("depart",),
                ("arrive", 9), ("depart",), ("waiting",), ("depart",),
            ],
        ),
        [7, 7, 4, 1, 9],
    ),
    (
        (
            [
                ("arrive", 2), ("depart",), ("arrive", 5), ("arrive", 8),
                ("front",), ("depart",), ("front",), ("depart",), ("waiting",),
            ],
        ),
        [2, 5, 5, 8, 8, 0],
    ),
    # Arrivals land while the release siding still holds wagons: they must wait
    # behind them, not be poured on top.
    (
        (
            [
                ("arrive", 11), ("arrive", 12), ("arrive", 13), ("depart",),
                ("arrive", 14), ("depart",), ("arrive", 15), ("depart",),
                ("depart",), ("depart",), ("waiting",),
            ],
        ),
        [11, 12, 13, 14, 15, 0],
    ),
    # One wagon, in and straight out.
    (([("arrive", 3), ("front",), ("depart",), ("waiting",)],), [3, 3, 0]),
    # Repeated wagon numbers, and a depot that drains twice.
    (
        (
            [
                ("arrive", 6), ("arrive", 6), ("depart",), ("depart",),
                ("arrive", 6), ("waiting",), ("depart",), ("waiting",),
            ],
        ),
        [6, 6, 1, 6, 0],
    ),
]

Pitfalls

• Pouring when the release siding is not empty. With 5 and 4 waiting there (5 on top) and wagon 3 arriving, an unconditional pour drops 3 above 5, so the next departure logs 3 — the wagon that has waited least.
• Pouring everything back after each departure to reset the depot. The order stays right, but every departure moves the whole depot twice and 10^5 operations turn back into billions of moves.
• Serving front from the arrival siding. inbound[-1] is the newest wagon, the exact opposite of the answer; on the first example it logs 4, not 7.

Variants

• Queues and amortised cost — the lesson behind the pour-once argument.
• The next lot to beat it — a stack read for what is still unresolved, rather than reversed into a queue.