1// Geometry and colour over manifest v3 layouts: owner index from rect2// unions, overlap and junction cells, holes, hue colouring of the adjacency3// graph, v2 conversion, delta coding, and the owner index build time at4// G=1000.5import { assert, assertEquals } from "@std/assert";6import {7 buildGeometry,8 cellId,9 cellXY,10 colourTiles,11 deltaDecode,12 deltaEncode,13 fold,14 foldAll,15 type GameEvent,16 hueOf,17 HUES,18 isHole,19 type ManifestV2,20 neighboursOf,21 normaliseManifest,22 ownerCount,23 ownersOf,24 tileContains,25 zoneCells,26} from "../lib/fold.ts";27import { cellFill, highestStatus, meanHueLab } from "../lib/colour.ts";28import { gridLayout, scatterLayout, synthesise } from "./fixture.ts";2930for (31 const [name, L] of [32 ["grid 27", gridLayout(2, 14)],33 ["scatter 100", scatterLayout("a", 100)],34 ["scatter 60", scatterLayout("b", 60)],35 ] as const36) {37 Deno.test(`geometry ${name}`, () => {38 const out = synthesise(L);39 const m = out.manifest;40 const G = m.G;41 const geo = buildGeometry(m);42 let overlaps = 0, junctions = 0, holes = 0;43 for (let y = 0; y < G; y++) {44 for (let x = 0; x < G; x++) {45 const id = cellId(x, y, G);46 const owners = ownersOf(geo, id);47 const expect = m.tiles.filter((t) => tileContains(t, x, y)).map((t) =>48 t.id49 );50 assertEquals(owners, expect, `owners of ${x},${y}`);51 assertEquals(isHole(geo, id), owners.length === 0);52 assertEquals(cellXY(id, G), [x, y]);53 if (owners.length === 0) holes++;54 if (owners.length === 2) overlaps++;55 if (owners.length >= 3) junctions++;56 // tiles sharing a cell never share a hue57 const hues = hueOf(geo, id);58 assertEquals(new Set(hues).size, hues.length, `hue clash at ${x},${y}`);59 for (const h of hues) assert(h >= 0 && h < HUES);60 }61 }62 assertEquals(geo.holes, holes);63 assert(overlaps > 0, "there are shared cells");64 if (L.kind === "scatter") {65 assert(holes > 0, "a scattered field has holes");66 assert(junctions > 0, "some cell has three owners");67 assert(68 m.tiles.some((t) => t.rects.length > 1),69 "some tile is not a rectangle",70 );71 }72 // the solution marks holes and nothing else with '.'73 for (let y = 0; y < G; y++) {74 for (let x = 0; x < G; x++) {75 assertEquals(out.solution[y][x] === ".", isHole(geo, cellId(x, y, G)));76 }77 }78 // overlaps: partner ids and counts agree with the owner index, and the79 // adjacency is symmetric80 for (const t of m.tiles) {81 assertEquals(neighboursOf(t), geo.adjacency[t.id]);82 for (const o of t.overlaps) {83 let n = 0;84 for (const id of geo.cellsOf[t.id]) {85 if (ownersOf(geo, id).includes(o.with)) n++;86 }87 assertEquals(o.cells, n);88 assert(geo.adjacency[o.with].includes(t.id));89 }90 assertEquals(geo.cellsOf[t.id].length, t.cells);91 }92 // the fold starts with nothing known and no tile solved93 const s = fold([{94 rev: 0,95 t: "2026-01-01T00:00:00.000Z",96 kind: "manifest",97 game_id: "g",98 manifest: m,99 rules: { guess: "accept", depth: 0 },100 }]);101 assertEquals(Object.keys(s.cells).length, 0);102 assert(s.tiles.every((t) => t === "hidden"));103 assertEquals(s.totals.reward, 0);104 });105}106107Deno.test("v2 manifest converts to v3 shapes with the same geometry", () => {108 // a 2x2 of 8x8 with one filler zone, in the v2 shape the old logs carry109 const v2: ManifestV2 = {110 version: 2,111 id: "x",112 seed_commit: "x",113 G: 20,114 packer: { kind: "grid" },115 m_by_n: { "8": 2 },116 rules: {},117 seed_tile: 0,118 tiles: [119 {120 id: 0,121 x0: 0,122 y0: 0,123 n: 8,124 m: 2,125 seams: [{ side: "right", from: 0, len: 8, with: 1 }, {126 side: "bottom",127 from: 0,128 len: 8,129 with: 2,130 }],131 },132 {133 id: 1,134 x0: 7,135 y0: 0,136 n: 8,137 m: 2,138 seams: [{ side: "left", from: 0, len: 8, with: 0 }],139 },140 {141 id: 2,142 x0: 0,143 y0: 7,144 n: 8,145 m: 2,146 seams: [{ side: "top", from: 0, len: 8, with: 0 }],147 },148 ],149 zones: [{ id: 0, rects: [[15, 15, 2, 2]], values: "0110" }],150 k: "unmeasured",151 generator: "test",152 library: null,153 };154 const m = normaliseManifest(v2);155 assertEquals(m.version, 3);156 assertEquals(m.source_version, 2);157 assertEquals(m.tiles[0].rects, [[0, 0, 8, 8]]);158 assertEquals(m.tiles[0].cells, 64);159 assertEquals(m.tiles[0].overlaps, [{ with: 1, cells: 8 }, {160 with: 2,161 cells: 8,162 }]);163 assertEquals(m.tiles[1].overlaps, [{ with: 0, cells: 8 }, {164 with: 2,165 cells: 1,166 }]);167 assertEquals(zoneCells(m).length, 4);168 const geo = buildGeometry(m);169 assertEquals(ownersOf(geo, cellId(7, 7, 20)), [0, 1, 2]);170 assert(isHole(geo, cellId(15, 15, 20)));171 const s = fold([{172 rev: 0,173 t: "2026-01-01T00:00:00.000Z",174 kind: "manifest",175 game_id: "g",176 manifest: v2,177 rules: { guess: "accept", depth: 0 },178 }]);179 assertEquals(Object.keys(s.cells).length, 4, "zone cells known from rev 0");180});181182Deno.test("owner index at G=1000 builds fast", () => {183 const m = synthesise(scatterLayout("big", 1000, 0.6)).manifest;184 const t0 = performance.now();185 const geo = buildGeometry(m);186 const ms = performance.now() - t0;187 assert(ms < 1500, `geometry took ${ms.toFixed(0)}ms`);188 assert(m.tiles.length > 1000, `${m.tiles.length} tiles`);189 let maxOwners = 0;190 for (let id = 0; id < m.G * m.G; id++) {191 maxOwners = Math.max(maxOwners, ownerCount(geo, id));192 }193 assert(maxOwners >= 2, `max owners ${maxOwners}`);194 for (const t of m.tiles) {195 for (const u of geo.adjacency[t.id]) {196 assert(geo.hues[t.id] !== geo.hues[u], `hue clash ${t.id} ${u}`);197 }198 }199});200201Deno.test("colouring is deterministic and collision-free on a dense graph", () => {202 // a wheel: hub 0 adjacent to everyone, rim a cycle203 const n = 12;204 const adj: number[][] = Array.from({ length: n }, () => []);205 for (let i = 1; i < n; i++) {206 adj[0].push(i);207 adj[i].push(0);208 const j = i === n - 1 ? 1 : i + 1;209 adj[i].push(j);210 adj[j].push(i);211 }212 const a = colourTiles(adj), b = colourTiles(adj);213 assertEquals(a, b);214 for (let i = 0; i < n; i++) {215 for (const j of adj[i]) assert(a[i] !== a[j]);216 }217});218219Deno.test("colour: fixed lightness, no pyramid at seams", () => {220 const single = meanHueLab([0]);221 const seam = meanHueLab([0, 1]);222 const corner = meanHueLab([0, 1, 3, 4]);223 assertEquals(single[0], seam[0]);224 assertEquals(single[0], corner[0]);225 const chroma = (lab: number[]) => Math.hypot(lab[1], lab[2]);226 assert(Math.abs(chroma(single) - chroma(seam)) < 1e-9);227 assert(Math.abs(chroma(single) - chroma(corner)) < 1e-9);228 assert(/^#[0-9a-f]{6}$/.test(cellFill([0, 1], "solved")));229 assert(/^#[0-9a-f]{6}$/.test(cellFill([], "solved")));230 // an unknown cell is never lighter than a known one on the dark theme231 assert(cellFill([2], "revealed", false) !== cellFill([2], "revealed", true));232 assertEquals(highestStatus(["hidden", "solved", "revealed"]), "solved");233 assertEquals(highestStatus(["hidden", "revealed"]), "revealed");234});235236Deno.test("delta coding round trips", () => {237 const ids = [5, 1, 900, 901, 42];238 assertEquals(deltaDecode(deltaEncode(ids)), [1, 5, 42, 900, 901]);239});240241// The fold is incremental with structural sharing: a daily-sized synthetic242// game (every tile revealed and committed in one batch, ~2 events per tile)243// folds with every intermediate state kept in well under 2 s, and244// `State.cells` reads like a plain object.245Deno.test("fold throughput on a daily-sized field, states share memory", () => {246 const out = synthesise(scatterLayout("throughput", 530, 0.85), "t");247 const m = out.manifest;248 const G = m.G;249 const geo = buildGeometry(m);250 const t = "2026-01-01T00:00:00.000Z";251 const events: GameEvent[] = [{252 rev: 0,253 t,254 kind: "manifest",255 game_id: "g",256 manifest: m,257 rules: { guess: "accept", depth: 0 },258 }];259 events.push({260 rev: 1,261 t,262 kind: "join",263 agent: "a0",264 harness: "test",265 seed_tile: m.seed_tile,266 });267 // reveal + commit every tile in frontier order (BFS over the overlap graph)268 const order: number[] = [m.seed_tile];269 const seen = new Set(order);270 for (let i = 0; i < order.length; i++) {271 for (const u of geo.adjacency[order[i]]) {272 if (!seen.has(u)) {273 seen.add(u);274 order.push(u);275 }276 }277 }278 const known = new Set<number>();279 for (const id of order) {280 const givens = out.tiles[id].givens.filter(([c]) => !known.has(c));281 givens.forEach(([c]) => known.add(c));282 events.push({283 rev: events.length,284 t,285 kind: "batch",286 op: "reveal",287 agent: "a0",288 tile: id,289 givens,290 seam: [],291 intent: "",292 });293 const accepted = geo.cellsOf[id].filter((c) => !known.has(c)).map((c) => {294 known.add(c);295 return {296 id: c,297 v: (out.solution[Math.floor(c / G)][c % G] === "1" ? 1 : 0) as 0 | 1,298 class: "forced" as const,299 rules: ["balance"],300 };301 });302 events.push({303 rev: events.length,304 t,305 kind: "batch",306 op: "commit",307 agent: "a0",308 intent: "",309 accepted,310 rejected: [],311 ignored: [],312 solved: [],313 judge_ms: 0,314 });315 }316 const t0 = performance.now();317 const states = foldAll(events);318 const ms = performance.now() - t0;319 const last = states.at(-1)!;320 assert(m.tiles.length > 1500, `${m.tiles.length} tiles`);321 assert(ms < 2000, `fold of ${events.length} events took ${ms.toFixed(0)} ms`);322 assertEquals(last.solvedTiles, m.tiles.length);323 assertEquals(last.cellStore.size, Object.keys(last.cells).length);324 assertEquals(325 last.cells[order[0] * 0 + geo.cellsOf[m.seed_tile][0]]?.v,326 out327 .solution[Math.floor(geo.cellsOf[m.seed_tile][0] / G)][328 geo.cellsOf[m.seed_tile][0] % G329 ] === "1"330 ? 1331 : 0,332 );333 // structural sharing: consecutive states share untouched chunks334 const a = states[states.length - 2].cellStore.chunks;335 const b = last.cellStore.chunks;336 let shared = 0;337 for (let i = 0; i < a.length; i++) {338 if (a[i] !== undefined && a[i] === b[i]) shared++;339 }340 assert(shared > a.length / 2, `only ${shared} of ${a.length} chunks shared`);341 console.log(342 `fold ${events.length} events / ${m.tiles.length} tiles: ${343 ms.toFixed(0)344 } ms`,345 );346});