179 lines
7.6 KiB
JavaScript
179 lines
7.6 KiB
JavaScript
// Verifier for Tents & Trees (Node only — no browser).
|
||
//
|
||
// 1. Unit-tests the solver against hand-built boards (unique / multi / no
|
||
// solution, and the no-touch rule).
|
||
// 2. Unit-tests the play-state helpers (toggle, diagnose, solve, answer).
|
||
// 3. Generation soak: produces puzzles for every difficulty and re-verifies
|
||
// each one independently (validity + uniqueness).
|
||
//
|
||
// Usage: node tools/verifyTents.js
|
||
|
||
import {
|
||
DIFFICULTIES, DIFFICULTY_ORDER, countSolutions, generatePuzzle,
|
||
newGame, toggleTent, diagnose, isSolved, solutionTents, keyOf,
|
||
} from '../src/games/tents/TentsLogic.js';
|
||
|
||
let passes = 0;
|
||
let failures = 0;
|
||
function check(name, cond, detail = '') {
|
||
if (cond) { passes++; console.log(` ok ${name}`); }
|
||
else { failures++; console.error(`FAIL ${name}${detail ? ` — ${detail}` : ''}`); }
|
||
}
|
||
|
||
// ── Solver unit tests ────────────────────────────────────────────────────────
|
||
|
||
console.log('[verify] solver');
|
||
|
||
// Two trees far apart, each with a single candidate: exactly one solution.
|
||
{
|
||
// 4×4: trees at (1,1) and (2,2) would share diagonal cells; use (0,0) & (3,3).
|
||
const trees = [[0, 0], [3, 3]];
|
||
const sols = countSolutions(trees, 4, { limit: 5 });
|
||
// (0,0)'s candidates: (1,0),(0,1); (3,3)'s: (2,3),(3,2). None touch → 4 solutions.
|
||
check('disjoint trees → 4 solutions', sols.length === 4, `got ${sols.length}`);
|
||
}
|
||
|
||
{
|
||
// 4×4: trees at (1,1) and (2,2) — diagonal neighbours. Their candidate sets
|
||
// overlap in touching cells; tent for one blocks the other's options.
|
||
const trees = [[1, 1], [2, 2]];
|
||
const sols = countSolutions(trees, 4, { limit: 5 });
|
||
// Each tree's candidates: (0,1),(1,0),(1,2) and (2,1),(3,2),(2,3).
|
||
// Valid pairs must not touch (8-way): (0,1)&(2,3)? dist (2,2) ok → no touch.
|
||
// Count them all: any combo where neither touches the other.
|
||
check('diagonal trees → 0 or more, each valid', sols.length >= 0, `got ${sols.length}`);
|
||
for (const sol of sols) {
|
||
const [a, b] = sol;
|
||
const touch = Math.max(Math.abs(a[0] - b[0]), Math.abs(a[1] - b[1])) <= 1;
|
||
check(`solution ${JSON.stringify(sol)} tents do not touch`, !touch);
|
||
}
|
||
}
|
||
|
||
{
|
||
// Tree in a corner with a tree right beside it: (0,0) & (0,1).
|
||
// (0,0)'s tent: (1,0) or (0,1)=tree → only (1,0). (0,1)'s tent: (0,0) tree,
|
||
// (0,2), (1,1). (1,0) touches (1,1) and (0,2)? (1,0)-(0,2): Δ(1,2) no touch.
|
||
// (1,0)-(1,1): touch. So (0,1)'s tent must be (0,2). One solution.
|
||
const sols = countSolutions([[0, 0], [0, 1]], 4, { limit: 5 });
|
||
check('corner pair → exactly 1 solution', sols.length === 1, `got ${sols.length}`);
|
||
check('corner pair solution', JSON.stringify(sols[0]) === JSON.stringify([[1, 0], [0, 2]]),
|
||
JSON.stringify(sols[0]));
|
||
}
|
||
|
||
{
|
||
// A tree walled in by trees (no empty orthogonal neighbour) → no solutions.
|
||
const trees = [[1, 1], [0, 1], [2, 1], [1, 0]];
|
||
const sols = countSolutions(trees, 4, { limit: 5 });
|
||
check('walled-in tree → no solutions', sols.length === 0, `got ${sols.length}`);
|
||
}
|
||
|
||
{
|
||
// Three in a row: trees (1,1),(2,1),(3,1) on 5×5.
|
||
// (1,1) tents: (0,1),(1,0),(1,2). (2,1): (2,0),(2,2). (3,1): (3,0),(3,2),(4,1).
|
||
// Must be non-touching. (2,1)'s only options (2,0)/(2,2) touch (1,0)/(1,2)
|
||
// diagonally and (3,0)/(3,2) diagonally → whichever chosen blocks both
|
||
// neighbours' matching side. Check solver finds the true count.
|
||
const sols = countSolutions([[1, 1], [2, 1], [3, 1]], 5, { limit: 10 });
|
||
check('three-in-row solvable', sols.length > 0, `got ${sols.length}`);
|
||
for (const sol of sols) {
|
||
let ok = true;
|
||
for (let i = 0; i < sol.length && ok; i++)
|
||
for (let j = i + 1; j < sol.length; j++)
|
||
if (Math.max(Math.abs(sol[i][0] - sol[j][0]), Math.abs(sol[i][1] - sol[j][1])) <= 1) ok = false;
|
||
check(`3-in-row solution ${JSON.stringify(sol)} non-touching`, ok);
|
||
}
|
||
}
|
||
|
||
// ── Play-state unit tests ────────────────────────────────────────────────────
|
||
|
||
console.log('[verify] play state');
|
||
|
||
{
|
||
// Fixed 4×4 puzzle with a known unique solution.
|
||
const trees = [[0, 0], [0, 1]];
|
||
const sols = countSolutions(trees, 4, { limit: 5 });
|
||
check('fixture has unique solution', sols.length === 1, `got ${sols.length}`);
|
||
const puzzle = {
|
||
difficulty: 'test', size: 4, trees,
|
||
rowCounts: [0, 0, 0, 0].map((_, r) => sols[0].filter(([, rr]) => rr === r).length),
|
||
colCounts: [0, 0, 0, 0].map((_, c) => sols[0].filter(([cc]) => cc === c).length),
|
||
solution: sols[0],
|
||
};
|
||
const g = newGame(puzzle);
|
||
|
||
check('clicking a tree is a no-op', toggleTent(g, 0, 0).changed === false);
|
||
check('place then remove round-trips',
|
||
toggleTent(g, 1, 0).placed === true && toggleTent(g, 1, 0).placed === false);
|
||
|
||
// Wrong tent (not beside any tree).
|
||
toggleTent(g, 3, 3);
|
||
let d = diagnose(g);
|
||
check('lonely tent flagged', d.badTents.has(keyOf(3, 3)));
|
||
|
||
// Two tents touching.
|
||
toggleTent(g, 1, 0);
|
||
toggleTent(g, 1, 1);
|
||
d = diagnose(g);
|
||
check('touching tents flagged', d.badTents.has(keyOf(1, 0)) && d.badTents.has(keyOf(1, 1)));
|
||
|
||
// Over-count a row: row 0 count is 1; add a second tent in row 0.
|
||
g.tents.add(keyOf(3, 0));
|
||
d = diagnose(g);
|
||
check('overfull row flagged', d.badRows.has(0));
|
||
|
||
check('not solved while broken', isSolved(g) === false);
|
||
|
||
// Solve it exactly.
|
||
g.tents.clear();
|
||
for (const [c, r] of puzzle.solution) g.tents.add(keyOf(c, r));
|
||
d = diagnose(g);
|
||
check('solution has no violations',
|
||
d.badTents.size + d.badTrees.size + d.badRows.size + d.badCols.size === 0);
|
||
check('solution counts as solved', isSolved(g) === true);
|
||
|
||
// Two tents on one tree → bad tree.
|
||
g.tents.add(keyOf(1, 1));
|
||
d = diagnose(g);
|
||
check('double-claimed tree flagged', d.badTrees.has(keyOf(0, 1)));
|
||
check('no longer solved', isSolved(g) === false);
|
||
}
|
||
|
||
// ── Generation soak ──────────────────────────────────────────────────────────
|
||
|
||
console.log('[verify] generation');
|
||
|
||
for (const key of DIFFICULTY_ORDER) {
|
||
const def = DIFFICULTIES[key];
|
||
const t0 = Date.now();
|
||
let puzzles = 0;
|
||
for (let i = 0; i < 12; i++) {
|
||
const p = generatePuzzle(key);
|
||
puzzles++;
|
||
// Independent re-verification.
|
||
// Independent re-verification: (trees + edge counts) must admit exactly
|
||
// one solution, and it must be the shipped one.
|
||
const sols = countSolutions(p.trees, p.size, { limit: 2, rowCounts: p.rowCounts, colCounts: p.colCounts });
|
||
const okUnique = sols.length === 1 && JSON.stringify(sols[0]) === JSON.stringify(p.solution);
|
||
check(`${key}: puzzle ${i} unique & matches solution`, okUnique,
|
||
`sols=${sols.length}`);
|
||
const d = (function () {
|
||
const g = newGame(p);
|
||
for (const [c, r] of p.solution) g.tents.add(keyOf(c, r));
|
||
return { g, d: diagnose(g) };
|
||
})();
|
||
check(`${key}: puzzle ${i} solution is valid`,
|
||
d.d.badTents.size + d.d.badTrees.size + d.d.badRows.size + d.d.badCols.size === 0
|
||
&& isSolved(d.g));
|
||
check(`${key}: puzzle ${i} has ${def.trees} trees`, p.trees.length === def.trees,
|
||
`got ${p.trees.length}`);
|
||
check(`${key}: puzzle ${i} counts sum to tree count`,
|
||
p.rowCounts.reduce((a, b) => a + b, 0) === p.trees.length
|
||
&& p.colCounts.reduce((a, b) => a + b, 0) === p.trees.length);
|
||
}
|
||
const ms = Date.now() - t0;
|
||
console.log(` · ${key}: ${puzzles} puzzles in ${ms} ms (${(ms / 12).toFixed(1)} ms avg)`);
|
||
}
|
||
|
||
console.log(`\n[verify] ${passes} passed, ${failures} failed`);
|
||
process.exit(failures ? 1 : 0);
|