1// The sweep, and everything that has to stand next to a distance field.2//3// Sliding-block moves are reversible, so the configuration graph is undirected.4// That single fact is what makes generation cheap: a breadth-first search5// *outward from the goal* labels every reachable configuration with its exact6// distance to a solved board, and every state sitting at depth k is, by7// construction, a puzzle whose optimal solution is exactly k unit steps. One8// sweep per family yields the family's whole difficulty-stratified catalogue at9// once — which is what makes an open-ended ladder possible from a single pass.10//11// Pass 1 discovers the component the family's packing lives in. Pass 2 is a12// multi-source BFS from every seated-goal state in that component.13//14// This runs off the UI thread because it has to: the classic board is about 26k15// states and the deepest family an order more, and a survey screen that cannot16// repaint is a frozen app rather than a paced one.17//18// What is *here* is traversal. What is not here is policy: which depth a rung19// asks for, how the four measurements are weighed, and every seed used along20// the way are decided in Gleam and arrive in the message. This worker never21// decides how hard a board is; it measures one and says what it found.2223const SHAPE_W = [0, 1, 1, 2, 2];24const SHAPE_H = [0, 1, 2, 1, 2];25const DIRS = [26 [0, -1],27 [0, 1],28 [-1, 0],29 [1, 0],30];3132// A configuration is stored as the grid of *shape classes*, not of piece33// identities, because two pieces of the same shape are interchangeable. Packing34// those cells in base five gives a plain number that is both an exact key and35// its own hash. A key has to stay under 2^53, and 5^22 fits where 5^23 does36// not, so 22 cells is the ceiling — which is what bounds the board sizes on37// offer.38const CAP = 400000;39const BUCKET_MAX = 96;40const ROLL_CAP = 2500;4142const surveys = new Map();43const pending = new Map();4445function makeBoard(width, height) {46 const n = width * height;47 return { width, height, n, scratch: new Uint8Array(n), seen: new Uint8Array(n) };48}4950function encode(b, grid) {51 let key = 0;52 for (let i = b.n - 1; i >= 0; i--) key = key * 5 + grid[i];53 return key;54}5556function decode(b, key, out) {57 for (let i = 0; i < b.n; i++) {58 const r = key % 5;59 out[i] = r;60 key = (key - r) / 5;61 }62 return out;63}6465function gridOf(b, key) {66 return Array.from(decode(b, key, new Uint8Array(b.n)));67}6869// Row-major scanning reaches a piece's top-left corner first, so the first70// unclaimed cell of each piece names it.71function piecesOf(b, grid, out) {72 out.length = 0;73 b.seen.fill(0);74 for (let y = 0; y < b.height; y++) {75 for (let x = 0; x < b.width; x++) {76 const i = y * b.width + x;77 const c = grid[i];78 if (!c || b.seen[i]) continue;79 const w = SHAPE_W[c];80 const h = SHAPE_H[c];81 for (let dy = 0; dy < h; dy++) {82 for (let dx = 0; dx < w; dx++) b.seen[(y + dy) * b.width + x + dx] = 1;83 }84 out.push({ x, y, w, h, c });85 }86 }87 return out;88}8990function canMove(b, grid, p, dx, dy) {91 const nx = p.x + dx;92 const ny = p.y + dy;93 if (nx < 0 || ny < 0 || nx + p.w > b.width || ny + p.h > b.height) return false;94 for (let y = 0; y < p.h; y++) {95 for (let x = 0; x < p.w; x++) {96 const cx = nx + x;97 const cy = ny + y;98 // Still self-covered: a piece never collides with the cells it is itself99 // vacating.100 if (cx >= p.x && cx < p.x + p.w && cy >= p.y && cy < p.y + p.h) continue;101 if (grid[cy * b.width + cx]) return false;102 }103 }104 return true;105}106107function applyMove(b, grid, p, dx, dy) {108 for (let y = 0; y < p.h; y++) {109 for (let x = 0; x < p.w; x++) grid[(p.y + y) * b.width + p.x + x] = 0;110 }111 for (let y = 0; y < p.h; y++) {112 for (let x = 0; x < p.w; x++) {113 grid[(p.y + dy + y) * b.width + p.x + dx + x] = p.c;114 }115 }116}117118// Unit-step neighbours. One cell, one direction — the convention the whole119// distance field is measured in.120function neighbours(b, key, out, pieceBuffer) {121 out.length = 0;122 const grid = decode(b, key, b.scratch);123 const pieces = piecesOf(b, grid, pieceBuffer);124 for (const p of pieces) {125 for (const [dx, dy] of DIRS) {126 if (!canMove(b, grid, p, dx, dy)) continue;127 applyMove(b, grid, p, dx, dy);128 out.push(encode(b, grid));129 applyMove(b, grid, { x: p.x + dx, y: p.y + dy, w: p.w, h: p.h, c: p.c }, -dx, -dy);130 }131 }132 return out;133}134135function seated(b, key, goalX, goalY) {136 const g = decode(b, key, b.scratch);137 return (138 g[goalY * b.width + goalX] === 4 &&139 g[goalY * b.width + goalX + 1] === 4 &&140 g[(goalY + 1) * b.width + goalX] === 4 &&141 g[(goalY + 1) * b.width + goalX + 1] === 4142 );143}144145function goalXY(b, key) {146 const g = decode(b, key, b.scratch);147 for (let y = 0; y < b.height - 1; y++) {148 for (let x = 0; x < b.width - 1; x++) {149 if (150 g[y * b.width + x] === 4 &&151 g[y * b.width + x + 1] === 4 &&152 g[(y + 1) * b.width + x] === 4 &&153 g[(y + 1) * b.width + x + 1] === 4154 ) {155 return { x, y };156 }157 }158 }159 return null;160}161162// The same generator the rest of the app is seeded by. It is here rather than163// imported because a worker is its own module graph, and it takes its seeds164// from the message: every number it produces was decided upstream.165function mulberry(a) {166 return function () {167 a |= 0;168 a = (a + 0x6d2b79f5) | 0;169 let t = Math.imul(a ^ (a >>> 15), 1 | a);170 t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;171 return ((t ^ (t >>> 14)) >>> 0) / 4294967296;172 };173}174175// ------------------------------------------------------------------- sweep176177function runSurvey(message) {178 const b = makeBoard(message.width, message.height);179 const start = encode(b, Uint8Array.from(message.grid));180 const seen = new Set([start]);181 const dist = new Map();182 // depth -> a sample of states at that depth, and how many sit there.183 const buckets = [];184 const widths = [];185 const nb = [];186 const pieceBuffer = [];187188 let queue = [start];189 let head = 0;190 let phase = 1;191 let ecc = 0;192 let reported = 0;193194 const tick = () => {195 const deadline = performance.now() + 10;196197 if (phase === 1) {198 while (head < queue.length && performance.now() < deadline) {199 const key = queue[head++];200 neighbours(b, key, nb, pieceBuffer);201 for (const next of nb) {202 if (!seen.has(next)) {203 seen.add(next);204 queue.push(next);205 }206 }207 if (seen.size > CAP) break;208 }209 if (head >= queue.length || seen.size > CAP) {210 queue = [];211 head = 0;212 for (const key of seen) {213 if (seated(b, key, message.goalX, message.goalY)) {214 dist.set(key, 0);215 queue.push(key);216 }217 }218 buckets[0] = queue.slice(0, BUCKET_MAX);219 widths[0] = queue.length;220 phase = 2;221 }222 } else {223 while (head < queue.length && performance.now() < deadline) {224 const key = queue[head++];225 const depth = dist.get(key) + 1;226 neighbours(b, key, nb, pieceBuffer);227 for (const next of nb) {228 if (dist.has(next) || !seen.has(next)) continue;229 dist.set(next, depth);230 queue.push(next);231 if (depth > ecc) ecc = depth;232 widths[depth] = (widths[depth] || 0) + 1;233 const bucket = buckets[depth] || (buckets[depth] = []);234 if (bucket.length < BUCKET_MAX) bucket.push(next);235 }236 }237 if (head >= queue.length) {238 const survey = { board: b, dist, buckets, widths, ecc, count: seen.size, start };239 surveys.set(message.familyId, survey);240 self.postMessage({241 type: "surveyed",242 familyId: message.familyId,243 ecc,244 count: seen.size,245 });246 drain(message.familyId);247 return;248 }249 }250251 // The count is a progress bar, not decoration: hiding it would leave a252 // still screen during a second and a half of work.253 if (performance.now() - reported > 50) {254 reported = performance.now();255 self.postMessage({256 type: "sweeping",257 familyId: message.familyId,258 count: phase === 1 ? seen.size : dist.size,259 total: seen.size,260 phase,261 });262 }263 setTimeout(tick, 0);264 };265266 tick();267}268269// --------------------------------------------------------------- the ladder270//271// The band a rung draws from, and a measurement of every candidate in it. Which272// depth was asked for, how wide the window is and where it starts were all273// decided upstream; this only knows how to reach into the field and walk it.274275function candidatesFor(survey, message) {276 const { buckets, ecc } = survey;277 const want = message.want;278 const pool = [];279 const take = (d) => {280 if (d < 2 || d > ecc) return;281 for (const state of buckets[d] || []) pool.push(state);282 };283284 if (message.ceiling) {285 // At the ceiling, draw from the deep band rather than the single deepest286 // depth. States at the exact maximum distance are rare — often a handful in287 // a graph of eighty thousand — so insisting on them would serve the same two288 // boards forever. A few steps of slack buys real variety and costs nothing289 // anyone can feel.290 for (let d = ecc; d >= ecc - 3; d--) take(d);291 } else {292 // Take the wanted depth alone if it has anything in it, so a rung's board is293 // exactly as long as the ladder says. Widening is a fallback for a thin band294 // near the ceiling, not a way to make the pool bigger — mixing depths and295 // then picking on score quietly serves a shallower board than advertised.296 take(want);297 }298 for (let spread = 1; spread <= 6 && !pool.length; spread++) {299 take(want - spread);300 take(want + spread);301 }302 if (!pool.length) for (let d = ecc; d >= 1 && !pool.length; d--) take(d);303 if (!pool.length) return [];304305 // Past the ceiling the band is the same every time, so rotate through it —306 // otherwise every rung from here on would serve the identical board.307 const window = Math.min(message.window, pool.length);308 const offset = Math.abs(message.offset) % pool.length;309 const rng = mulberry(message.seed);310 const out = [];311 for (let i = 0; i < window; i++) {312 const state = pool[(offset + i) % pool.length];313 out.push(analyse(survey, state, ((rng() * 1e6) | 0) + i, message));314 }315 return out;316}317318// Expected steps for an eps-greedy walker to reach the goal, plus the shape of319// one shortest path. Both are properties of the state space rather than of the320// solution, which is the whole point: machine difficulty is not human321// difficulty, and a long solution down a wide, well-signposted corridor stays322// easy while a short one that makes you retreat does not.323function analyse(survey, state, seed, message) {324 const b = survey.board;325 const dist = survey.dist;326 const rng = mulberry(seed);327 const nb = [];328 const pieceBuffer = [];329 const optimal = dist.get(state) ?? 0;330331 let total = 0;332 for (let roll = 0; roll < message.rollouts; roll++) {333 let s = state;334 let steps = 0;335 while (dist.get(s) > 0 && steps < ROLL_CAP) {336 neighbours(b, s, nb, pieceBuffer);337 if (!nb.length) break;338 let pick;339 if (rng() < message.stray) {340 pick = nb[(rng() * nb.length) | 0];341 } else {342 const here = dist.get(s);343 let downhill = 0;344 for (const next of nb) if (dist.get(next) < here) downhill++;345 if (downhill) {346 let j = (rng() * downhill) | 0;347 for (const next of nb) {348 if (dist.get(next) < here && j-- === 0) {349 pick = next;350 break;351 }352 }353 } else {354 pick = nb[(rng() * nb.length) | 0];355 }356 }357 s = pick;358 steps++;359 }360 total += steps;361 }362 const wander = total / Math.max(1, message.rollouts);363364 // One shortest path, walked greedily down the distance field, and the count of365 // counter-intuitive steps along it — moves that carry the goal block *away*366 // from its exit, which is the move nobody finds.367 const path = [state];368 let s = state;369 let guard = 0;370 while (dist.get(s) > 0 && guard++ < 4000) {371 neighbours(b, s, nb, pieceBuffer);372 const here = dist.get(s);373 const next = nb.find((k) => dist.get(k) === here - 1);374 if (next === undefined) break;375 s = next;376 path.push(s);377 }378379 let retreats = 0;380 let branch = 0;381 for (let i = 0; i < path.length; i++) {382 neighbours(b, path[i], nb, pieceBuffer);383 branch += nb.length;384 if (!i) continue;385 const was = goalXY(b, path[i - 1]);386 const now = goalXY(b, path[i]);387 if (!was || !now) continue;388 const before = Math.abs(was.x - message.goalX) + Math.abs(was.y - message.goalY);389 const after = Math.abs(now.x - message.goalX) + Math.abs(now.y - message.goalY);390 if (after > before) retreats++;391 }392 branch /= Math.max(1, path.length);393394 return { state, grid: gridOf(b, state), optimal, wander, retreats, branch };395}396397// A survey may not have finished when a screen asks for a board. Queue the398// question rather than answering it wrongly.399function drain(familyId) {400 const waiting = pending.get(familyId);401 if (!waiting) return;402 pending.delete(familyId);403 for (const message of waiting) handle(message);404}405406function defer(message) {407 const waiting = pending.get(message.familyId) || [];408 waiting.push(message);409 pending.set(message.familyId, waiting);410}411412function handle(message) {413 if (message.type === "survey") {414 const known = surveys.get(message.familyId);415 if (known) {416 self.postMessage({417 type: "surveyed",418 familyId: message.familyId,419 ecc: known.ecc,420 count: known.count,421 });422 return;423 }424 // Already sweeping: queue the question rather than starting a second sweep425 // of the same graph. It is answered the moment the first one lands.426 if (pending.has(message.familyId)) {427 defer(message);428 return;429 }430 pending.set(message.familyId, []);431 runSurvey(message);432 return;433 }434435 const survey = surveys.get(message.familyId);436 if (!survey) {437 defer(message);438 return;439 }440441 if (message.type === "puzzle") {442 self.postMessage({443 type: "puzzled",444 familyId: message.familyId,445 rung: message.rung,446 candidates: candidatesFor(survey, message),447 });448 }449450 // The harness's question: how far is each of these, with no claim that they451 // are a run. Kept apart from "distances" so a probe can never be spliced into452 // a trace.453 if (message.type === "probe") {454 self.postMessage({455 type: "probed",456 familyId: message.familyId,457 distances: message.states.map((state) => survey.dist.get(state) ?? -1),458 });459 }460461 if (message.type === "distances") {462 self.postMessage({463 type: "measured",464 familyId: message.familyId,465 seq: message.seq,466 distances: message.states.map((state) => survey.dist.get(state) ?? -1),467 });468 }469}470471self.addEventListener("message", ({ data }) => handle(data));