// research/penneys-game — de-risking "Always Bet Second" (Penney's game).
//
// Everything the page claims numerically is recomputed here first, in the same
// JavaScript the in-browser instruments run, so the live readouts reproduce these
// offline numbers. Three independent engines must agree:
//
//   1. Conway's leading-number formula            — closed form, O(L)
//   2. an exact absorbing-Markov linear solver    — first principles, rational
//   3. brute-force enumeration to a depth cutoff  — direct, model-free
//
// plus a Monte-Carlo sanity pass. Run: `node research/penneys-game/verify.mjs`.

// ---- exact rational arithmetic (BigInt) ----
const g = (a, b) => (b ? g(b, a % b) : a < 0n ? -a : a);
class Q {
  constructor(n, d = 1n) {
    if (d < 0n) { n = -n; d = -d; }
    const k = g(n < 0n ? -n : n, d) || 1n;
    this.n = n / k; this.d = d / k;
  }
  add(o) { return new Q(this.n * o.d + o.n * this.d, this.d * o.d); }
  sub(o) { return new Q(this.n * o.d - o.n * this.d, this.d * o.d); }
  mul(o) { return new Q(this.n * o.n, this.d * o.d); }
  div(o) { return new Q(this.n * o.d, this.d * o.n); }
  eq(o)  { return this.n === o.n && this.d === o.d; }
  get f() { return Number(this.n) / Number(this.d); }
  get s() { return `${this.n}/${this.d}`; }
}
const Z = new Q(0n), HALF = new Q(1n, 2n), ONE = new Q(1n);

// ---- ENGINE 1: Conway's leading numbers ----
// corr(X,Y): for k=1..L, if the last k chars of X equal the first k chars of Y,
// add 2^(k-1). Odds that B beats A are (AA-AB):(BB-BA).
function corr(X, Y) {
  const L = X.length; let t = 0n;
  for (let k = 1; k <= L; k++) if (X.slice(-k) === Y.slice(0, k)) t += 2n ** BigInt(k - 1);
  return t;
}
function conwayBwinsA(A, B) {
  const AA = corr(A, A), AB = corr(A, B), BA = corr(B, A), BB = corr(B, B);
  const num = AA - AB, den = BB - BA;
  return new Q(num, num + den);
}

// ---- ENGINE 2: exact absorbing-Markov linear solver ----
// State = relevant history (the suffix of length up to L-1 of the flips so far).
// p[h] = P(A appears before B | history h). Solve the linear system with Gaussian
// elimination over exact rationals; answer is p[''] (empty start).
function* bits(L) {
  for (let k = 0; k < L; k++)
    for (let m = 0; m < (1 << k); m++)
      yield Array.from({ length: k }, (_, i) => (m >> (k - 1 - i)) & 1 ? 'T' : 'H').join('');
}
function markovAwinsA(A, B) {
  const L = A.length;
  const states = [...bits(L)];                 // '', H, T, HH, ... length 0..L-1
  const idx = new Map(states.map((s, i) => [s, i]));
  const n = states.length;
  const M = Array.from({ length: n }, () => Array.from({ length: n + 1 }, () => Z));
  for (const h of states) {
    const i = idx.get(h);
    M[i][i] = M[i][i].add(ONE);
    for (const c of 'HT') {
      const s = h + c;
      if (s.endsWith(A)) M[i][n] = M[i][n].add(HALF);          // A wins -> contributes 1
      else if (s.endsWith(B)) { /* B wins -> contributes 0 */ }
      else {
        const suff = L - 1 > 0 ? s.slice(-(L - 1)) : '';
        const j = idx.get(suff);
        M[i][j] = M[i][j].sub(HALF);
      }
    }
  }
  // Gauss-Jordan
  for (let col = 0; col < n; col++) {
    let piv = col; while (M[piv][col].eq(Z)) piv++;
    [M[col], M[piv]] = [M[piv], M[col]];
    const pv = M[col][col];
    M[col] = M[col].map((x) => x.div(pv));
    for (let r = 0; r < n; r++) if (r !== col && !M[r][col].eq(Z)) {
      const f = M[r][col];
      M[r] = M[r].map((x, k) => x.sub(f.mul(M[col][k])));
    }
  }
  return M[idx.get('')][n];                    // P(A first) from empty
}

// ---- ENGINE 3: brute-force enumeration to a depth cutoff ----
// Sum probabilities of every finite flip-string that ends the game at B, up to
// maxLen flips; the residual (games still running) is reported so the bound is honest.
function bruteBwinsA(A, B, maxLen = 40) {
  const L = A.length;
  // frontier: map history -> probability mass still live
  let live = new Map([['', 1]]);
  let pB = 0, pA = 0;
  for (let step = 0; step < maxLen; step++) {
    const next = new Map();
    for (const [h, mass] of live) for (const c of 'HT') {
      const s = h + c, m = mass / 2;
      if (s.endsWith(A)) pA += m;
      else if (s.endsWith(B)) pB += m;
      else {
        const suff = L - 1 > 0 ? s.slice(-(L - 1)) : '';
        next.set(suff, (next.get(suff) || 0) + m);
      }
    }
    live = next;
  }
  const residual = [...live.values()].reduce((a, b) => a + b, 0);
  return { pB, pA, residual };
}

// ---- Monte Carlo sanity ----
function montecarlo(A, B, trials = 300000) {
  const L = A.length; let winsB = 0;
  for (let t = 0; t < trials; t++) {
    let s = '';
    for (;;) {
      s += Math.random() < 0.5 ? 'H' : 'T';
      if (s.endsWith(A)) break;
      if (s.endsWith(B)) { winsB++; break; }
      s = s.slice(-(L - 1));
    }
  }
  return winsB / trials;
}

// ===================== checks =====================
const seqs3 = [...'01234567'].map((_, i) => i.toString(2).padStart(3, '0').replace(/0/g, 'H').replace(/1/g, 'T'));
let checks = 0, fails = 0;
const ok = (cond, msg) => { checks++; if (!cond) { fails++; console.log('  ✗ ' + msg); } };

console.log('Penney\'s game — three engines must agree on all 56 ordered length-3 pairs:');
let maxBruteResidual = 0;
for (const A of seqs3) for (const B of seqs3) {
  if (A === B) continue;
  const c = conwayBwinsA(A, B);                       // engine 1
  const m = ONE.sub(markovAwinsA(A, B));              // engine 2 (B wins = 1 - A wins)
  const br = bruteBwinsA(A, B);                        // engine 3
  ok(c.eq(m), `Conway≠Markov for ${B} vs ${A}: ${c.s} vs ${m.s}`);
  // brute-force is truncated at 40 flips: the exact value must lie inside
  // [pB, pB+residual] (undecided mass can only add to B's count).
  ok(c.f >= br.pB - 1e-12 && c.f <= br.pB + br.residual + 1e-12, `brute bracket fails for ${B} vs ${A}`);
  maxBruteResidual = Math.max(maxBruteResidual, br.residual);
}
console.log(`  ${checks - fails}/${checks} pairwise checks pass; max brute-force residual after 40 flips = ${maxBruteResidual.toExponential(2)}`);

// optimal counter == Conway rule: B = flip(A[1]) + A[0] + A[1]
const flip = (c) => (c === 'H' ? 'T' : 'H');
console.log('\nOptimal second-player counter for each length-3 first choice:');
for (const A of seqs3) {
  let best = null, bestQ = Z;
  for (const B of seqs3) if (B !== A) { const q = conwayBwinsA(A, B); if (q.f > bestQ.f) { bestQ = q; best = B; } }
  const rule = flip(A[1]) + A[0] + A[1];
  ok(best === rule, `best counter to ${A} is ${best}, not Conway rule ${rule}`);
  // uniqueness
  const ties = seqs3.filter((B) => B !== A && conwayBwinsA(A, B).eq(bestQ));
  ok(ties.length === 1, `best counter to ${A} not unique: ${ties}`);
  console.log(`  ${A} → ${best}   P = ${bestQ.s} = ${bestQ.f.toFixed(3)}   (Conway rule ${rule} ✓)`);
}

// the nontransitive 4-cycle
console.log('\nNontransitive cycle (each beats the next):');
const cyc = ['HHT', 'HTT', 'TTH', 'THH'];
for (let i = 0; i < 4; i++) {
  const A = cyc[i], B = cyc[(i + 1) % 4];
  const p = conwayBwinsA(B, A);                       // P(A beats B)
  const mc = montecarlo(B, A, 200000);
  ok(Math.abs(p.f - mc) < 0.02, `MC off for ${A} beats ${B}`);
  console.log(`  ${A} beats ${B}: ${p.s} = ${p.f.toFixed(4)}   (MC ${mc.toFixed(4)})`);
}

// length-2: nontransitivity is NOT yet universal (HT, TH only tie at best)
console.log('\nLength-2 (the switch-on threshold): best counter, with odds');
const seqs2 = ['HH', 'HT', 'TH', 'TT'];
for (const A of seqs2) {
  let best = null, bestQ = Z;
  for (const B of seqs2) if (B !== A) { const q = conwayBwinsA(A, B); if (q.f > bestQ.f) { bestQ = q; best = B; } }
  console.log(`  ${A} → ${best}   P = ${bestQ.s} = ${bestQ.f.toFixed(3)}${bestQ.eq(HALF) ? '  (only a tie — not beatable)' : ''}`);
}
ok(conwayBwinsA('HT', 'HH').eq(HALF) && conwayBwinsA('TH', 'HT').eq(HALF),
   'length-2 HT/TH should be only tie-able');

// waiting times (the same overlap that governs the game)
console.log('\nMean waiting times E[T_X] (the self-overlap, read the other way):');
function waiting(X) { let t = 0n; for (let k = 1; k <= X.length; k++) if (X.slice(0, k) === X.slice(-k)) t += 2n ** BigInt(k); return Number(t); }
const wt = { HHH: 14, HHT: 8, HTH: 10, HTT: 8, THH: 8, THT: 10, TTH: 8, TTT: 14 };
for (const X of seqs3) { ok(waiting(X) === wt[X], `waiting ${X}`); console.log(`  ${X}: ${waiting(X)}`); }

// the marginal blindfold: identical single-window marginals, but ordered (cyclic) relations
console.log('\nMarginal blindfold — every triple fills a fixed 3-window with probability exactly 1/8:');
const eighth = new Q(1n, 8n);
for (const w of seqs3) ok(new Q(1n, 2n ** BigInt(w.length)).eq(eighth), `marginal of ${w} is not 1/8`);
console.log('  all 8 triples: P(window = pattern) = 1/8, identical.  ✓');
// the contrast that proves frequency can't see the order
ok(waiting('HHT') === waiting('THH'), 'HHT and THH should share a waiting time');
ok(conwayBwinsA('HHT', 'THH').eq(new Q(3n, 4n)), 'yet THH should beat HHT 3/4');
console.log(`  HHT and THH: identical waiting time (${waiting('HHT')}) — yet THH beats HHT 3/4. Marginals tie; relations don't.`);
// Monte-Carlo: overlapping-window rates over a long fair stream all approach 1/8
{
  const N = 2_000_000; const cnt = {}; seqs3.forEach(s => cnt[s] = 0); let l2 = '';
  for (let i = 0; i < N; i++) { const c = Math.random() < 0.5 ? 'H' : 'T'; if (l2.length === 2) cnt[l2 + c]++; l2 = (l2 + c).slice(-2); }
  const W = N - 2; const rates = seqs3.map(s => cnt[s] / W); const mx = Math.max(...rates), mn = Math.min(...rates);
  ok(rates.every(r => Math.abs(r - 0.125) < 0.005), `8 overlapping-window rates near 1/8 (spread ${(100 * (mx - mn)).toFixed(3)}%)`);
  console.log(`  ${W.toLocaleString('en-US')} windows: rates ${(100 * mn).toFixed(2)}%–${(100 * mx).toFixed(2)}%, all near 12.5% — the eight stay tied.`);
}

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