// Verifier for the "siteswap" stratum. Every on-page claim is asserted here.
// Run: node research/siteswap/verify.mjs
import { isValid, balls, enumValid, countAtMostB, countExactB } from './engine.mjs';
import { execSync } from 'node:child_process';
import { existsSync, readFileSync } from 'node:fs';
import { dirname, join } from 'node:path';
import { fileURLToPath } from 'node:url';
import { homedir } from 'node:os';
const HERE = dirname(fileURLToPath(import.meta.url));

let pass = 0, fail = 0;
const ok = (name, cond) => { if (cond) { pass++; } else { fail++; console.log('  FAIL:', name); } };

// ---- 1. Validity test agrees with an INDEPENDENT simulation -------------------
// Independent definition: extend the period-n sequence over many beats; the throw
// at beat t lands at beat t+a[t mod n]. The pattern is valid iff, in steady state,
// every beat is the landing of exactly one throw (no two balls collide, none drop).
function validBySimulation(seq) {
  const n = seq.length, K = 20;            // simulate K periods
  const M = n * K;
  const landedBy = new Array(M + 1).fill(0);
  for (let t = 0; t < M; t++) {
    const land = t + seq[t % n];
    if (land <= M) landedBy[land]++;
  }
  // inspect the steady interior, past the warm-up (sources >= 0) and before cool-down
  const mx = Math.max(...seq);
  for (let b = mx + n; b < M - mx - n; b++) {
    if (landedBy[b] !== 1) return false;   // a collision (>1) or a drop (0)
  }
  return true;
}
{
  let mism = 0, tot = 0;
  for (let n = 1; n <= 5; n++)
    for (const s of enumAll(n, 5)) {       // ALL sequences, valid or not
      tot++;
      if (isValid(s) !== validBySimulation(s)) mism++;
    }
  ok(`validity (mod-n permutation) == validity (12-period simulation), 0 mismatches over ${tot} sequences`, mism === 0);
}
function enumAll(n, maxThrow) {
  const out = []; const seq = new Array(n).fill(0);
  (function rec(i){ if(i===n){out.push(seq.slice());return;} for(let v=0;v<=maxThrow;v++){seq[i]=v;rec(i+1);} })(0);
  return out;
}

// ---- 2. The AVERAGE THEOREM ----------------------------------------------------
// Every valid pattern's ball count = (sum of throws)/period, and it is an integer.
{
  let nonint = 0, tot = 0;
  for (let n = 1; n <= 6; n++)
    for (const s of enumValid(n, 7)) { tot++; if (!Number.isInteger(balls(s))) nonint++; }
  ok(`average theorem: all ${tot} valid patterns (n<=6) have integer ball count = mean throw`, nonint === 0);
  // A famous worked example: 5 3 1 -> 3 balls.
  ok('worked example 531 is valid and is a 3-ball pattern', isValid([5,3,1]) && balls([5,3,1]) === 3);
  ok('worked example 441 is valid, 3 balls', isValid([4,4,1]) && balls([4,4,1]) === 3);
  ok('worked example 97531 is valid, 5 balls', isValid([9,7,5,3,1]) && balls([9,7,5,3,1]) === 5);
  ok('the cascade 3 is valid, 3 balls', isValid([3]) && balls([3]) === 3);
  // Integer mean is NECESSARY but not SUFFICIENT: 522 has mean 3 yet is valid,
  // while 321 has mean 2 (integer) yet collides — all three throws land on the same beat.
  ok('522 is valid (3 balls); 321 is INVALID despite integer mean — the permutation test bites',
     isValid([5,2,2]) && balls([5,2,2]) === 3 && !isValid([3,2,1]) && balls([3,2,1]) === 2);
}

// ---- 3. The BEGW COUNTING THEOREM ---------------------------------------------
// Buhler, Eisenbud, Graham, Wright, "Juggling Drops and Descents",
// Amer. Math. Monthly 101 (1994) 507-519:
//   #{valid period-n patterns, at most b balls} = (b+1)^n
//   #{valid period-n patterns, exactly  b balls} = (b+1)^n - b^n
{
  let bad = 0, cells = 0;
  for (let n = 1; n <= 4; n++)
    for (let b = 0; b <= 3; b++) {
      cells++;
      const am = countAtMostB(n, b), ex = countExactB(n, b);
      if (am !== (b + 1) ** n) bad++;
      if (ex !== (b + 1) ** n - b ** n) bad++;
    }
  ok(`BEGW: atMost=(b+1)^n and exact=(b+1)^n-b^n hold across ${cells} (n,b) cells`, bad === 0);
  // The exactly-2-ball column is 3^n - 2^n (OEIS A001047): 1,5,19,65,211,665,2059.
  const col2 = [1,2,3,4,5,6,7].map(n => countExactB(n, 2));
  ok('exactly-2-ball count = 3^n-2^n (A001047): 1,5,19,65,211,665,2059',
     JSON.stringify(col2) === JSON.stringify([1,5,19,65,211,665,2059]));
  // at-most-b for n=1 is just b+1 (the one-beat patterns 0,1,...,b)
  ok('n=1: at-most-b patterns are exactly {0,1,...,b}', [0,1,2,3,4,5].every(b => countAtMostB(1,b) === b+1));
}

// ---- 4. Closure / sanity -------------------------------------------------------
// A rotation of a valid pattern is valid (juggling is periodic — where you "start" is free).
{
  let bad = 0, tot = 0;
  for (let n = 1; n <= 5; n++)
    for (const s of enumValid(n, 6)) {
      for (let k = 0; k < n; k++) {
        const r = s.slice(k).concat(s.slice(0, k));
        tot++; if (!isValid(r)) bad++;
      }
    }
  ok(`every cyclic rotation of a valid pattern is valid (${tot} rotations checked)`, bad === 0);
}

// ---- 5. THE KERNEL PROOF (Lean) — the average theorem for ALL n, no census ------
// §2 enumerates valid patterns only to n<=6; it can never settle the "for every n"
// statement. lean/Siteswap.lean proves it: for EVERY period n and every valid
// pattern, n | (sum of throws), so the ball count (Σ throws)/n is always a whole
// number, with no search. Here we (a) confirm the Lean predicate `Valid` (landings
// are a PERMUTATION of {0,..,n-1}) is exactly the engine's `isValid` (the n landings
// are DISTINCT) over the whole enumerated space — so the theorem is about the very
// pattern the page operates — and (b) when `lean` is on PATH, typecheck the file
// live and assert its [propext, Quot.sound] axiom footprint.
console.log('\n=== V.  The kernel proof (Lean): n | sum-of-throws for EVERY n, no census ===\n');
{
  // (a) model fidelity: engine isValid (distinct landings) <=> permutation of {0..n-1}.
  const landings = (seq) => { const n = seq.length; return seq.map((v, i) => (i + v) % n); };
  const isPermOfRange = (seq) => {
    const n = seq.length;
    const L = landings(seq).slice().sort((a, b) => a - b);
    for (let i = 0; i < n; i++) if (L[i] !== i) return false;
    return true;
  };
  let mism = 0, tot = 0;
  for (let n = 1; n <= 6; n++)
    for (const s of enumAll(n, 6)) { tot++; if (isValid(s) !== isPermOfRange(s)) mism++; }
  ok(`Lean predicate fidelity: engine isValid == "landings are a permutation of {0..n-1}", 0 mismatches over ${tot} patterns`, mism === 0);

  // Cross-check the two concrete numbers the Lean file settles by `decide`, computed here.
  ok('Lean example 531 -> 3 balls matches engine', isValid([5, 3, 1]) && balls([5, 3, 1]) === 3);
  ok('Lean example 97531 -> 5 balls matches engine', isValid([9, 7, 5, 3, 1]) && balls([9, 7, 5, 3, 1]) === 5);
  ok('Lean example: 321 collides despite integer mean (matches engine)', !isValid([3, 2, 1]) && balls([3, 2, 1]) === 2);

  // (b) the file: theorems present, no sorry / native_decide, typecheck + footprint.
  const leanFile = join(HERE, 'lean', 'Siteswap.lean');
  ok(existsSync(leanFile), 'Lean proof file present (lean/Siteswap.lean)');
  if (existsSync(leanFile)) {
    const src = readFileSync(leanFile, 'utf8');
    for (const t of ['average_theorem', 'ballCount_exact', 'valid_landings_nodup', 'perm_sum'])
      ok(new RegExp(`theorem ${t}\\b`).test(src), `Lean states theorem ${t}`);
    ok(!/\bsorry\b(?![^\n]*`)/.test(src.replace(/no `sorry`[^\n]*/g, '')) && !/native_decide/.test(src.replace(/no `native_decide`[^\n]*/g, '')),
      'Lean source has no sorry / native_decide');
    const candidates = ['lean', join(homedir(), '.elan', 'bin', 'lean'), join(homedir(), '.nix-profile', 'bin', 'lean')];
    let leanBin = null;
    for (const c of candidates) {
      try { execSync(`${c} --version`, { stdio: 'ignore' }); leanBin = c; break; } catch { /* keep trying */ }
    }
    if (leanBin) {
      let out = '', typechecked = true;
      try {
        out = execSync(`${leanBin} ${JSON.stringify(leanFile)}`, { encoding: 'utf8', stdio: ['ignore', 'pipe', 'pipe'] });
      } catch (e) {
        out = (e.stdout || '') + (e.stderr || '');
        typechecked = false;
      }
      ok(typechecked, 'Lean typechecks with no errors' + (typechecked ? '' : ' — ' + out.split('\n').slice(0, 3).join(' | ')));
      const axiomLines = out.split('\n').filter((l) => /depends on axioms|does not depend on any axioms/.test(l));
      ok(axiomLines.length >= 6, `Lean emitted axiom footprints (${axiomLines.length} lines)`);
      const badAxiom = axiomLines.find((l) => /sorryAx|Classical\.choice/.test(l));
      ok(!badAxiom, 'every kernel theorem is [propext, Quot.sound] or tighter (no sorryAx, no Classical.choice)' + (badAxiom ? ' — ' + badAxiom : ''));
      for (const l of axiomLines) console.log('   ', l.trim());
    } else {
      console.log('  ..  lean not on PATH — static check only (run research/siteswap/lean/install-lean-nix.sh to typecheck)');
    }
  }
}

console.log(`\nsiteswap verifier: ${pass}/${pass + fail} checks passed.`);
if (fail) process.exit(1);
