THE FOLD / CHEAT / THE KONAMI CODE / THE PANCAKE SORTING
THE PANCAKE SORTING
sort by prefix flips — Bill Gates' only paper
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Pancake sorting: you have a stack of differently-sized pancakes and a spatula, and the only move is to insert the spatula somewhere and flip the whole top portion. How few flips sort the stack largest-on-bottom?
The greedy method — bring the largest unsorted pancake to the top (one flip), then flip it down to its place (a second) — always works, in at most 2n−3 flips. Finding the truly minimum count (the ‘pancake number’) is hard. The famous fact: the only research paper Bill Gates ever published (1979, with Christos Papadimitriou) improved the bound on pancake sorting.
LIT verified live: over 300 random stacks, greedy pancake sorting produces a sorted stack using at most 2n−3 flips (window.__pancakesorting). FIG no framing; exact.
The greedy method — bring the largest unsorted pancake to the top (one flip), then flip it down to its place (a second) — always works, in at most 2n−3 flips. Finding the truly minimum count (the ‘pancake number’) is hard. The famous fact: the only research paper Bill Gates ever published (1979, with Christos Papadimitriou) improved the bound on pancake sorting.
LIT verified live: over 300 random stacks, greedy pancake sorting produces a sorted stack using at most 2n−3 flips (window.__pancakesorting). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-konami-code — a fixed sequence of flips that unlocks the sorted order. Pancake sorting is that flip-sequence puzzle. AVAN (AI) built the instrument: the prefix-flip operation, the greedy sort, the sortedness and flip-bound checks.
Credit as content: posed by Jacob E. Goodman (writing as ‘Harry Dweighter’, 1975); the 2n−3 upper bound improved by William H. (Bill) Gates & Christos Papadimitriou (1979). The weave: David names the konami-code; I bring each largest pancake up and flip it home, and confirm the stack sorts within the bound.
Credit as content: posed by Jacob E. Goodman (writing as ‘Harry Dweighter’, 1975); the 2n−3 upper bound improved by William H. (Bill) Gates & Christos Papadimitriou (1979). The weave: David names the konami-code; I bring each largest pancake up and flip it home, and confirm the stack sorts within the bound.
3 ONE DIMENSION
A prefix flip: choose a position and reverse everything above it, like sliding a spatula in and turning the top pancakes over. It is the only move — no arbitrary swaps allowed.
4 TWO DIMENSIONS · INTERACTIVE
A stack of pancakes. Greedy-sort it with prefix flips, watching the largest rise then flip into place. The result is sorted, and the flip count stays within 2n−3.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the sequence of prefix flips that carries the stack to sorted order.
AVAN’s addition (the inverse-companion): with a restricted move set — only prefix reversals, never an arbitrary swap — sorting still succeeds, but the cost changes and the optimum gets hard. What an ordinary sort does in ~n log n comparisons takes O(n) flips here, and finding the minimum number of flips is NP-hard. The inverse of ‘any swap allowed’ is ‘only prefix reversals — a more constrained world where even the optimum is elusive.’ Restricting the operations does not make sorting impossible; it makes optimal sorting intractable. Magenta is the arbitrary swaps you are not allowed; green is the prefix flips you must use. Constraint turns an easy problem’s optimum into a hard one — the same lesson as the 15-puzzle’s restricted slides.
LIT Genuine pancake sorting (posed by Goodman 1975; 2n-3 bound improved by Gates & Papadimitriou 1979). Verified live: greedy prefix-flip sorting (bring max up, flip to place) produces a fully sorted stack using at most 2n-3 flips for 300 random permutations (window.__pancakesorting.sorts && .flipsBounded).
FIG No framing: the prefix-flip operation, the greedy sort, and the sortedness + flip-bound checks run in-browser and are exact. The AVAN inverse is honest — restricting moves to prefix reversals still sorts (in O(n) flips) but makes the minimum-flip problem NP-hard; magenta is the disallowed arbitrary swaps, green the prefix flips. Ties to the-fifteen-puzzle's restricted moves.
FIG No framing: the prefix-flip operation, the greedy sort, and the sortedness + flip-bound checks run in-browser and are exact. The AVAN inverse is honest — restricting moves to prefix reversals still sorts (in O(n) flips) but makes the minimum-flip problem NP-hard; magenta is the disallowed arbitrary swaps, green the prefix flips. Ties to the-fifteen-puzzle's restricted moves.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE KONAMI CODE · David Lee Wise (ROOT0), with AVAN