1// Test fixtures for manifest v3: synthetic layouts (a grid of squares, or a2// scattered field of shapes with rectangular overlaps and holes) wrapped in3// a synthetic generator output (random solution, random givens). Enough for4// fold and referee tests, which never check Takuzu validity; the judge is5// stubbed. No engine binary is involved.6import type { GenOutput, JudgeInput, JudgeOutput } from "../lib/engine.ts";7import {8 buildGeometry,9 cellId,10 type LocalRect,11 type Manifest,12 overlapsOf,13 tileMask,14 type TileSpec,15} from "../lib/fold.ts";1617export type Layout = {18 G: number;19 kind: string;20 seed_tile: number;21 seed_tiles?: number[];22 tiles: Omit<TileSpec, "overlaps" | "hash">[];23};2425/** Small deterministic PRNG so fixtures are stable per seed. */26export function rng(seed: string): () => number {27 let h = 2166136261;28 for (const ch of seed) h = Math.imul(h ^ ch.charCodeAt(0), 16777619);29 return () => {30 h = Math.imul(h ^ (h >>> 15), 2246822507);31 h = Math.imul(h ^ (h >>> 13), 3266489909);32 h ^= h >>> 16;33 return (h >>> 0) / 4294967296;34 };35}3637export function mFor(cells: number): number {38 return cells <= 64 ? 2 : cells <= 196 ? 3 : 4;39}4041function countCells(w: number, h: number, rects: LocalRect[]): number {42 return tileMask({ x0: 0, y0: 0, w, h, rects } as TileSpec).reduce(43 (a, b) => a + b,44 0,45 );46}4748/** X by X squares of side n on a pitch of n-1 (the phase-1 grid). */49export function gridLayout(X: number, n: number): Layout {50 const G = X * (n - 1) + 1;51 const tiles: Layout["tiles"] = [];52 for (let ty = 0; ty < X; ty++) {53 for (let tx = 0; tx < X; tx++) {54 tiles.push({55 id: tiles.length,56 x0: tx * (n - 1),57 y0: ty * (n - 1),58 w: n,59 h: n,60 rects: [[0, 0, n, n]],61 cells: n * n,62 m: mFor(n * n),63 });64 }65 }66 return { G, kind: "grid", seed_tile: Math.floor(tiles.length / 2), tiles };67}6869/**70 * Shapes of random even sides 6..16: a rectangle, or an L / T / plus made71 * of two even rectangles at even offsets so every line stays even.72 */73function randomShape(74 r: () => number,75): { w: number; h: number; rects: LocalRect[] } {76 const even = (lo: number, hi: number) =>77 lo + 2 * Math.floor(r() * ((hi - lo) / 2 + 1));78 const w = even(6, 16), h = even(6, 16);79 const roll = r();80 if (roll < 0.55) return { w, h, rects: [[0, 0, w, h]] };81 // second rectangle attached to the first82 const w2 = even(4, Math.max(4, w)), h2 = even(4, 12);83 const ox = even(0, w - w2);84 if (roll < 0.8) {85 // T or L: below the first, at an even offset86 return {87 w: Math.max(w, ox + w2),88 h: h + h2,89 rects: [[0, 0, w, h], [ox, h, w2, h2]],90 };91 }92 // plus / notched: second rect straddling the first vertically93 const oy = even(0, Math.max(0, h - 2));94 const W = Math.max(w, ox + w2), H = Math.max(h, oy + h2);95 return { w: W, h: H, rects: [[0, 0, w, h], [ox, oy, w2, h2]] };96}9798/**99 * A scattered field: shapes dropped at random positions, accepted when they100 * overlap the growing cluster by 4..25% of the smaller tile's cells (and by101 * at least 4 cells), are contained in no tile and contain none. Holes are102 * whatever stays uncovered. Deterministic per seed.103 */104export function scatterLayout(seed: string, G: number, target = 0.7): Layout {105 const r = rng(seed);106 const owners = new Uint8Array(G * G);107 const tiles: Layout["tiles"] = [];108 let covered = 0;109 const cellsOf = (110 t: { x0: number; y0: number; w: number; h: number; rects: LocalRect[] },111 ) => {112 const mask = tileMask(t as TileSpec);113 const ids: number[] = [];114 for (let y = 0; y < t.h; y++) {115 for (let x = 0; x < t.w; x++) {116 if (mask[y * t.w + x]) ids.push(cellId(t.x0 + x, t.y0 + y, G));117 }118 }119 return ids;120 };121 const place = (t: Layout["tiles"][number]) => {122 tiles.push(t);123 for (const id of cellsOf(t)) {124 if (owners[id] === 0) covered++;125 owners[id]++;126 }127 };128 // seed tile near the middle129 {130 const s = randomShape(r);131 place({132 id: 0,133 x0: Math.floor(G / 2 - s.w / 2),134 y0: Math.floor(G / 2 - s.h / 2),135 ...s,136 cells: countCells(s.w, s.h, s.rects),137 m: mFor(countCells(s.w, s.h, s.rects)),138 });139 }140 let misses = 0;141 while (covered < target * G * G && misses < 4000) {142 const s = randomShape(r);143 if (s.w > G || s.h > G) {144 misses++;145 continue;146 }147 // drop it near a random tile of the cluster so it can touch something148 const anchor = tiles[Math.floor(r() * tiles.length)];149 const jx = Math.floor(r() * (anchor.w + s.w - 2)) - (s.w - 1);150 const jy = Math.floor(r() * (anchor.h + s.h - 2)) - (s.h - 1);151 const t = {152 id: tiles.length,153 x0: Math.max(0, Math.min(G - s.w, anchor.x0 + jx)),154 y0: Math.max(0, Math.min(G - s.h, anchor.y0 + jy)),155 ...s,156 cells: countCells(s.w, s.h, s.rects),157 m: 0,158 };159 t.m = mFor(t.cells);160 const ids = cellsOf(t);161 let shared = 0;162 for (const id of ids) if (owners[id] > 0) shared++;163 if (shared < 4 || shared > 0.25 * t.cells) {164 misses++;165 continue;166 }167 // per neighbour: not contained either way, overlap under a quarter168 let ok = true;169 const byTile = new Map<number, number>();170 const near = tiles.filter((o) =>171 o.x0 < t.x0 + t.w && o.x0 + o.w > t.x0 && o.y0 < t.y0 + t.h &&172 o.y0 + o.h > t.y0173 );174 const masks = new Map(near.map((o) => [o.id, tileMask(o as TileSpec)]));175 for (const id of ids) {176 if (owners[id] === 0) continue;177 const gx = id % G, gy = Math.floor(id / G);178 for (const o of near) {179 const lx = gx - o.x0, ly = gy - o.y0;180 if (lx < 0 || ly < 0 || lx >= o.w || ly >= o.h) continue;181 if (masks.get(o.id)![ly * o.w + lx]) {182 byTile.set(o.id, (byTile.get(o.id) ?? 0) + 1);183 }184 }185 }186 for (const [oid, n] of byTile) {187 const o = tiles[oid];188 if (189 n === o.cells || n === t.cells || n > 0.25 * Math.min(o.cells, t.cells)190 ) {191 ok = false;192 }193 }194 if (!ok) {195 misses++;196 continue;197 }198 place(t);199 misses = 0;200 }201 return { G, kind: "scatter", seed_tile: 0, tiles };202}203204/**205 * Choose n seed tiles spread over the layout by farthest-point sampling206 * over the overlap graph (a stand-in for the field generator's one seed207 * per chunk). The first is the layout's seed tile.208 */209export function withSeeds(L: Layout, n: number): Layout {210 const tiles: TileSpec[] = L.tiles.map((t) => ({ ...t, overlaps: [] }));211 const geo = buildGeometry({212 version: 3,213 id: "s",214 seed_commit: "s",215 G: L.G,216 packer: { kind: L.kind },217 rules: {},218 seed_tile: L.seed_tile,219 tiles,220 k: "unmeasured",221 generator: "fixture",222 library: null,223 });224 const dist = (from: number) => {225 const d = new Array(tiles.length).fill(-1);226 d[from] = 0;227 const q = [from];228 for (let i = 0; i < q.length; i++) {229 for (const u of geo.adjacency[q[i]]) {230 if (d[u] < 0) {231 d[u] = d[q[i]] + 1;232 q.push(u);233 }234 }235 }236 return d;237 };238 const seeds = [L.seed_tile];239 let best = dist(L.seed_tile).map((d) => (d < 0 ? 0 : d));240 while (seeds.length < n) {241 let pick = -1;242 for (let t = 0; t < tiles.length; t++) {243 if (!seeds.includes(t) && (pick < 0 || best[t] > best[pick])) pick = t;244 }245 if (pick < 0) break;246 seeds.push(pick);247 const d = dist(pick);248 best = best.map((b, t) => Math.min(b, d[t] < 0 ? b : d[t]));249 }250 return { ...L, seed_tiles: seeds };251}252253/** Wrap a layout as generator output: random solution, ~30% givens per tile. */254export function synthesise(255 L: Layout,256 seed = "fixture",257): GenOutput & { manifest: Manifest } {258 const r = rng(seed);259 const G = L.G;260 const tiles: TileSpec[] = L.tiles.map((t) => ({261 ...t,262 hash: `h${t.id}`,263 overlaps: [],264 }));265 const manifest: Manifest = {266 version: 3,267 id: `fixture-${L.kind}-${G}`,268 seed_commit: `fixture-${L.kind}-${G}`,269 G,270 packer: { kind: L.kind },271 rules: { overlaps: true, cross_tile: false },272 seed_tile: L.seed_tile,273 ...(L.seed_tiles ? { seed_tiles: L.seed_tiles } : {}),274 tiles,275 k: "unmeasured",276 generator: "fixture",277 library: null,278 };279 const geo = buildGeometry(manifest);280 for (const t of tiles) t.overlaps = overlapsOf(geo, t.id);281 const solution: string[] = [];282 for (let y = 0; y < G; y++) {283 let row = "";284 for (let x = 0; x < G; x++) {285 const id = cellId(x, y, G);286 row += geo.ownerStart[id] === geo.ownerStart[id + 1]287 ? "."288 : (r() < 0.5 ? "0" : "1");289 }290 solution.push(row);291 }292 // givens: 30% of each tile's cells that no other tile shares293 const genTiles = tiles.map((t) => {294 const givens: [number, 0 | 1][] = [];295 for (const id of geo.cellsOf[t.id]) {296 if (geo.ownerStart[id + 1] - geo.ownerStart[id] > 1) continue;297 if (r() < 0.3) {298 givens.push([id, solution[Math.floor(id / G)][id % G] === "1" ? 1 : 0]);299 }300 }301 return { id: t.id, givens };302 });303 return { manifest, solution, tiles: genTiles };304}305306/** Deterministic stand-in for the engine judge: even ids forced, odd guess. */307export function stubJudge(input: JudgeInput): Promise<JudgeOutput> {308 const known = new Set(input.known.map(([id]) => id));309 return Promise.resolve({310 ms: 0,311 steps: 0,312 results: input.candidates.map(([id, v]) => ({313 id,314 v,315 class: known.has(id) ? "known" : id % 2 === 0 ? "forced" : "guess",316 rules: known.has(id) ? ["seam"] : id % 2 === 0 ? ["balance"] : [],317 })),318 });319}320321/** Place a layout on a larger canvas, shifted by (dx, dy): a cluster with room to grow. */322export function embed(L: Layout, G: number, dx: number, dy: number): Layout {323 return {324 ...L,325 G,326 tiles: L.tiles.map((t) => ({ ...t, x0: t.x0 + dx, y0: t.y0 + dy })),327 };328}329330/**331 * A synthetic growth ring: rectangles dropped just outside the cluster's332 * bounding box, each overlapping some existing border tile by at least 4333 * cells (so it is pinnable) and no other new tile. Ids continue from the334 * base; two of the new tiles become seed tiles. Returns the delta layout335 * (new tiles only) with `seed_tiles` for the ring.336 */337export function growLayout(338 base: Layout,339 seed: string,340 ring: number,341): Layout {342 const r = rng(`${seed}|grow|${ring}`);343 const G = base.G;344 const owners = new Uint8Array(G * G);345 const cellsOf = (346 t: { x0: number; y0: number; w: number; h: number; rects: LocalRect[] },347 ) => {348 const mask = tileMask(t as TileSpec);349 const ids: number[] = [];350 for (let y = 0; y < t.h; y++) {351 for (let x = 0; x < t.w; x++) {352 if (353 mask[y * t.w + x] && t.x0 + x >= 0 && t.y0 + y >= 0 && t.x0 + x < G &&354 t.y0 + y < G355 ) {356 ids.push(cellId(t.x0 + x, t.y0 + y, G));357 }358 }359 }360 return ids;361 };362 for (const t of base.tiles) for (const id of cellsOf(t)) owners[id] = 1;363 let x0 = G, y0 = G, x1 = 0, y1 = 0;364 for (const t of base.tiles) {365 x0 = Math.min(x0, t.x0);366 y0 = Math.min(y0, t.y0);367 x1 = Math.max(x1, t.x0 + t.w);368 y1 = Math.max(y1, t.y0 + t.h);369 }370 const fresh = new Uint8Array(G * G);371 const tiles: Layout["tiles"] = [];372 let id = base.tiles.length;373 const tryPlace = (tx: number, ty: number, w: number, h: number) => {374 if (tx < 0 || ty < 0 || tx + w > G || ty + h > G) return;375 const t = { x0: tx, y0: ty, w, h, rects: [[0, 0, w, h]] as LocalRect[] };376 const ids = cellsOf(t);377 let shared = 0;378 for (const c of ids) {379 if (fresh[c]) return; // new tiles do not overlap each other380 if (owners[c]) shared++;381 }382 if (shared < 4 || shared > ids.length / 4) return;383 for (const c of ids) fresh[c] = 1;384 tiles.push({ id: id++, ...t, cells: ids.length, m: mFor(ids.length) });385 };386 // walk the four sides of the box, dropping tiles that straddle it387 for (let x = x0 - 2; x < x1; x += 6 + Math.floor(r() * 4)) {388 const w = 8, h = 6 + 2 * Math.floor(r() * 3);389 tryPlace(x, y0 - h + 2 + Math.floor(r() * 2), w, h);390 tryPlace(x, y1 - 2 - Math.floor(r() * 2), w, h);391 }392 for (let y = y0 - 2; y < y1; y += 6 + Math.floor(r() * 4)) {393 const w = 6 + 2 * Math.floor(r() * 3), h = 8;394 tryPlace(x0 - w + 2 + Math.floor(r() * 2), y, w, h);395 tryPlace(x1 - 2 - Math.floor(r() * 2), y, w, h);396 }397 const seeds = tiles.length >= 2398 ? [tiles[0].id, tiles[tiles.length - 1].id]399 : tiles.map((t) => t.id);400 return {401 G,402 kind: base.kind,403 seed_tile: base.seed_tile,404 seed_tiles: seeds,405 tiles,406 };407}408409/**410 * Wrap a growth ring as the engine's delta output over a base output: the411 * manifest holds only the new tiles (overlaps computed on the union), the412 * solution is the base solution with the new cells filled in (old cells413 * unchanged), the private tiles are the new ones.414 */415export function synthesiseDelta(416 base: GenOutput & { manifest: Manifest },417 delta: Layout,418 ring: number,419 seed = "fixture",420): GenOutput & { manifest: Manifest } {421 const r = rng(`${seed}|delta|${ring}`);422 const G = base.manifest.G;423 const union: Manifest = {424 ...base.manifest,425 tiles: [426 ...base.manifest.tiles,427 ...delta.tiles.map((t) => ({ ...t, hash: `h${t.id}`, overlaps: [] })),428 ],429 };430 const geo = buildGeometry(union);431 const newTiles: TileSpec[] = delta.tiles.map((t) => ({432 ...t,433 hash: `h${t.id}`,434 overlaps: overlapsOf(geo, t.id),435 }));436 const solution = base.solution.map((row, y) => {437 let out = "";438 for (let x = 0; x < G; x++) {439 const id = cellId(x, y, G);440 const covered = geo.ownerStart[id] !== geo.ownerStart[id + 1];441 out += row[x] !== "." ? row[x] : covered ? (r() < 0.5 ? "0" : "1") : ".";442 }443 return out;444 });445 const genTiles = newTiles.map((t) => {446 const givens: [number, 0 | 1][] = [];447 for (const id of geo.cellsOf[t.id]) {448 if (geo.ownerStart[id + 1] - geo.ownerStart[id] > 1) continue;449 if (r() < 0.3) {450 givens.push([id, solution[Math.floor(id / G)][id % G] === "1" ? 1 : 0]);451 }452 }453 return { id: t.id, givens };454 });455 const field = {456 ...(base.manifest.field ?? { chunks: 0, chunk_g: 0, band: 0 }),457 grown: ring,458 };459 const manifest: Manifest = {460 ...base.manifest,461 tiles: newTiles,462 seed_tiles: delta.seed_tiles ?? [],463 field,464 };465 return {466 manifest,467 solution,468 tiles: genTiles,469 stats: { exhausted: newTiles.length === 0 ? 1 : 0 },470 };471}