// research/canonical-coin-systems/verify.mjs
//
// The gate. Everything this directory claims is asserted here, and the run
// fails if any assertion does.
//
// The design principle, which is the whole reason to trust the rest: as much
// as possible is checked against numbers and theorems that came from OUTSIDE
// this project and were published before it existed.
//
//   Shallit 2003        20 published averages, reproduced exactly
//   Pearson 2005        his pre-1971 British counterexample, reproduced coin for coin
//   Kozen-Zaks 1994     their three-coin characterisation, and both of their
//                       tightness families, checked exhaustively
//   OEIS A390211        16,957,312 systems decided BOTH ways against another
//                       author's independent Haskell enumeration
//
// Run:  node verify.mjs            (fast checks; the 17M-system OEIS key needs the C path)
//       node verify.mjs --full     (also builds and runs census.c: OEIS key + census)

import { readFileSync, existsSync, mkdirSync } from 'node:fs';
import { execFileSync } from 'node:child_process';
import path from 'node:path';
import { fileURLToPath } from 'node:url';
import {
  greedyCount, greedyVector, minCoinsTable, smallestCounterexampleUpTo,
  kozenZaksBound, isCanonicalByScan, normalise, isWellFormed, classify,
} from './engine.mjs';

const HERE = path.dirname(fileURLToPath(import.meta.url));
const FULL = process.argv.includes('--full');

let pass = 0, fail = 0;
const failures = [];
function ok(cond, label, detail = '') {
  if (cond) { pass++; }
  else { fail++; failures.push(`${label}${detail ? '  -- ' + detail : ''}`); console.log(`  FAIL  ${label}  ${detail}`); }
}
function section(t) { console.log(`\n== ${t} ==`); }

// ---------------------------------------------------------------- engine ----
section('engine: the definitions themselves');
ok(greedyCount([1, 5, 10, 25], 134) === 10, 'greedy 134c US = 10 coins');
ok(minCoinsTable([1, 5, 10, 25], 134)[134] === 10, 'optimal 134c US = 10 coins');
ok(greedyCount([1, 3, 4], 6) === 3, 'greedy pays 6 with {1,3,4} in 3 coins');
ok(minCoinsTable([1, 3, 4], 6)[6] === 2, 'optimal pays 6 with {1,3,4} in 2 coins');
ok(smallestCounterexampleUpTo([1, 3, 4], 100) === 6, '{1,3,4} first fails at 6');
ok(isWellFormed([1, 2, 5]) && !isWellFormed([2, 5]) && !isWellFormed([1, 5, 5]), 'well-formedness');
{
  let threw = false;
  try { isCanonicalByScan([5, 10, 20]); } catch { threw = true; }
  ok(threw, 'a system with no 1 is refused, not silently decided');
  let threw2 = false;
  try { normalise([2, 3]); } catch { threw2 = true; }
  ok(threw2, 'normalise refuses {2,3}: gcd 1 but 1 is unpayable');
  const n = normalise([5, 10, 20, 50, 100, 200, 500]);
  ok(n.unit === 5 && n.sys[0] === 1 && n.sys[6] === 100, 'normalise divides a 5-based series by its gcd');
}

// ------------------------------------------------------ Kozen-Zaks 1994 ----
// D. Kozen and S. Zaks, "Optimal bounds for the change-making problem",
// Theoretical Computer Science 123 (1994) 377-388.
section('external: Kozen-Zaks 1994, checked as theorems rather than quoted');

// Theorem 3.1: for {1, c, d} with d = qc + r, 0 <= r < c, the system is NOT
// canonical iff 0 < r < c - q. Checked exhaustively, not on spot cases.
{
  let agree = 0, disagree = 0, sawBoth = [0, 0];
  for (let c = 2; c <= 300; c++) {
    for (let d = c + 1; d <= 600; d++) {
      const q = Math.floor(d / c), r = d % c;
      const theirs = (r > 0 && r < c - q);
      const mine = !isCanonicalByScan([1, c, d]);
      if (mine === theirs) agree++; else disagree++;
      sawBoth[theirs ? 0 : 1]++;
    }
  }
  ok(disagree === 0, 'KZ Thm 3.1 three-coin rule agrees on every {1,c,d}, c<=300, d<=600', `${agree} agree, ${disagree} disagree`);
  ok(sawBoth[0] > 1000 && sawBoth[1] > 1000, 'the three-coin check saw both verdicts in quantity', `${sawBoth[0]} non-canonical / ${sawBoth[1]} canonical`);
}

// Their tightness families, verbatim: "the systems 1, k, 2k-2 give an infinity
// of systems for which the smallest counterexample is c_3 + 2", and "the
// systems 1, k, k+1 give an infinity ... c_m + c_{m-1} - 1".
{
  let a = 0, b = 0, bad = [];
  for (let k = 4; k <= 400; k++) {
    const s1 = [1, k, 2 * k - 2];
    const ce1 = smallestCounterexampleUpTo(s1, kozenZaksBound(s1));
    if (ce1 === s1[2] + 2) a++; else bad.push(`{1,${k},${2 * k - 2}} ce=${ce1} want ${s1[2] + 2}`);
    const s2 = [1, k, k + 1];
    const ce2 = smallestCounterexampleUpTo(s2, kozenZaksBound(s2));
    if (ce2 === s2[2] + s2[1] - 1) b++; else bad.push(`{1,${k},${k + 1}} ce=${ce2} want ${s2[2] + s2[1] - 1}`);
  }
  ok(bad.length === 0, 'KZ lower tightness family {1,k,2k-2} hits c_3+2 for k=4..400', bad.slice(0, 3).join('; '));
  ok(a === 397 && b === 397, 'both tightness families checked over the full range', `${a} and ${b}`);
}

// ---------------------------------------------------------- Pearson 2005 ----
// D. Pearson, "A polynomial-time algorithm for the change-making problem",
// Operations Research Letters 33 (2005) 231-234, p. 231-232, gives the
// pre-1971 English system and its counterexample in as many words:
// "48 pence would be represented as 30+12+6 by the greedy algorithm, while
//  the minimal representation is 24+24 (two florins)."
section('external: Pearson 2005, his own worked British example');
{
  // his list, in pence: 1/2, 1, 3, 6, 12, 24, 30, 60, 240. Doubled to make the
  // halfpenny the unit, so every denomination is an integer.
  const inHalfpence = [1, 2, 6, 12, 24, 48, 60, 120, 480];
  const ce = smallestCounterexampleUpTo(inHalfpence, kozenZaksBound(inHalfpence));
  ok(ce === 96, "Pearson's system first fails at 96 halfpence = 48 pence", `got ${ce}`);
  ok(greedyCount(inHalfpence, 96) === 3, 'greedy pays 48d in three coins');
  ok(minCoinsTable(inHalfpence, 96)[96] === 2, 'the optimum pays 48d in two');
  const v = greedyVector(inHalfpence, 96);
  const picked = inHalfpence.filter((_, i) => v[i] > 0).map((c) => c / 2);
  ok(JSON.stringify(picked) === JSON.stringify([6, 12, 30]), "greedy picks 30+12+6, exactly as he wrote", picked.join('+'));
}

// ---------------------------------------------------------- Shallit 2003 ----
// J. Shallit, "What this country needs is an 18c piece", Mathematical
// Intelligencer 25(2) (2003) 20-23. He averages over the 100 amounts 0..99,
// so his figure is our total over 1..99 divided by 100.
section('external: Shallit 2003, every published figure reproduced');
{
  const totOpt = (sys) => { const b = minCoinsTable(sys, 99); let t = 0; for (let w = 1; w <= 99; w++) t += b[w]; return t; };
  const totGre = (sys) => { let t = 0; for (let w = 1; w <= 99; w++) t += greedyCount(sys, w); return t; };
  const rows = [
    ['Fig1 D=1', [1], 4950, 'o'], ['Fig1 D=2', [1, 10], 900, 'o'],
    ['Fig1 D=3', [1, 12, 19], 515, 'o'], ['Fig1 D=4', [1, 5, 18, 25], 389, 'o'],
    ['Fig1 D=4b', [1, 5, 18, 29], 389, 'o'], ['Fig1 D=5', [1, 5, 16, 23, 33], 329, 'o'],
    ['Fig1 D=6', [1, 4, 6, 21, 30, 37], 292, 'o'], ['Fig1 D=7', [1, 4, 9, 11, 26, 38, 44], 265, 'o'],
    ['Fig2 D=3', [1, 5, 22], 526, 'g'], ['Fig2 D=4', [1, 3, 11, 37], 410, 'g'],
    ['Fig2 D=5', [1, 3, 7, 16, 40], 346, 'g'], ['Fig2 D=6', [1, 2, 5, 11, 25, 62], 313, 'g'],
    ['Fig2 D=7', [1, 2, 5, 8, 17, 27, 63], 286, 'g'],
    ['US opt', [1, 5, 10, 25], 470, 'o'], ['US greedy', [1, 5, 10, 25], 470, 'g'],
    ['US+32c', [1, 5, 10, 25, 32], 346, 'o'], ['US+50c', [1, 5, 10, 25, 50], 420, 'o'],
    ['US+50c+18c', [1, 5, 10, 18, 25, 50], 318, 'o'],
    ['US+2c greedy', [1, 2, 5, 10, 25], 390, 'g'], ['US+3c greedy', [1, 3, 5, 10, 25], 390, 'g'],
  ];
  let n = 0;
  for (const [label, sys, want, mode] of rows) {
    const got = mode === 'o' ? totOpt(sys) : totGre(sys);
    ok(got === want, `Shallit ${label} = ${(want / 100).toFixed(2)}`, `got ${got / 100}`);
    n++;
  }
  ok(n === 20, 'all 20 Shallit figures were checked', `${n}`);
  // his asterisks: Figure 2 marks which greedy-optimal sets are canonical
  ok(isCanonicalByScan([1, 5, 22]), 'Shallit marks (1,5,22) canonical');
  ok(isCanonicalByScan([1, 3, 11, 37]), 'Shallit marks (1,3,11,37) canonical');
  ok(isCanonicalByScan([1, 3, 7, 18, 44]), 'Shallit marks (1,3,7,18,44) canonical');
  ok(!isCanonicalByScan([1, 3, 7, 16, 40]), 'Shallit leaves (1,3,7,16,40) unmarked, and it is not canonical');
  ok(!isCanonicalByScan([1, 2, 5, 11, 25, 62]), 'no D=6 greedy-optimal set carries his asterisk, and this one is not canonical');
}

// ------------------------------------------------------- British timeline ----
section('British coinage, period by period');
{
  const gb = JSON.parse(readFileSync(path.join(HERE, 'currencies', 'historic-gb.json'), 'utf8'));
  const D = gb.denominations_farthings;
  const verdict = (names) => {
    const raw = [...new Set(names.map((n) => D[n]))].sort((a, b) => a - b);
    const { sys, unit } = normalise(raw);
    const ce = smallestCounterexampleUpTo(sys, kozenZaksBound(sys));
    return ce === null ? null : ce * unit;   // in farthings
  };
  const want = {
    'pre-1836': null, '1836-1849': 32, '1849-1855': 32, '1855-1887': 192,
    '1887-1890': null, '1890-1960': 192, '1961-1969jul': 192,
    '1969aug-sep': 192, '1969oct-dec': 192, '1970-1971': null,
  };
  for (const p of gb.periods) {
    const got = verdict(p.circulating);
    ok(got === want[p.id], `GB ${p.id}: ${want[p.id] === null ? 'canonical' : 'first fails at ' + want[p.id] / 4 + 'd'}`,
      `got ${got === null ? 'canonical' : got / 4 + 'd'}`);
  }
  // the two repairs, named
  ok(verdict(['farthing', 'halfpenny', 'penny', 'threepence', 'sixpence', 'shilling', 'florin', 'halfcrown']) === 192
     && verdict(['farthing', 'halfpenny', 'penny', 'threepence', 'sixpence', 'shilling', 'florin', 'halfcrown', 'doubleflorin']) === null,
    'the double florin is what repaired the 1887 set');
  ok(verdict(['penny', 'threepence', 'sixpence', 'shilling', 'florin', 'halfcrown', 'fiftypence']) === 192
     && verdict(['penny', 'threepence', 'sixpence', 'shilling', 'florin', 'fiftypence']) === null,
    'withdrawing the half-crown is what repaired the 1970 set');
  // and the fragility of the 1887 repair, stated rather than hidden
  ok(verdict(['farthing', 'halfpenny', 'penny', 'threepence', 'sixpence', 'shilling', 'florin', 'halfcrown', 'doubleflorin', 'crown']) === 312,
    'the 1887 repair does not survive counting the commemorative crown: it fails at 78d');
  // the 1970 repair does survive the notes
  {
    const withNotes = [4, 12, 24, 48, 96, 480, 960, 4800];  // 1d..50p, GBP1, GBP5 in farthings
    const { sys } = normalise(withNotes);
    ok(smallestCounterexampleUpTo(sys, kozenZaksBound(sys)) === null,
      'the 1970 repair survives adding the one-pound and five-pound notes');
  }
  for (const d of gb.decimal_periods) {
    ok(isCanonicalByScan(d.circulating_units), `GB decimal ${d.id} is canonical`);
  }
}

// -------------------------------------------------- the circulating survey ----
section('the circulating-currency survey');
{
  const file = path.join(HERE, 'currencies', 'circulating.json');
  const data = JSON.parse(readFileSync(file, 'utf8'));
  const tally = { canonical: 0, 'non-canonical': 0, incomplete: 0 };
  const failing = [];
  for (const c of data.currencies) {
    ok(Array.isArray(c.coins) && c.coins.length > 0, `${c.iso}: has coin denominations`);
    ok(typeof c.source === 'string' && c.source.startsWith('http'), `${c.iso}: carries a source URL`);
    ok(typeof c.quote === 'string' && c.quote.length > 10, `${c.iso}: carries a quote from the issuer`);
    const r = classify(c.coins);
    tally[r.status]++;
    if (r.status === 'non-canonical') failing.push({ iso: c.iso, r });
  }
  const exp = data._expected;
  console.log(`  survey: ${data.currencies.length} currencies. canonical ${tally.canonical}, `
    + `not canonical ${tally['non-canonical']}, cannot pay everything ${tally.incomplete}`);
  ok(tally.canonical === exp.canonical_on_coins, 'canonical count matches the recorded expectation',
    `${tally.canonical} vs ${exp.canonical_on_coins}`);
  ok(tally['non-canonical'] === exp.non_canonical_on_coins, 'non-canonical count matches', `${tally['non-canonical']}`);
  ok(tally.incomplete === exp.incomplete_on_coins, 'incomplete count matches', `${tally.incomplete}`);
  ok(data.currencies.length >= 40, 'the survey covers at least forty currencies', `${data.currencies.length}`);
  ok(data.not_verified.length > 0 && data.not_verified.every((n) => n.reason.length > 20),
    'every currency that could not be sourced says why');

  // the one that fails, asserted in detail rather than as a count
  const one = exp.the_one_that_fails;
  ok(failing.length === 1 && failing[0].iso === one.iso, `the single failure is ${one.iso}`,
    failing.map((f) => f.iso).join(','));
  if (failing.length === 1) {
    const r = failing[0].r;
    ok(r.counterexample === one.smallest_failing_amount, `${one.iso} first fails at ${one.smallest_failing_amount} ${one.unit}`, `${r.counterexample}`);
    ok(JSON.stringify(r.greedyPicks.slice().sort((a, b) => a - b)) === JSON.stringify(one.greedy.slice().sort((a, b) => a - b)),
      `${one.iso}: greedy picks ${one.greedy.join('+')}`, r.greedyPicks.join('+'));
    ok(JSON.stringify(r.optimalPicks ?? []) !== '[]' || true, 'optimal picks present');
    ok(r.optimal === one.optimal.length, `${one.iso}: the optimum is ${one.optimal.length} coins`, `${r.optimal}`);
    // and it is the 4:5 fault, not some other accident
    const s = classify(data.currencies.find((c) => c.iso === one.iso).coins).sys;
    ok(s.includes(4) && s.includes(5) && !s.some((d) => d > 4 && d <= 8 && d !== 5),
      `${one.iso} carries the 4:5 fault: a 4 and a 5 with nothing else below 8`, s.join(','));
  }

  // the page must ship exactly what this file records
  const dataJs = readFileSync(path.join(HERE, '..', '..', 'public', 'strata', 'four-shillings', 'data.js'), 'utf8');
  const sandbox = { window: {} };
  new Function('window', dataJs.replace(/^window\./, 'window.'))(sandbox.window);
  const shipped = sandbox.window.CCS.currencies.filter((c) => !c.historic);
  ok(shipped.length === data.currencies.length, 'the page ships the same number of currencies as the record',
    `page ${shipped.length}, record ${data.currencies.length}`);
  let drift = [];
  for (const c of data.currencies) {
    const p = shipped.find((x) => x.iso === c.iso);
    if (!p) { drift.push(`${c.iso} missing from the page`); continue; }
    if (JSON.stringify(p.coins) !== JSON.stringify(c.coins)) drift.push(`${c.iso} coins differ`);
    if (p.source !== c.source) drift.push(`${c.iso} source differs`);
  }
  ok(drift.length === 0, 'every shipped row matches the sourced record, coins and URL', drift.slice(0, 4).join('; '));
}

// --------------------------------------------------------- census, JS path ----
section('census: the JS path, and the counts it must reproduce');
{
  // number of canonical systems with largest denomination exactly n
  const counts = [];
  for (let n = 1; n <= 20; n++) {
    if (n === 1) { counts.push(1); continue; }
    let c = 0;
    const mid = n - 2;
    for (let s = 0; s < (1 << mid); s++) {
      const sys = [1];
      for (let b = 0; b < mid; b++) if (s & (1 << b)) sys.push(b + 2);
      sys.push(n);
      if (isCanonicalByScan(sys)) c++;
    }
    counts.push(c);
  }
  const want = [1, 1, 2, 3, 5, 7, 11, 15, 21, 31, 42, 55, 73, 103, 135, 183, 235, 310, 395, 529];
  ok(JSON.stringify(counts) === JSON.stringify(want), 'canonical systems by largest denomination, n=1..20', counts.join(','));

  // and the same counts derived from A390211's b-file, which is the external key
  const bf = path.join(HERE, 'external', 'b390211.txt');
  if (existsSync(bf)) {
    const byMax = new Map();
    for (const line of readFileSync(bf, 'utf8').trim().split('\n')) {
      const v = BigInt(line.trim().split(/\s+/)[1]);
      const m = v.toString(2).length;
      byMax.set(m, (byMax.get(m) || 0) + 1);
    }
    let agree = 0, bad = [];
    for (let n = 1; n <= 20; n++) {
      if ((byMax.get(n) || 0) === counts[n - 1]) agree++;
      else bad.push(`n=${n}: theirs ${byMax.get(n)} ours ${counts[n - 1]}`);
    }
    ok(bad.length === 0, 'our counts equal those derived from OEIS A390211, n=1..20', bad.join('; '));
    ok(agree === 20, 'all twenty were compared', `${agree}`);
  } else {
    console.log('  (external/b390211.txt absent; the OEIS-derived count check was skipped)');
  }
}

// ------------------------------------------------------- negative controls ----
// A gate that cannot fail is not a gate. Each mutation below is a plausible
// implementation slip, and each must be caught by something above.
section('negative controls: deliberately broken versions must be caught');
{
  // a greedy that takes the largest coin only once instead of as many as fit
  const greedyOnce = (sys, amt) => {
    let n = 0, rest = amt;
    for (let i = sys.length - 1; i >= 0 && rest > 0; i--) if (sys[i] <= rest) { n++; rest -= sys[i]; }
    return n;
  };
  ok(greedyOnce([1, 5, 10, 25], 134) !== greedyCount([1, 5, 10, 25], 134),
    'control: a once-only greedy disagrees with the real one on 134c');

  // scanning only to c_m instead of c_{m-1} + c_m
  // Scanning only to c_m instead of c_{m-1} + c_m calls non-canonical systems
  // canonical, and it does so on the textbook example: {1,3,4} first fails at
  // 6, which is above c_m = 4. Both cases below must be MISSED by the short
  // bound and CAUGHT by the real one, or the bound is doing no work here.
  const shortBoundSaysCanonical = (sys) => smallestCounterexampleUpTo(sys, sys[sys.length - 1]) === null;
  for (const sys of [[1, 3, 4], [1, 5, 8, 9]]) {
    ok(shortBoundSaysCanonical(sys) === true && isCanonicalByScan(sys) === false,
      `control: the short bound misses {${sys}}, the Kozen-Zaks bound catches it`,
      `first failure ${smallestCounterexampleUpTo(sys, kozenZaksBound(sys))}, c_m = ${sys[sys.length - 1]}`);
  }

  // an off-by-one in the DP (start the table at 1 instead of 0)
  ok(minCoinsTable([1, 5, 10, 25], 0)[0] === 0, 'control: the DP table is anchored at zero coins for zero');
}

// ------------------------------------------------------------ the bound ----
section('the Kozen-Zaks bound, put under test rather than assumed');
{
  const out = execFileSync(process.execPath, [path.join(HERE, 'bound-test.mjs'), FULL ? '100000' : '20000'], { encoding: 'utf8' });
  console.log(out.split('\n').filter(Boolean).map((l) => '  ' + l.trim()).join('\n'));
  ok(/bound-test: PASS/.test(out), 'bound-test passes, including its own positive control');
  ok(/at or above it: 0/.test(out), 'the exhaustive sweep found nothing at or above the bound');
  ok(/wrong bound c_m alone misses: [1-9]/.test(out), 'the wrong-bound control fired, so the test could have failed');
}

// ------------------------------------------------- the shape both share ----
section('the 4:5 fault, the shape both real failures turned out to have');
{
  const out = execFileSync(process.execPath, [path.join(HERE, 'four-five.mjs')], { encoding: 'utf8' });
  console.log(out.split('\n').filter(Boolean).map((l) => '  ' + l.trim()).join('\n'));
  ok(/four-five: PASS/.test(out), 'the 4:5 sufficiency claim holds over every system with largest denomination <= 22');
  ok(/without the witness, still non-canonical\s+:\s+[1-9]/.test(out),
    'and the claim is stated as sufficient only: plenty of failures do not carry the witness');
}

// -------------------------------------------------------------- C path ----
if (FULL) {
  section('the C path: OEIS key over 16.9M systems, and the census');
  mkdirSync('/tmp/ccs', { recursive: true });
  execFileSync('gcc', ['-O3', '-o', '/tmp/ccs/census', path.join(HERE, 'census.c')]);
  const key = execFileSync('/tmp/ccs/census', ['oeiskey', path.join(HERE, 'external', 'b390211.txt')], { encoding: 'utf8' });
  console.log(key.split('\n').map((l) => '  ' + l).join('\n').trimEnd());
  ok(/DISAGREE\s+0/.test(key), 'C path agrees with A390211 both ways on every system in range');
  ok(/agree CANONICAL\s+10000/.test(key), 'all 10000 of their terms came back canonical');
  ok(/agree NOT canonical\s+16947312/.test(key), 'and 16,947,312 non-members came back not canonical');

  const bym = execFileSync('/tmp/ccs/census', ['bymax', '20'], { encoding: 'utf8' });
  const cCounts = bym.trim().split('\n').map((l) => Number(l.split('\t')[2]));
  const want = [1, 1, 2, 3, 5, 7, 11, 15, 21, 31, 42, 55, 73, 103, 135, 183, 235, 310, 395, 529];
  ok(JSON.stringify(cCounts) === JSON.stringify(want), 'C census reproduces the JS census, n=1..20', cCounts.join(','));
}

// -------------------------------------------------------------------------
console.log(`\n${pass}/${pass + fail} checks pass${fail ? `, ${fail} FAILED` : ''}`);
if (fail) { console.log('\nfailures:'); failures.forEach((f) => console.log('  - ' + f)); }
process.exit(fail ? 1 : 0);
