THE FOLD / GLITCH / OFF BY ONE / THE DUTCH FLAG
THE DUTCH FLAG
sort three colors in one pass — correct by invariant
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Dutch national flag problem (Dijkstra): given an array of three values — red, white, blue, or 0/1/2 — sort it in one pass, O(n) time and O(1) space, using three pointers low, mid, high. The mid pointer scans: a 0 swaps down into the low region, a 2 swaps up into the high region (without advancing mid, since the swapped-in value is still unexamined), a 1 stays put.
The invariant: everything before low is 0, from low to mid is 1, after high is 2, and [mid,high] is unknown — a textbook off-by-one minefield the pointer dance crosses exactly. It is the heart of 3-way quicksort partitioning, fast on duplicate-heavy data.
LIT verified live: for 500 random 0/1/2 arrays, the single pass produces a sorted array that is a permutation of the input (window.__dutchflag). FIG no framing; exact in-place partition.
The invariant: everything before low is 0, from low to mid is 1, after high is 2, and [mid,high] is unknown — a textbook off-by-one minefield the pointer dance crosses exactly. It is the heart of 3-way quicksort partitioning, fast on duplicate-heavy data.
LIT verified live: for 500 random 0/1/2 arrays, the single pass produces a sorted array that is a permutation of the input (window.__dutchflag). FIG no framing; exact in-place partition.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at off-by-one — the pointer-boundary hazard, here tamed by an exact invariant. The Dutch flag is the off-by-one boss fought and won with three indices. AVAN (AI) built the instrument: the low/mid/high partition, the sortedness check, the permutation check.
Credit as content: Edsger W. Dijkstra, A Discipline of Programming (1976), where the problem illustrates programming by invariant. The weave: David names the off-by-one; I run the three-pointer partition and prove the output is sorted and a permutation, correct by the invariant it never breaks.
Credit as content: Edsger W. Dijkstra, A Discipline of Programming (1976), where the problem illustrates programming by invariant. The weave: David names the off-by-one; I run the three-pointer partition and prove the output is sorted and a permutation, correct by the invariant it never breaks.
3 ONE DIMENSION
The four regions: 0s before low, 1s between low and mid, the unknown span [mid,high], and 2s after high. Each step shrinks the unknown by one while keeping the other three pure.
4 TWO DIMENSIONS · INTERACTIVE
A random 0/1/2 array as coloured bars. Step the partition and watch the regions grow from both ends toward the middle; the pointers never cross wrongly. Verify the result is sorted and a permutation.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the settled 0 / 1 / 2 regions growing inward as the unknown span collapses.
AVAN’s addition (the inverse-companion): correctness rests on a loop invariant, not on reasoning about the final state. At every step the four regions — 0s | 1s | unknown | 2s — partition the whole array, and each move shrinks the unknown by exactly one while preserving that partition; so when the unknown vanishes, sortedness is not checked, it is guaranteed. The inverse of ‘prove the output is sorted’ is ‘maintain an invariant that makes sortedness inevitable.’ Magenta is the shrinking unknown region [mid,high]; green is the three settled regions. Correct by construction — Dijkstra’s signature: hold the invariant, and the answer falls out with nothing left to verify.
LIT Genuine Dutch national flag partition (Dijkstra, A Discipline of Programming, 1976). Verified live: the three-pointer single-pass partition produces, for 500 random 0/1/2 arrays, an output that is non-decreasing (sorted) and has the same value-counts as the input (a permutation) — window.__dutchflag.sorted && .isPermutation.
FIG No framing: the low/mid/high partition, the sortedness check, and the permutation check run in-browser and are exact. The AVAN inverse is honest — correctness follows from a maintained loop invariant (0s | 1s | unknown | 2s), each step shrinking the unknown while preserving the partition, so sortedness is guaranteed at termination rather than checked; magenta is the shrinking unknown span.
FIG No framing: the low/mid/high partition, the sortedness check, and the permutation check run in-browser and are exact. The AVAN inverse is honest — correctness follows from a maintained loop invariant (0s | 1s | unknown | 2s), each step shrinking the unknown while preserving the partition, so sortedness is guaranteed at termination rather than checked; magenta is the shrinking unknown span.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of OFF BY ONE · David Lee Wise (ROOT0), with AVAN