fuzzyworld

basin / files / src / model / puzzle.ts

puzzle.ts

Blame: the commit that last changed each line · file · history

a7bf123a 2026-07-01 Pavel Safronov1import { mulberry32 } from '../rng';
2import type { Rng } from '../rng';
36e6a8b9 2026-07-02 Pavel Safronov3import { generateDome, heightAt, isOceanEdge } from './heightmap';
a7bf123a 2026-07-01 Pavel Safronov4import type { Edges, EdgeType, Heightmap } from './heightmap';
5import { simulateFlows } from './flow';
6import type { Cell } from './flow';
7
8/**
9 * Everything that defines a board. A `Config` maps 1:1 to a shareable {@link
10 * encodeConfig | code}: same config → same board, and every axis is a knob the
11 * UI exposes.
12 */
13export interface Config {
14 /** Square board edge length, in cells. */
15 size: number;
16 /** How many hidden springs the player must find. */
17 springCount: number;
18 /** Per-side edge types (ocean vs wall). */
19 edges: Edges;
03c2cc12 2026-07-01 Pavel Safronov20 /**
21 * How much simulated erosion (aging) the terrain underwent before the board
22 * was shown. 0 = a pristine dome; higher values carve deeper grooves and shift
23 * the outflow signature. See {@link erode}.
24 */
25 erosion: number;
36e6a8b9 2026-07-02 Pavel Safronov26 /**
27 * How far from the shore springs are drawn from: low values favour land just
28 * above the waterline, high values favour high ground near the peak. 0-15,
29 * centred at {@link REACH_DEFAULT} (no preference — the original behaviour).
30 */
31 reach: number;
a7bf123a 2026-07-01 Pavel Safronov32 /** Seed for the terrain noise + spring placement (given the other axes). */
33 terrainSeed: number;
34}
35
36export const SIZE_MIN = 5;
b9acd697 2026-07-01 Pavel Safronov37export const SIZE_MAX = 100;
a7bf123a 2026-07-01 Pavel Safronov38export const SPRINGS_MIN = 1;
39export const SPRINGS_MAX = 6;
03c2cc12 2026-07-01 Pavel Safronov40export const EROSION_MIN = 0;
41export const EROSION_MAX = 15; // fits the 4 spare bits of the config code
36e6a8b9 2026-07-02 Pavel Safronov42export const REACH_MIN = 0;
43export const REACH_MAX = 15;
44export const REACH_DEFAULT = 8;
a7bf123a 2026-07-01 Pavel Safronov45
46/**
47 * A solvable board (Reading A): terrain + a target edge signature are given, and
48 * the player must rediscover the hidden spring *positions* that produce it.
49 */
50export interface Puzzle {
51 config: Config;
52 hm: Heightmap;
53 width: number;
54 height: number;
55 /** Per-side edge configuration (ocean vs wall) for this board. */
56 edges: Edges;
57 /** Hidden spring positions the player is hunting for. Order irrelevant. */
58 solution: Cell[];
59 /** 1 for every border cell water must reach in the solution, row-major. */
60 target: Uint8Array;
61 /** The target's wet border cells, for rendering the goal. */
62 targetOutflow: Cell[];
63}
64
65/**
66 * Build a puzzle from a config. The terrain seed drives terrain + spring
67 * placement, so a board is fully reproducible from its config (hence its code).
68 *
69 * Springs are drawn from interior land cells, kept a minimum gap apart so their
7b368f91 2026-07-01 Pavel Safronov70 * watersheds stay distinct, and re-rolled until they yield a signature that is
71 * both reasonably rich (a wider target is easier to read) and, above all,
72 * *unambiguous*: the chosen set must be the only set of that size reproducing it,
73 * so the gold-edge hint actually pins down a single answer (see
74 * {@link isUniqueSolution}). Boards that can't be made unique fall back to the
75 * richest set found, so generation never fails.
a7bf123a 2026-07-01 Pavel Safronov76 */
b9acd697 2026-07-01 Pavel Safronov77export function generatePuzzle(
78 config: Config,
79 onProgress?: (fraction: number) => void,
80): Puzzle {
81 onProgress?.(0);
a7bf123a 2026-07-01 Pavel Safronov82 const norm = normalizeConfig(config);
36e6a8b9 2026-07-02 Pavel Safronov83 const { size, springCount, edges, erosion, reach, terrainSeed } = norm;
a7bf123a 2026-07-01 Pavel Safronov84 const rng = mulberry32(terrainSeed);
36e6a8b9 2026-07-02 Pavel Safronov85 let hm = generateDome(size, size, rng, edges, erosion);
86
87 // Heavy erosion (or just an unlucky seed) can wash away most standing land,
88 // leaving a board that reads as almost entirely water — not a fair puzzle.
89 // Back off the *effective* aging in fixed steps, each redrawn from a seed
90 // derived from terrainSeed (so the fallback is itself deterministic), until
91 // enough land remains. Boards that already clear the bar take zero extra
92 // steps and are unaffected.
93 const interior = (size - 2) * (size - 2);
94 const minLand = Math.min(interior, Math.max(springCount, Math.ceil(interior * 0.2)));
95 for (let step = 1; landCandidates(hm, size).length < minLand && step <= 6; step++) {
96 const backoffRng = mulberry32((terrainSeed + step * 0x9e3779b9) >>> 0);
97 hm = generateDome(size, size, backoffRng, edges, erosion * Math.pow(0.7, step));
98 }
b9acd697 2026-07-01 Pavel Safronov99 onProgress?.(0.1);
a7bf123a 2026-07-01 Pavel Safronov100
644389f3 2026-07-02 Pavel Safronov101 // Candidates: interior land cells with enough elevation to render visibly as
102 // land (not water-blue). After drainage resolution all interior cells have
103 // height > 0, but very shallow cells near ocean edges can still look like
104 // water in the terrain colours — a spring there would be unclickable.
105 // 0.1 sits comfortably in the water→land colour transition (0.02–0.15).
36e6a8b9 2026-07-02 Pavel Safronov106 const candidates = landCandidates(hm, size);
107
108 // The backoff above targets the common case; guarantee the invariant outright
109 // by back-filling with the highest remaining interior cells if it's still
110 // short. Interior cell count is always >= springCount (normalizeConfig
111 // guarantees it), so this always reaches springCount candidates.
112 if (candidates.length < springCount) {
113 const seen = new Set(candidates.map((c) => c.y * size + c.x));
114 const rest: Cell[] = [];
115 for (let y = 1; y < size - 1; y++) {
116 for (let x = 1; x < size - 1; x++) {
117 if (!seen.has(y * size + x)) rest.push({ x, y });
118 }
a7bf123a 2026-07-01 Pavel Safronov119 }
36e6a8b9 2026-07-02 Pavel Safronov120 rest.sort((a, b) => heightAt(hm, b.x, b.y) - heightAt(hm, a.x, a.y));
121 candidates.push(...rest.slice(0, springCount - candidates.length));
a7bf123a 2026-07-01 Pavel Safronov122 }
123
36e6a8b9 2026-07-02 Pavel Safronov124 // Springs must never land on a "shore" cell — an interior cell directly
125 // adjacent to an ocean edge — because that's exactly where the renderer
126 // draws the gold target outline (see Renderer.drawTarget): a spring there
127 // would double as its own goal indicator, giving it away. `pickSpringIdx`
128 // below exhausts non-shore candidates before ever touching `shoreIdx`, so
129 // shore cells are used only for the picks that genuinely can't be filled
130 // otherwise (tiny boards with springCount larger than the non-shore
131 // interior can support) — never more than the unavoidable minimum.
132 const nonShoreIdx = candidates.map((_, i) => i).filter((i) => !isShoreCell(candidates[i], edges, size));
133 const shoreIdx = candidates.map((_, i) => i).filter((i) => isShoreCell(candidates[i], edges, size));
134
135 // Reach then biases which non-shore candidates get *proposed* as springs:
136 // low values favour land just above the shoreline (but still off it), high
137 // values favour high ground near the peak. Height is a direct proxy for
138 // distance from the ocean edge in this dome model (see generateDome). This
139 // only narrows the proposal pool, not the uniqueness check below — `sig`
140 // covers every real candidate, so a spring set outside the reach band is
141 // still counted as a competing solution. That way "Reach" never makes the
142 // gold-edge hint ambiguous, it just shapes which legible answer generation
143 // reaches for. A hard band keeps the effect legible; if it would leave too
144 // few candidates to place springCount springs, fall back to the full
145 // non-shore pool.
146 const REACH_BAND = 0.5; // fraction of the sorted pool kept at any reach setting
147 const byHeight = [...nonShoreIdx].sort(
148 (a, b) => heightAt(hm, candidates[a].x, candidates[a].y) - heightAt(hm, candidates[b].x, candidates[b].y),
149 );
150 const bandStart = (reach / REACH_MAX) * (1 - REACH_BAND);
151 const lo = Math.floor(bandStart * byHeight.length);
152 const hi = Math.min(byHeight.length, lo + Math.ceil(REACH_BAND * byHeight.length));
153 const windowed = byHeight.slice(lo, hi);
154 const reachPool = windowed.length >= springCount ? windowed : nonShoreIdx;
155
156 // Only ever hand pickSpringIdx a shore tier if non-shore candidates can't
157 // reach springCount at all. Otherwise every attempt's minGap relaxation
158 // (below) already finds a spaced non-shore set on its own by the time it's
159 // fully relaxed — gating here stops an early, still-strict attempt from
160 // reaching into shore just to patch a spacing gap it didn't need to.
161 const springPools = nonShoreIdx.length >= springCount ? [reachPool] : [nonShoreIdx, shoreIdx];
162
7b368f91 2026-07-01 Pavel Safronov163 // A candidate's outflow footprint is fixed by the terrain, so precompute each
164 // one once as a bitmask over border-cell indices. Because wet sets (and hence
165 // outflow) union across springs, a spring set's target signature is simply the
166 // OR of its members' masks — which is what makes the uniqueness check cheap.
b9acd697 2026-07-01 Pavel Safronov167 const sigStart = performance.now();
168 const sig: bigint[] = [];
169 for (let i = 0; i < candidates.length; i++) {
170 sig.push(outflowMask(simulateFlows(hm, [candidates[i]]).outflow, size));
171 if ((i & 63) === 0) onProgress?.(0.1 + 0.1 * ((i + 1) / candidates.length));
172 }
173 const sigMs = Math.max(1, performance.now() - sigStart);
174
175 // countCovers (the uniqueness DFS) uses bigint arithmetic, which is empirically
176 // ~10× slower than the float32 array ops in simulateFlows. Use the measured sig
177 // rate to estimate how long the 128 uniqueness-check attempts will take, then
178 // give each phase its proportional share of the progress bar.
179 const BIGINT_FACTOR = 10;
180 const perSigMs = sigMs / Math.max(1, candidates.length);
181 const compatEst = Math.floor(candidates.length * 0.4); // ~40% of candidates fit any target
182 const BUDGET = 200_000;
183 const attemptsOpsEst = Math.min(BUDGET, Math.pow(compatEst, springCount) / springCount);
184 const ATTEMPTS = 128;
185 const perAttemptMs = (attemptsOpsEst * perSigMs * BIGINT_FACTOR) / Math.max(1, (size * size) / 2);
186 const attemptsEstMs = Math.max(1, ATTEMPTS * perAttemptMs);
187
188 // Snap bar to sig's real proportional share, then fill the rest during attempts.
189 const totalEstMs = sigMs + attemptsEstMs;
190 const P_SIG_END = 0.1 + 0.88 * (sigMs / totalEstMs);
191 onProgress?.(P_SIG_END);
7b368f91 2026-07-01 Pavel Safronov192
a7bf123a 2026-07-01 Pavel Safronov193 const wanted = Math.max(3, springCount); // prefer a signature at least this wide
7b368f91 2026-07-01 Pavel Safronov194 let bestUnique: Candidate | null = null;
195 let bestAny: Candidate | null = null;
a7bf123a 2026-07-01 Pavel Safronov196
b9acd697 2026-07-01 Pavel Safronov197 const attemptsStart = performance.now();
198 for (let attempt = 0; attempt < ATTEMPTS; attempt++) {
199 const elapsed = performance.now() - attemptsStart;
200 onProgress?.(P_SIG_END + (0.99 - P_SIG_END) * Math.min(0.98, elapsed / attemptsEstMs));
a7bf123a 2026-07-01 Pavel Safronov201 // Relax the spacing requirement if the board is too cramped to satisfy it.
202 const minGap = attempt < 96 ? 3 : attempt < 112 ? 2 : 1;
36e6a8b9 2026-07-02 Pavel Safronov203 const idx = pickSpringIdx(candidates, springPools, springCount, rng, minGap);
7b368f91 2026-07-01 Pavel Safronov204 if (idx.length < springCount) continue;
205
206 let target = 0n;
207 for (const i of idx) target |= sig[i];
208 if (target === 0n) continue; // must reach an ocean edge
a7bf123a 2026-07-01 Pavel Safronov209
7b368f91 2026-07-01 Pavel Safronov210 const richness = popcount(target);
211 const pick: Candidate = { solution: idx.map((i) => candidates[i]), richness };
212 if (!bestAny || richness > bestAny.richness) bestAny = pick;
a7bf123a 2026-07-01 Pavel Safronov213
7b368f91 2026-07-01 Pavel Safronov214 // Only accept a pick whose signature no *other* size-k spring set reproduces.
215 if (isUniqueSolution(sig, target, springCount)) {
216 if (!bestUnique || richness > bestUnique.richness) bestUnique = pick;
217 if (richness >= wanted) break; // unique *and* rich enough — good to go
a7bf123a 2026-07-01 Pavel Safronov218 }
219 }
b9acd697 2026-07-01 Pavel Safronov220 onProgress?.(0.99);
a7bf123a 2026-07-01 Pavel Safronov221
7b368f91 2026-07-01 Pavel Safronov222 // Prefer an unambiguous board; fall back to the richest set otherwise. `bestAny`
223 // is always set: normalizeConfig guarantees at least `springCount` interior
224 // candidates, and every interior cell drains to an ocean edge, so some attempt
225 // always yields a non-empty signature.
226 const chosen = bestUnique ?? bestAny!;
227 const targetOutflow = simulateFlows(hm, chosen.solution).outflow;
a7bf123a 2026-07-01 Pavel Safronov228 const target = borderSignature(targetOutflow, size, size);
229
b9acd697 2026-07-01 Pavel Safronov230 onProgress?.(1);
7b368f91 2026-07-01 Pavel Safronov231 return {
232 config: norm,
233 hm,
234 width: size,
235 height: size,
236 edges,
237 solution: chosen.solution,
238 target,
239 targetOutflow,
240 };
241}
242
36e6a8b9 2026-07-02 Pavel Safronov243/** Is `c` directly adjacent to an ocean edge — a "shore" cell (see Renderer.drawTarget)? */
244function isShoreCell(c: Cell, edges: Edges, size: number): boolean {
245 const neighbors: ReadonlyArray<readonly [number, number]> = [
246 [c.x - 1, c.y],
247 [c.x + 1, c.y],
248 [c.x, c.y - 1],
249 [c.x, c.y + 1],
250 ];
251 return neighbors.some(([nx, ny]) => isOceanEdge(edges, nx, ny, size, size));
252}
253
254/** Interior cells whose height clears the "looks like land" threshold. */
255function landCandidates(hm: Heightmap, size: number): Cell[] {
256 const out: Cell[] = [];
257 for (let y = 1; y < size - 1; y++) {
258 for (let x = 1; x < size - 1; x++) {
259 if (heightAt(hm, x, y) >= 0.1) out.push({ x, y });
260 }
261 }
262 return out;
263}
264
7b368f91 2026-07-01 Pavel Safronov265/** A spring set under consideration during generation, with its signature width. */
266interface Candidate {
267 solution: Cell[];
268 /** Number of border cells the set wets — how rich (readable) its signature is. */
269 richness: number;
a7bf123a 2026-07-01 Pavel Safronov270}
271
272/** Is `cell` one of the puzzle's hidden spring positions? */
273export function isSolutionSpring(puzzle: Puzzle, cell: Cell): boolean {
274 return puzzle.solution.some((s) => s.x === cell.x && s.y === cell.y);
275}
276
277// ---------------------------------------------------------------------------
278// Config: bounds, randomisation, and the shareable code.
279// ---------------------------------------------------------------------------
280
281const clampInt = (v: number, lo: number, hi: number): number =>
282 Math.min(hi, Math.max(lo, Math.round(v)));
283
284/** Clamp every axis into range and guarantee at least one ocean side. */
285export function normalizeConfig(c: Config): Config {
286 const size = clampInt(c.size, SIZE_MIN, SIZE_MAX);
287 const interior = (size - 2) * (size - 2);
288 const springCount = clampInt(c.springCount, SPRINGS_MIN, Math.min(SPRINGS_MAX, interior));
03c2cc12 2026-07-01 Pavel Safronov289 const erosion = clampInt(c.erosion ?? 0, EROSION_MIN, EROSION_MAX);
36e6a8b9 2026-07-02 Pavel Safronov290 const reach = clampInt(c.reach ?? REACH_DEFAULT, REACH_MIN, REACH_MAX);
03c2cc12 2026-07-01 Pavel Safronov291 return {
292 size,
293 springCount,
294 edges: ensureOcean(c.edges),
295 erosion,
36e6a8b9 2026-07-02 Pavel Safronov296 reach,
03c2cc12 2026-07-01 Pavel Safronov297 terrainSeed: c.terrainSeed >>> 0,
298 };
a7bf123a 2026-07-01 Pavel Safronov299}
300
301/** A wholly random board within sensible bounds. */
302export function randomConfig(): Config {
303 return normalizeConfig({
304 size: 8 + Math.floor(Math.random() * 5) * 2, // 8,10,12,14,16
305 springCount: 2 + Math.floor(Math.random() * 3), // 2,3,4
306 edges: rollEdges(Math.random),
03c2cc12 2026-07-01 Pavel Safronov307 erosion: Math.floor(Math.random() * 9), // 0..8: pristine to well-weathered
36e6a8b9 2026-07-02 Pavel Safronov308 reach: Math.floor(Math.random() * (REACH_MAX + 1)),
a7bf123a 2026-07-01 Pavel Safronov309 terrainSeed: (Math.random() * 2 ** 32) >>> 0,
310 });
311}
312
36e6a8b9 2026-07-02 Pavel Safronov313// The config packs into 52 bits — seed(32) · edges(4) · springs(3) · size(5) ·
314// erosion(4) · reach(4) — which we emit as a 9-char base64url string so the
315// axes aren't legible at a glance. It's obfuscation, not encryption: fully
316// reversible, no secrets. Erosion occupies bits 44-47 and reach bits 48-51,
317// both added after the original 8-char (48-bit) format; older codes are a
318// char shorter and no longer decode (decodeConfig rejects them), so a stale
319// shared link just rolls a fresh board rather than misbehaving.
a7bf123a 2026-07-01 Pavel Safronov320const B64 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_';
36e6a8b9 2026-07-02 Pavel Safronov321const CODE_LEN = 9;
a7bf123a 2026-07-01 Pavel Safronov322
36e6a8b9 2026-07-02 Pavel Safronov323/** A compact, reversible code for a config, e.g. "BQAr3kf9x". */
a7bf123a 2026-07-01 Pavel Safronov324export function encodeConfig(c: Config): string {
325 const n = normalizeConfig(c);
326 let v =
327 BigInt(n.terrainSeed >>> 0) |
328 (BigInt(edgesToMask(n.edges)) << 32n) |
329 (BigInt(n.springCount) << 36n) |
03c2cc12 2026-07-01 Pavel Safronov330 (BigInt(n.size) << 39n) |
36e6a8b9 2026-07-02 Pavel Safronov331 (BigInt(n.erosion) << 44n) |
332 (BigInt(n.reach) << 48n);
a7bf123a 2026-07-01 Pavel Safronov333 let out = '';
334 for (let i = 0; i < CODE_LEN; i++) {
335 out = B64[Number(v & 63n)] + out;
336 v >>= 6n;
337 }
338 return out;
339}
340
341/** Parse a config code, or null if it isn't well-formed. */
342export function decodeConfig(code: string): Config | null {
343 const s = code.trim();
344 if (s.length !== CODE_LEN) return null;
345 let v = 0n;
346 for (const ch of s) {
347 const d = B64.indexOf(ch);
348 if (d < 0) return null;
349 v = (v << 6n) | BigInt(d);
350 }
351 return normalizeConfig({
352 size: Number((v >> 39n) & 0x1fn),
353 springCount: Number((v >> 36n) & 0x7n),
354 edges: maskToEdges(Number((v >> 32n) & 0xfn)),
03c2cc12 2026-07-01 Pavel Safronov355 erosion: Number((v >> 44n) & 0xfn),
36e6a8b9 2026-07-02 Pavel Safronov356 reach: Number((v >> 48n) & 0xfn),
a7bf123a 2026-07-01 Pavel Safronov357 terrainSeed: Number(v & 0xffffffffn) >>> 0,
358 });
359}
360
361/** Bit per side (1 = wall): n=8, e=4, s=2, w=1. */
362function edgesToMask(e: Edges): number {
363 return (
364 (e.n === 'wall' ? 8 : 0) |
365 (e.e === 'wall' ? 4 : 0) |
366 (e.s === 'wall' ? 2 : 0) |
367 (e.w === 'wall' ? 1 : 0)
368 );
369}
370
371function maskToEdges(mask: number): Edges {
372 const side = (bit: number): EdgeType => ((mask >> bit) & 1 ? 'wall' : 'ocean');
373 return { n: side(3), e: side(2), s: side(1), w: side(0) };
374}
375
376/** If every side is a wall, water could never exit — force the west side ocean. */
377function ensureOcean(edges: Edges): Edges {
378 const allWall =
379 edges.n === 'wall' && edges.e === 'wall' && edges.s === 'wall' && edges.w === 'wall';
380 return allWall ? { ...edges, w: 'ocean' } : { ...edges };
381}
382
383/**
384 * Roll a per-side edge configuration. Each side is a wall ~35% of the time, with
385 * at least one ocean side kept so water can always exit somewhere.
386 */
387function rollEdges(rng: Rng): Edges {
388 const pick = (): EdgeType => (rng() < 0.35 ? 'wall' : 'ocean');
389 return ensureOcean({ n: pick(), e: pick(), s: pick(), w: pick() });
390}
391
392/**
36e6a8b9 2026-07-02 Pavel Safronov393 * Sample the indices of `k` distinct candidates — drawn from `pools` (each an
394 * array of indices into `candidates`, e.g. a reach-narrowed subset) — that are
395 * pairwise at least `minGap` apart (Chebyshev distance). Pools are tried in
396 * order: every candidate in `pools[0]` is exhausted (shuffled, so still
397 * random within the tier) before any candidate from `pools[1]` is considered,
398 * so a lower-priority pool (e.g. shore cells that must be avoided if
399 * possible) is only reached into for the picks the higher-priority pool
400 * genuinely can't fill. Returns fewer than `k` only if the spacing can't be
401 * met even across every pool. Returns indices into `candidates` (not `pools`)
402 * so callers can look up precomputed per-cell data — notably each candidate's
403 * outflow signature — which must stay indexed over the *full* candidate set
404 * for the uniqueness check to be meaningful.
a7bf123a 2026-07-01 Pavel Safronov405 */
36e6a8b9 2026-07-02 Pavel Safronov406function pickSpringIdx(candidates: Cell[], pools: number[][], k: number, rng: Rng, minGap: number): number[] {
407 const order: number[] = [];
408 for (const pool of pools) {
409 const shuffled = [...pool];
410 for (let i = shuffled.length - 1; i > 0; i--) {
411 const j = Math.floor(rng() * (i + 1));
412 [shuffled[i], shuffled[j]] = [shuffled[j], shuffled[i]];
413 }
414 order.push(...shuffled);
a7bf123a 2026-07-01 Pavel Safronov415 }
416
7b368f91 2026-07-01 Pavel Safronov417 const chosen: number[] = [];
418 for (const i of order) {
419 const c = candidates[i];
420 const spaced = chosen.every((o) => {
421 const p = candidates[o];
422 return Math.max(Math.abs(p.x - c.x), Math.abs(p.y - c.y)) >= minGap;
423 });
a7bf123a 2026-07-01 Pavel Safronov424 if (spaced) {
7b368f91 2026-07-01 Pavel Safronov425 chosen.push(i);
a7bf123a 2026-07-01 Pavel Safronov426 if (chosen.length === k) break;
427 }
428 }
429 return chosen;
430}
431
7b368f91 2026-07-01 Pavel Safronov432// ---------------------------------------------------------------------------
433// Uniqueness: is the chosen spring set the only one reproducing its signature?
434// ---------------------------------------------------------------------------
435
436/**
437 * A signature is *unambiguous* iff exactly one size-`k` set of candidates
438 * reproduces it. Any candidate whose footprint isn't wholly inside the target
439 * can't belong to such a set (it would wet a non-target edge), so only those need
440 * be considered — usually a small pool. We then count size-`k` exact covers of
441 * the target, stopping at the first duplicate; the chosen set is always one of
442 * them, so "unique" means the count is exactly 1.
443 */
444function isUniqueSolution(sig: bigint[], target: bigint, k: number): boolean {
445 const compat: bigint[] = [];
446 for (const s of sig) if (s !== 0n && (s | target) === target) compat.push(s);
447 return countCovers(compat, target, k, 2) === 1;
448}
449
450/**
451 * Count size-`k` subsets of `masks` whose bitwise-OR equals `target`, stopping
452 * once `cap` is reached. A bounded node budget guards against pathological pools;
453 * exhausting it reports `cap` (treat as ambiguous) rather than falsely claiming
454 * uniqueness.
455 */
456function countCovers(masks: bigint[], target: bigint, k: number, cap: number): number {
457 let count = 0;
458 let budget = 200_000;
459 const n = masks.length;
460
461 const dfs = (start: number, chosen: number, acc: bigint): void => {
462 if (chosen === k) {
463 if (acc === target) count++;
464 return;
465 }
466 if (n - start < k - chosen) return; // too few candidates left to reach k
467 for (let i = start; i < n; i++) {
468 if (--budget < 0) {
469 count = cap; // give up — conservatively treat as ambiguous
470 return;
471 }
472 dfs(i + 1, chosen + 1, acc | masks[i]);
473 if (count >= cap) return;
474 }
475 };
476
477 dfs(0, 0, 0n);
478 return count;
479}
480
481/** Bitmask of a flow's wet border cells, one bit per row-major cell index. */
482function outflowMask(outflow: Cell[], width: number): bigint {
483 let m = 0n;
484 for (const c of outflow) m |= 1n << BigInt(c.y * width + c.x);
485 return m;
486}
487
488/** Number of set bits in `m` (the width of a signature, in border cells). */
489function popcount(m: bigint): number {
490 let n = 0;
491 for (let v = m; v > 0n; v >>= 1n) n += Number(v & 1n);
492 return n;
493}
494
a7bf123a 2026-07-01 Pavel Safronov495/** Mark the wet border cells of a flow as a row-major signature mask. */
496function borderSignature(outflow: Cell[], width: number, height: number): Uint8Array {
497 const sig = new Uint8Array(width * height);
498 for (const c of outflow) sig[c.y * width + c.x] = 1;
499 return sig;
500}