Timber stack tipping

The saw feeds thickest board first or the blade snatches. The only tool by the stack is a tipping arm that takes the top few boards and sets them back down inverted.

The problem

n planed boards sit on a pallet, milled to whole millimetres and no two alike, so the thicknesses are the integers 1 through n. The stack is given top down: stack[0] lifts off first, stack[-1] rests on the pallet.

The arm does one thing. Given k, it picks up the top k boards as a block, turns the block over and sets it back down — reversing the first k entries. It cannot pick up fewer than 2. The saw wants the thickest board on the pallet, so the list must end up ascending.

Many sequences sort a stack, so one rule makes the answer single-valued: working from the pallet upwards, take the thickest board not yet placed and do nothing if it already sits at its final depth; otherwise tip it to the top, unless it is there already, then tip it down into place.

Input. stack — a permutation of 1..n, top of the stack first.

Output. The k values given to the arm, in order; empty if the stack is already in saw order.

Example.

stack = [3, 2, 4, 1]   ->  [3, 4, 2, 3, 2]

A tip of 3 turns 3 2 4 over: 4 2 3 1. A tip of 4 turns the whole stack to 1 3 2 4, and board 4 is on the pallet for good. Tips of 2, 3 and 2 finish the rest.

A second example, one tip:

stack = [3, 2, 1]      ->  [3]

Board 3 is already topmost, so nothing is needed to reach it; one tip of the whole stack sends it to the pallet and sorts the rest on the way.

Constraints.

• 0 <= n <= 100, stack is a permutation of 1..n
• every reported k satisfies 2 <= k <= n
• at most 10n tips

Hints

Approach

Brute force

Search for the shortest sequence breadth-first over stack states. Every permutation is a state: 8 boards give 40 320 and 13 give 6 × 10⁹, against a limit of 100.

The insight

Two tips park any board at any depth, and a tip can never disturb a board deeper than the block it lifts — so place the thickest board first, then forget it exists.

Bring the thickest unplaced board up with one tip, then tip a block of exactly the current working size so it lands at the bottom of that block. Every later tip uses a smaller k and stops short of it. That is selection sort with the arm standing in for a swap: at most two tips for each of n - 1 boards, which is 2n - 2, well inside the budget of 10n.

Algorithm

1. For size from n down to 2, find board size among the top size.
2. If it sits at index size - 1 it is placed; do nothing.
3. Otherwise, unless it is at index 0, tip index + 1 to bring it up.
4. Tip size to send it to index size - 1.

Complexity

Time O(n²) — each of n rounds scans and reverses a prefix. Space O(n) for the working copy and the list of tips.

Solution

"""Timber stack tipping — place the thickest board with at most two prefix flips."""


def solve(stack):
    boards = list(stack)
    tips = []
    # Invariant: after handling working size s, boards[s:] holds the thickest
    # boards in final order, and no later tip reaches past index s-1, so a
    # placed board is never disturbed again.
    for size in range(len(boards), 1, -1):
        deepest = size - 1
        here = boards.index(size, 0, size)
        if here == deepest:
            continue                       # already at its final depth
        if here > 0:
            tips.append(here + 1)          # bring it to the top of the stack
            boards[:here + 1] = reversed(boards[:here + 1])
        tips.append(size)                  # send it down to depth size - 1
        boards[:size] = reversed(boards[:size])
    return tips

TESTS = [
    (([3, 2, 4, 1],), [3, 4, 2, 3, 2]),
    (([3, 2, 1],), [3]),
    (([1, 2, 3, 4],), []),
    (([1],), []),
    (([2, 1],), [2]),
    (([1, 3, 2],), [2, 3, 2]),
    (([],), []),
]

Pitfalls

• Tipping index instead of index + 1 leaves the board one place down instead of on top: on [3, 2, 4, 1] a tip of 2 gives 2 3 4 1, and board 4 has not moved.
• Searching the whole stack for the thickest board rather than the top size drags the board you just placed back up, so the loop never finishes.
• Recording a tip of 1 when the board is already on top reports a move the arm cannot make.
• Returning the sorted stack gives the yard a destination when it needs moves.

Variants

• Booth changeover run — order as the output again, reachable with one library sort.
• Order as a key — the lesson on why most ordering questions collapse to a key.