// verify.mjs — offline proof of every claim in "The Game the Golden Ratio Wins".
//   node research/wythoffs-game/verify.mjs
//
// Wythoff's game (Wythoff 1907 / "Wythoff's Nim" / Wythoff's queen):
//   Two piles of tokens (a,b). A legal move is one of:
//     - remove k>=1 from pile a,
//     - remove k>=1 from pile b,
//     - remove the same k>=1 from BOTH piles.
//   Normal play: the player who removes the last token (moves to (0,0)) wins;
//   equivalently the player who cannot move (is at (0,0)) loses.
//   Geometric form: a single chess queen on a quarter-infinite board at (a,b),
//   moving only W, S, or SW (toward the corner). Whoever lands it on (0,0) wins.
//
// The claims this checks, every one independently:
//   1. The cold positions (P-positions: the player to move loses) computed by
//      brute-force retrograde game analysis EQUAL (floor(n*phi), floor(n*phi^2)).
//   2. They also equal the mex construction a_n = mex(prev), b_n = a_n + n.
//   3. b_n = a_n + n exactly (because phi^2 = phi + 1).
//   4. The two sequences A=(a_n) and B=(b_n), n>=1, PARTITION the positive
//      integers — every k>=1 in exactly one (Beatty/Rayleigh, 1/phi+1/phi^2=1).
//   5. 1/phi + 1/phi^2 = 1 exactly (the Beatty condition).
//   6. From every hot (N-) position there is >=1 move to a cold position, and
//      from every cold position there is none (the optimal-play invariant).
//   7. The first terms match OEIS A000201 (lower Wythoff) and A001950 (upper).
//   8. Grundy/Sprague-Grundy value G(a,b)=0 exactly on the cold positions.
//
// Nothing here is asserted on the page that is not first proven here in code.

let fails = 0, checks = 0;
const ok = (cond, msg) => { checks++; if (!cond) { fails++; console.log('  ✗ ' + msg); } else console.log('  ✓ ' + msg); };
const PHI = (1 + Math.sqrt(5)) / 2;

// ---- exact integer floor(n*phi) and floor(n*phi^2) via BigInt isqrt --------
// floor(n*sqrt5) = isqrt(5 n^2); floor(n*phi) = (n + floor(n*sqrt5)) / 2 (integer
// division is exact: the leftover fractional part of n*sqrt5 is < 1, halved < 1/2,
// never bridges to the next integer). floor(n*phi^2) = floor(n*phi) + n.
function isqrt(n) { // BigInt integer square root
  if (n < 0n) throw new Error('neg');
  if (n < 2n) return n;
  let x = n, y = (x + 1n) / 2n;
  while (y < x) { x = y; y = (x + n / x) / 2n; }
  return x;
}
const lowerExact = (n) => { const N = BigInt(n); return Number((N + isqrt(5n * N * N)) / 2n); };
const upperExact = (n) => lowerExact(n) + n;

// sanity: confirm the integer formula matches the (n+sqrt5 n)/2 definition for
// a range, and that the "<1/2 never bridges" argument holds (no off-by-ones).
{
  let good = true;
  for (let n = 0; n <= 5000; n++) {
    const N = BigInt(n);
    const s = isqrt(5n * N * N);            // floor(n*sqrt5)
    ok2: { if (!(s * s <= 5n * N * N && (s + 1n) * (s + 1n) > 5n * N * N)) { good = false; break ok2; } }
    // floor(n*phi) must satisfy  L <= n*phi < L+1  i.e. 2L <= n+n*sqrt5 < 2L+2 ... check via squares
    const L = lowerExact(n);
    // n*phi in [L, L+1): equivalent to  (2L - n)^2 <= 5 n^2  and (2(L+1)-n)^2 > 5 n^2  (with sign care)
    const a = BigInt(2 * L - n), b = BigInt(2 * (L + 1) - n);
    if (!((a < 0n || a * a <= 5n * N * N) && b * b > 5n * N * N)) { good = false; }
  }
  ok(good, 'integer floor(n*phi)/floor(n*phi^2) verified exact against sqrt bounds for n=0..5000 (no float error)');
}

// ---- 1. brute-force retrograde game analysis on a board, M x M ------------
const M = 240; // classify every position with coords 0..M
// pos(a,b): true = COLD (P-position, player to move loses); false = HOT (N).
const cold = Array.from({ length: M + 1 }, () => new Uint8Array(M + 1));
// We compute by increasing total order so every reachable position is settled.
// A position is COLD iff EVERY move leads to a HOT position (and (0,0) is COLD).
// A position is HOT iff SOME move leads to a COLD position.
// Order by (a+b) then a: every legal move strictly decreases a+b, so by the time
// we evaluate (a,b) all its move-targets are already classified.
const order = [];
for (let s = 0; s <= 2 * M; s++) for (let a = Math.max(0, s - M); a <= Math.min(M, s); a++) { const b = s - a; if (b >= 0 && b <= M) order.push([a, b]); }
for (const [a, b] of order) {
  if (a === 0 && b === 0) { cold[0][0] = 1; continue; }
  let someColdReachable = false;
  // remove from a
  for (let k = 1; k <= a && !someColdReachable; k++) if (cold[a - k][b]) someColdReachable = true;
  // remove from b
  for (let k = 1; k <= b && !someColdReachable; k++) if (cold[a][b - k]) someColdReachable = true;
  // remove k from both
  for (let k = 1; k <= Math.min(a, b) && !someColdReachable; k++) if (cold[a - k][b - k]) someColdReachable = true;
  cold[a][b] = someColdReachable ? 0 : 1; // cold iff no cold reachable
}

// gather brute-force cold positions with a<=b (the canonical orientation)
const bruteCold = [];
for (let a = 0; a <= M; a++) for (let b = a; b <= M; b++) if (cold[a][b]) bruteCold.push([a, b]);
bruteCold.sort((p, q) => p[0] - q[0] || p[1] - q[1]);

// ---- 2./3. formula + mex construction --------------------------------------
const formulaCold = [];
for (let n = 0; upperExact(n) <= M; n++) formulaCold.push([lowerExact(n), upperExact(n)]);

// mex construction: a_n = smallest nonneg integer not yet used as any a_i or b_i.
const mexCold = [];
const used = new Set();
for (let n = 0; ; n++) {
  let a = 0; while (used.has(a)) a++;
  const b = a + n;
  if (b > M) break;
  mexCold.push([a, b]); used.add(a); used.add(b);
}

const eqSeq = (X, Y) => X.length === Y.length && X.every(([a, b], i) => a === Y[i][0] && b === Y[i][1]);
// align lengths to the shortest fully-contained prefix (all have b<=M)
const minLen = Math.min(bruteCold.length, formulaCold.length, mexCold.length);
const trim = (X) => X.slice(0, minLen);
ok(eqSeq(trim(bruteCold), trim(formulaCold)), `brute-force cold positions == (floor(n*phi),floor(n*phi^2)) for all ${minLen} positions with both coords <= ${M}`);
ok(eqSeq(trim(formulaCold), trim(mexCold)), `the golden-ratio formula == the mex construction (a_n=mex, b_n=a_n+n) for all ${minLen} positions`);
ok(formulaCold.every(([a, b], n) => b - a === n), 'b_n - a_n == n exactly for every cold position (phi^2 = phi + 1)');

// ---- 4. Beatty partition ---------------------------------------------------
const LIMIT = 100000;
const A = new Set(), B = new Set();
for (let n = 1; ; n++) { const a = lowerExact(n); if (a > LIMIT) break; A.add(a); }
for (let n = 1; ; n++) { const b = upperExact(n); if (b > LIMIT) break; B.add(b); }
let partitionOk = true, both = 0, neither = 0;
for (let k = 1; k <= LIMIT; k++) { const inA = A.has(k), inB = B.has(k); if (inA && inB) both++; if (!inA && !inB) neither++; if (inA === inB) partitionOk = false; }
ok(partitionOk && both === 0 && neither === 0, `A=floor(n*phi) and B=floor(n*phi^2) partition 1..${LIMIT.toLocaleString('en-US')} exactly (0 in both, 0 in neither) — Beatty/Rayleigh`);

// ---- 5. the Beatty condition 1/phi + 1/phi^2 = 1 ---------------------------
ok(Math.abs(1 / PHI + 1 / (PHI * PHI) - 1) < 1e-12, '1/phi + 1/phi^2 = 1 (the exact condition that makes the two sequences complementary)');
// algebraically: 1/phi + 1/phi^2 = (phi+1)/phi^2 = phi^2/phi^2 = 1, since phi^2=phi+1.
ok(Math.abs(PHI * PHI - (PHI + 1)) < 1e-12, 'phi^2 = phi + 1 (the defining identity behind everything above)');

// ---- 6. optimal-play invariant ---------------------------------------------
// from every HOT position there is at least one move to a COLD position;
// from every COLD position every move lands on a HOT position.
let invariantOk = true, sampleMove = null;
for (let a = 0; a <= M && invariantOk; a++) for (let b = 0; b <= M && invariantOk; b++) {
  const targets = [];
  for (let k = 1; k <= a; k++) targets.push([a - k, b]);
  for (let k = 1; k <= b; k++) targets.push([a, b - k]);
  for (let k = 1; k <= Math.min(a, b); k++) targets.push([a - k, b - k]);
  const reachCold = targets.some(([x, y]) => cold[x][y]);
  if (cold[a][b]) { if (reachCold) invariantOk = false; }     // cold -> must reach NO cold
  else { if (!reachCold) invariantOk = false; if (!sampleMove) sampleMove = [a, b, targets.find(([x, y]) => cold[x][y])]; }
}
ok(invariantOk, 'optimal play verified: every hot position has a winning move to a cold one; every cold position has none');

// ---- 7. OEIS cross-check ----------------------------------------------------
// A000201 lower Wythoff a(n)=floor(n*phi), n>=1 (b-file head):
const A000201 = [1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 24, 25, 27, 29, 30, 32, 33, 35, 37, 38, 40];
// A001950 upper Wythoff a(n)=floor(n*phi^2), n>=1 (verbatim from oeis.org/A001950 b-file):
const A001950 = [2, 5, 7, 10, 13, 15, 18, 20, 23, 26, 28, 31, 34, 36, 39, 41, 44, 47, 49, 52, 54, 57, 60, 62, 65];
ok(A000201.every((v, i) => lowerExact(i + 1) === v), 'first 25 terms of floor(n*phi) match OEIS A000201 (lower Wythoff)');
ok(A001950.every((v, i) => upperExact(i + 1) === v), 'first 25 terms of floor(n*phi^2) match OEIS A001950 (upper Wythoff)');

// ---- 8. Sprague-Grundy values: G(a,b)=0 exactly on cold positions ----------
const G = Array.from({ length: M + 1 }, () => new Int32Array(M + 1).fill(-1));
for (const [a, b] of order) {
  const reach = new Set();
  for (let k = 1; k <= a; k++) reach.add(G[a - k][b]);
  for (let k = 1; k <= b; k++) reach.add(G[a][b - k]);
  for (let k = 1; k <= Math.min(a, b); k++) reach.add(G[a - k][b - k]);
  let m = 0; while (reach.has(m)) m++;
  G[a][b] = m;
}
let grundyOk = true;
for (let a = 0; a <= M && grundyOk; a++) for (let b = 0; b <= M; b++) if ((G[a][b] === 0) !== (cold[a][b] === 1)) { grundyOk = false; break; }
ok(grundyOk, 'Sprague-Grundy value G(a,b)=0 exactly on the cold positions (and nowhere else)');

// ---- bonus: how close to the golden lines? ---------------------------------
const last = formulaCold[formulaCold.length - 1];
const ratio = last[1] / last[0];
ok(Math.abs(ratio - PHI) < 0.01, `the cold ratio b_n/a_n -> phi (last sampled = ${ratio.toFixed(6)} vs phi = ${PHI.toFixed(6)})`);

console.log(`\n${fails === 0 ? 'ALL PASS' : 'FAIL'} — ${checks - fails}/${checks} checks`);
process.exit(fails ? 1 : 0);
