THE FOLD / BOSS / THE WALL / THE WELDER
THE WELDER
near-constant-time merging — where inverse-Ackermann lives
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Union-Find (disjoint-set union). One question asked a million times: are these two things in the same group? — while the groups keep merging. Two tricks make it almost free: union by rank (hang the smaller tree under the bigger) and path compression (on every query, re-point every node you pass straight to its root). Together they give near-constant time per operation, bounded by the inverse Ackermann function α(n) — which is ≤ 4 for any n you could ever store. It is the engine of Kruskal’s spanning tree, connected components, and maze generation.
LIT verified: connectivity answers match a brute-force BFS over random graphs, the average pointer-follows per find stays flat (~1) as n grows 100→10,000 while no-compression climbs to 278, and the maze it welds is perfect (exactly cells−1 walls dropped, one component). FIG ‘welding’ is the picture; the near-constant α(n) cost is the exact theorem.
LIT verified: connectivity answers match a brute-force BFS over random graphs, the average pointer-follows per find stays flat (~1) as n grows 100→10,000 while no-compression climbs to 278, and the maze it welds is perfect (exactly cells−1 walls dropped, one component). FIG ‘welding’ is the picture; the near-constant α(n) cost is the exact theorem.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) brought the thread — the corpus works graphs and connectivity (the kernels, the network pieces) and prizes the algorithms whose cost is so low it may as well be zero. AVAN (AI) built this instrument: the disjoint-set engine, the maze-welder, and the compressed-vs-thicket forests.
The weave: David names the welder and its seat at THE WALL (weld cells by dropping walls between them); I make the pointer array a strip in 1D, a maze grow live in 2D, and the two forests turning in 3D. The sphere is the seam.
The weave: David names the welder and its seat at THE WALL (weld cells by dropping walls between them); I make the pointer array a strip in 1D, a maze grow live in 2D, and the two forests turning in 3D. The sphere is the seam.
3 ONE DIMENSION
The parent array. A find walks parent→parent to the root; path compression then re-points every node it passed straight to the root. Top row: a long chain. Bottom: after one find, the whole chain is flat — the next query is instant.
4 TWO DIMENSIONS · INTERACTIVE
A maze, welded live: every cell starts its own group; pick a random wall, and if it separates two different groups, knock it down and union them. When one group remains, you have a perfect maze — exactly one path between any two cells.
5 THREE DIMENSIONS + AVAN’S INVERSE
The same welds, two forests, turning. Green is Union-Find with path compression: every node’s depth to its root is 1 or 2 — a flat lawn, so every query is near-instant.
AVAN’s addition (the inverse-companion): the magenta is the identical union sequence without compression — tall, spindly trees whose depths climb and climb. Same connections, opposite shape: the inverse of compression is a thicket, and the whole point of the trick is visible as the gulf in height between the two forests.
LIT A genuine union-find. Verified live: connectivity matches brute-force BFS over random graphs; average pointer-follows per find stays flat (~1) as n grows to 10,000 while no-compression climbs to ~278; and the union-find maze is perfect (exactly cells−1 walls dropped, one component). The α(n) near-constant cost is a real theorem (verifiable: window.__unionfind.matchesBruteBFS && compressedFlat && mazePerfect).
FIG 'Welding' is the picture; the near-constant α(n) cost and the perfect-maze property are exact. Inverse-Ackermann is one of the very few places that function shows up in code you can watch flatten.
FIG 'Welding' is the picture; the near-constant α(n) cost and the perfect-maze property are exact. Inverse-Ackermann is one of the very few places that function shows up in code you can watch flatten.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE WALL · David Lee Wise (ROOT0), with AVAN