#!/usr/bin/env node
/**
 * verify-shake-the-cloth.mjs
 *
 * Independent offline recomputation of every load-bearing number shown by
 * public/strata/shake-the-cloth/index.html.
 *
 * Nothing here imports page code. The decision procedure, the census, the satin
 * arithmetic and the interlacement statistics are all rebuilt from the
 * definitions. Node 22 built-ins only.
 *
 * Model (Grunbaum-Shephard): a doubly periodic fabric of period n is an n x n
 * binary matrix M with M[i][j] = 1 meaning "warp j passes OVER weft i".
 * A set of warps W and wefts F can be LIFTED OFF the rest iff
 *     for all j in W and all i not in F:  M[i][j] = 1
 *     for all i in F and all j not in W:  M[i][j] = 0
 * The fabric FALLS APART iff some (W,F) other than (empty, empty) and
 * (all, all) is liftable; otherwise it HANGS TOGETHER.
 *
 * Usage:  node verify-shake-the-cloth.mjs           (full run, ~20 s)
 *         node verify-shake-the-cloth.mjs --quick   (skips the 5x5 census)
 */

'use strict';

const QUICK = process.argv.includes('--quick');
let PASS = 0;
const FAILS = [];

function ok(label, got, want) {
  const g = JSON.stringify(got), w = JSON.stringify(want);
  if (g === w) { PASS++; console.log(`  ok   ${label}  =  ${g}`); }
  else { FAILS.push(`${label}: got ${g}, want ${w}`); console.log(`  FAIL ${label}: got ${g}, want ${w}`); }
}
function section(t) { console.log(`\n== ${t}`); }

/* ------------------------------------------------------------------ */
/* 1. The decision procedure, written twice, independently.            */
/* ------------------------------------------------------------------ */

/* (a) The naive definition: try every (W,F) pair. Exponential; used only as
   ground truth on tiny cases to validate (b). */
function fallsApartNaive(M) {
  const n = M.length, m = M[0].length;
  for (let wm = 0; wm < (1 << m); wm++) {
    for (let fm = 0; fm < (1 << n); fm++) {
      if (wm === 0 && fm === 0) continue;
      if (wm === (1 << m) - 1 && fm === (1 << n) - 1) continue;
      let good = true;
      for (let j = 0; j < m && good; j++) {
        if (!((wm >> j) & 1)) continue;
        for (let i = 0; i < n; i++) if (!((fm >> i) & 1) && M[i][j] !== 1) { good = false; break; }
      }
      for (let i = 0; i < n && good; i++) {
        if (!((fm >> i) & 1)) continue;
        for (let j = 0; j < m; j++) if (!((wm >> j) & 1) && M[i][j] !== 0) { good = false; break; }
      }
      if (good) return { falls: true, W: wm, F: fm };
    }
  }
  return { falls: false };
}

/* (b) The closure procedure the page implements.
   Seed one strand; apply the two forced implications
       warp j lifted and M[i][j] = 0  ->  weft i must lift too
       weft i lifted and M[i][j] = 1  ->  warp j must lift too
   to a fixed point. Because both rules quantify over ALL rows (resp. all
   columns) and M is n-periodic, each closure is a union of whole residue
   classes, so it is automatically periodic; and any liftable set containing
   strand x contains cl(x). Hence: the fabric hangs together iff cl(x) is
   everything for each of the 2n class seeds. */
function decide(M) {
  const n = M.length, m = M[0].length;
  const wits = [];
  for (let seed = 0; seed < n + m; seed++) {
    const W = new Array(m).fill(false), F = new Array(n).fill(false);
    if (seed < m) W[seed] = true; else F[seed - m] = true;
    let changed = true;
    while (changed) {
      changed = false;
      for (let j = 0; j < m; j++) if (W[j]) for (let i = 0; i < n; i++)
        if (M[i][j] === 0 && !F[i]) { F[i] = true; changed = true; }
      for (let i = 0; i < n; i++) if (F[i]) for (let j = 0; j < m; j++)
        if (M[i][j] === 1 && !W[j]) { W[j] = true; changed = true; }
    }
    if (!(W.every(Boolean) && F.every(Boolean))) {
      wits.push({
        W: W.map((v, k) => v ? k : -1).filter(k => k >= 0),
        F: F.map((v, k) => v ? k : -1).filter(k => k >= 0)
      });
    }
  }
  return { hangs: wits.length === 0, witnesses: wits };
}
const hangs = M => decide(M).hangs;

/* (c) The bitmask form used for the census (must agree with (b)). */
function hangsFast(rows, n) {
  const FULL = (1 << n) - 1;
  const zc = new Int32Array(n);
  for (let j = 0; j < n; j++) { let z = 0; for (let i = 0; i < n; i++) if (!((rows[i] >>> j) & 1)) z |= (1 << i); zc[j] = z; }
  for (let seed = 0; seed < 2 * n; seed++) {
    let W = 0, F = 0;
    if (seed < n) W = 1 << seed; else F = 1 << (seed - n);
    for (;;) {
      let nF = F, w = W;
      while (w) { const j = 31 - Math.clz32(w & -w); nF |= zc[j]; w &= w - 1; }
      let nW = W, f = nF;
      while (f) { const i = 31 - Math.clz32(f & -f); nW |= rows[i]; f &= f - 1; }
      if (nW === W && nF === F) break;
      W = nW; F = nF;
      if (W === FULL && F === FULL) break;
    }
    if (!(W === FULL && F === FULL)) return false;
  }
  return true;
}

const rowsOf = M => M.map(r => r.reduce((a, b, j) => a | (b << j), 0));
const matOf = (rows, n) => rows.map(r => Array.from({ length: n }, (_, j) => (r >>> j) & 1));

/* (d) Clapham's bipartite tournament: one node per strand, an arc from the
   thread on top to the thread underneath at each crossing. A liftable set is a
   nonempty proper subset with no incoming arcs, which exists iff the digraph is
   not strongly connected. Shares no logic with (a), (b) or (c). */
function hangsSCC(M) {
  const n = M.length, m = M[0].length, N = n + m;
  const out = new Array(N).fill(0), inn = new Array(N).fill(0);
  for (let i = 0; i < n; i++) for (let j = 0; j < m; j++) {
    if (M[i][j] === 1) { out[j] |= (1 << (m + i)); inn[m + i] |= (1 << j); }
    else { out[m + i] |= (1 << j); inn[j] |= (1 << (m + i)); }
  }
  const reach = adj => {
    let seen = 1, frontier = 1;
    while (frontier) {
      let nxt = 0, f = frontier;
      while (f) { const k = 31 - Math.clz32(f & -f); nxt |= adj[k]; f &= f - 1; }
      nxt &= ~seen; seen |= nxt; frontier = nxt;
    }
    return seen;
  };
  const FULL = (1 << N) - 1;
  return reach(out) === FULL && reach(inn) === FULL;
}

section('1. the four implementations of the criterion agree');
{
  let mismatchNaive = 0, mismatchFast = 0;
  for (let code = 0; code < 512; code++) {          // every 3x3 draft
    const rows = [code & 7, (code >> 3) & 7, (code >> 6) & 7];
    const M = matOf(rows, 3);
    if (decide(M).hangs === fallsApartNaive(M).falls) mismatchNaive++;
    if (decide(M).hangs !== hangsFast(rows, 3)) mismatchFast++;
  }
  ok('closure vs brute-force-over-all-(W,F), 3x3 disagreements', mismatchNaive, 0);
  ok('closure vs bitmask, 3x3 disagreements', mismatchFast, 0);
  let mm = 0;
  for (let code = 0; code < 65536; code += 3) {     // a third of all 4x4 drafts
    const rows = [code & 15, (code >> 4) & 15, (code >> 8) & 15, (code >> 12) & 15];
    if (decide(matOf(rows, 4)).hangs !== hangsFast(rows, 4)) mm++;
  }
  ok('closure vs bitmask, 4x4 sample disagreements', mm, 0);
  /* the tournament criterion, over every 3x3 and every 4x4 draft */
  let sccMis3 = 0, sccGood3 = 0;
  for (let code = 0; code < 512; code++) {
    const M = matOf([code & 7, (code >> 3) & 7, (code >> 6) & 7], 3);
    const a = decide(M).hangs, b = hangsSCC(M);
    if (b) sccGood3++;
    if (a !== b) sccMis3++;
  }
  ok('closure vs Clapham tournament, all 512 3x3 drafts: disagreements', sccMis3, 0);
  ok('tournament criterion agrees on the 3x3 count', sccGood3, 102);
  let sccMis4 = 0, sccGood4 = 0;
  for (let code = 0; code < 65536; code++) {
    const M = matOf([code & 15, (code >> 4) & 15, (code >> 8) & 15, (code >> 12) & 15], 4);
    const a = decide(M).hangs, b = hangsSCC(M);
    if (b) sccGood4++;
    if (a !== b) sccMis4++;
  }
  ok('closure vs Clapham tournament, all 65,536 4x4 drafts: disagreements', sccMis4, 0);
  ok('tournament criterion agrees on the 4x4 count', sccGood4, 22730);
  /* the degenerate 1x1 case both criteria must call a non-fabric */
  ok('1x1: neither draft hangs together', [hangs([[0]]), hangs([[1]]), hangsSCC([[0]]), hangsSCC([[1]])],
    [false, false, false, false]);
}

/* ------------------------------------------------------------------ */
/* 2. Named fabrics.                                                   */
/* ------------------------------------------------------------------ */

function satin(n, s) {
  const M = Array.from({ length: n }, () => new Array(n).fill(0));
  for (let i = 0; i < n; i++) M[i][(s * i) % n] = 1;
  return M;
}
function permDraft(order) {           // order is 1-indexed lifting sequence
  const n = order.length;
  return Array.from({ length: n }, (_, i) => {
    const r = new Array(n).fill(0); r[order[i] - 1] = 1; return r;
  });
}
const PLAIN = [[1, 0], [0, 1]];
const TWILL22 = Array.from({ length: 4 }, (_, i) =>
  Array.from({ length: 4 }, (_, j) => { const d = (j - i + 4) % 4; return (d === 0 || d === 1) ? 1 : 0; }));
/* 4x4 double cloth: warps/wefts 0,2 are the top layer, 1,3 the bottom.
   Each layer is plain weave; every top warp rides over every bottom weft,
   and every top weft rides over every bottom warp. */
const DOUBLE = Array.from({ length: 4 }, (_, i) => Array.from({ length: 4 }, (_, j) => {
  const it = i % 2 === 0, jt = j % 2 === 0;
  if (it && jt) return ((i / 2) + (j / 2)) % 2 === 0 ? 1 : 0;
  if (!it && !jt) return (((i - 1) / 2) + ((j - 1) / 2)) % 2 === 0 ? 1 : 0;
  return it ? 0 : 1;
}));
const IRREG6 = permDraft([1, 3, 6, 4, 2, 5]);

section('2. named fabrics: hangs together?');
ok('plain weave 2x2 hangs', hangs(PLAIN), true);
ok('2/2 twill 4x4 hangs', hangs(TWILL22), true);
ok('satin n=5 s=2 hangs', hangs(satin(5, 2)), true);
ok('satin n=5 s=3 hangs', hangs(satin(5, 3)), true);
ok('satin n=7 s=2 hangs', hangs(satin(7, 2)), true);
ok('satin n=8 s=3 hangs', hangs(satin(8, 3)), true);
ok('satin n=12 s=5 hangs', hangs(satin(12, 5)), true);
ok('six-end step 2 hangs', hangs(satin(6, 2)), false);
ok('six-end step 3 hangs', hangs(satin(6, 3)), false);
ok('four-end step 2 hangs', hangs(satin(4, 2)), false);
ok('irregular six-end 1,3,6,4,2,5 hangs', hangs(IRREG6), true);
ok('4x4 double cloth hangs', hangs(DOUBLE), false);

section('2b. how each failure fails');
{
  /* six-end step 2: warps 2,4,6 (1-indexed) never rise at all. The rest of the
     cloth lifts clean away from them. */
  const M = satin(6, 2);
  const neverUp = [];
  for (let j = 0; j < 6; j++) { let s = 0; for (let i = 0; i < 6; i++) s += M[i][j]; if (s === 0) neverUp.push(j + 1); }
  ok('six-end step 2: warps that never pass over any weft', neverUp, [2, 4, 6]);
  const w = decide(M).witnesses[0];
  ok('six-end step 2: warps in the lifting sheet (1-indexed)', w.W.map(x => x + 1), [1, 3, 5]);
  ok('six-end step 2: wefts in the lifting sheet (1-indexed)', w.F.map(x => x + 1), [1, 2, 3, 4, 5, 6]);

  const M3 = satin(6, 3);
  const nu3 = [];
  for (let j = 0; j < 6; j++) { let s = 0; for (let i = 0; i < 6; i++) s += M3[i][j]; if (s === 0) nu3.push(j + 1); }
  ok('six-end step 3: warps that never pass over any weft', nu3, [2, 3, 5, 6]);

  /* double cloth: no loose strand at all, yet it splits 2+2 / 2+2. */
  const dw = decide(DOUBLE).witnesses[0];
  ok('double cloth: lifting warps (1-indexed)', dw.W.map(x => x + 1), [1, 3]);
  ok('double cloth: lifting wefts (1-indexed)', dw.F.map(x => x + 1), [1, 3]);
  ok('double cloth has no all-over or all-under strand', hasLooseStrand(rowsOf(DOUBLE), 4), false);
}

/* ------------------------------------------------------------------ */
/* 3. Every permutation draft hangs together.                          */
/* ------------------------------------------------------------------ */

function permutations(a) {
  if (a.length <= 1) return [a];
  const out = [];
  a.forEach((x, i) => permutations([...a.slice(0, i), ...a.slice(i + 1)]).forEach(p => out.push([x, ...p])));
  return out;
}

section('3. single-riser (permutation) drafts');
for (const n of [2, 3, 4, 5, 6]) {
  const ps = permutations([...Array(n).keys()]);
  let h = 0;
  for (const p of ps) h += hangs(permDraft(p.map(v => v + 1))) ? 1 : 0;
  ok(`n=${n}: permutation drafts that hang / total`, [h, ps.length], [ps.length, ps.length]);
}

/* The weaving-practice spacing rule, formalised: reading down the repeat
   cyclically, no two consecutive risers may sit in the same or an adjacent
   warp column (mod n). Regular satins satisfy it exactly when 1 < s < n-1. */
function spacedOrders(n) {
  const out = [];
  for (const p of permutations([...Array(n).keys()])) {
    let ok2 = true;
    for (let i = 0; i < n; i++) {
      const d = ((p[(i + 1) % n] - p[i]) % n + n) % n;
      if (d === 0 || d === 1 || d === n - 1) { ok2 = false; break; }
    }
    if (ok2) out.push(p.map(v => v + 1));
  }
  return out;
}
section('3b. admissible single-riser orders under the spacing rule');
{
  const counts = {};
  for (const n of [4, 5, 6, 7, 8]) counts[n] = spacedOrders(n).length;
  ok('spaced single-riser orders, n=4..8', counts, { 4: 0, 5: 10, 6: 36, 7: 322, 8: 2832 });
  const six = spacedOrders(6).map(o => o.join(','));
  ok('1,3,6,4,2,5 is one of the 36 admissible six-end orders', six.includes('1,3,6,4,2,5'), true);
  ok('every spaced order also hangs together, n=6', spacedOrders(6).every(o => hangs(permDraft(o))), true);
  /* at n=5 the ten spaced orders are exactly the five row-rotations of each of
     the two regular satins */
  const rot = (o, k) => o.map((_, i) => o[(i + k) % o.length]);
  const fromSatin = new Set();
  for (const s of [2, 3]) {
    const base = [...Array(5).keys()].map(i => (s * i) % 5 + 1);
    for (let k = 0; k < 5; k++) fromSatin.add(rot(base, k).join(','));
  }
  ok('n=5: the 10 spaced orders are exactly the rotations of the 2 regular satins',
    spacedOrders(5).map(o => o.join(',')).sort().join('|') === [...fromSatin].sort().join('|'), true);
}

/* ------------------------------------------------------------------ */
/* 4. The satin arithmetic.                                            */
/* ------------------------------------------------------------------ */

function gcd(a, b) { while (b) { const t = a % b; a = b; b = t; } return a; }
function satinSteps(n) { const o = []; for (let s = 2; s < n - 1; s++) if (gcd(s, n) === 1) o.push(s); return o; }
function modInv(s, n) { for (let t = 1; t < n; t++) if ((s * t) % n === 1) return t; return null; }
function satinClasses(n) {
  const steps = satinSteps(n), seen = new Set(), out = [];
  for (const s of steps) {
    if (seen.has(s)) continue;
    const orb = new Set(), stack = [s];
    while (stack.length) {
      const x = stack.pop();
      if (orb.has(x)) continue;
      orb.add(x);
      for (const y of [(n - x) % n, modInv(x, n)]) if (y != null && steps.includes(y) && !orb.has(y)) stack.push(y);
    }
    orb.forEach(x => seen.add(x));
    out.push([...orb].sort((a, b) => a - b));
  }
  return out;
}

section('4. regular satin steps: 1 < s < n-1 and gcd(s,n) = 1');
{
  const table = {};
  for (let n = 4; n <= 24; n++) table[n] = satinSteps(n);
  ok('n=4  (no regular satin)', table[4], []);
  ok('n=5', table[5], [2, 3]);
  ok('n=6  (no regular satin)', table[6], []);
  ok('n=7', table[7], [2, 3, 4, 5]);
  ok('n=8', table[8], [3, 5]);
  ok('n=9', table[9], [2, 4, 5, 7]);
  ok('n=10', table[10], [3, 7]);
  ok('n=12', table[12], [5, 7]);
  ok('n=16', table[16], [3, 5, 7, 9, 11, 13]);
  ok('n=24', table[24], [5, 7, 11, 13, 17, 19]);
  const empty = [];
  for (let n = 4; n <= 24; n++) if (table[n].length === 0) empty.push(n);
  ok('the only repeat sizes 4..24 with NO regular satin', empty, [4, 6]);
  /* the reason: s*i mod n is a permutation of the columns iff gcd(s,n)=1 */
  let bad = 0;
  for (let n = 3; n <= 16; n++) for (let s = 1; s < n; s++) {
    const cols = new Set(); for (let i = 0; i < n; i++) cols.add((s * i) % n);
    if ((cols.size === n) !== (gcd(s, n) === 1)) bad++;
  }
  ok('gcd(s,n)=1 <=> the risers hit every warp exactly once (counterexamples)', bad, 0);
  /* and when gcd = d > 1, exactly n - n/d warps are never bound */
  let bad2 = 0;
  for (let n = 4; n <= 16; n++) for (let s = 1; s < n; s++) {
    const d = gcd(s, n);
    const M = satin(n, s);
    let never = 0;
    for (let j = 0; j < n; j++) { let t = 0; for (let i = 0; i < n; i++) t += M[i][j]; if (t === 0) never++; }
    if (never !== n - n / d) bad2++;
  }
  ok('gcd(s,n)=d leaves exactly n - n/d warps unbound (counterexamples)', bad2, 0);
}

section('4b. when are two satins the same cloth (s ~ -s ~ s^-1 mod n)');
{
  ok('n=5 classes', satinClasses(5), [[2, 3]]);
  ok('n=7 classes', satinClasses(7), [[2, 3, 4, 5]]);
  ok('n=8 classes', satinClasses(8), [[3, 5]]);
  ok('n=10 classes', satinClasses(10), [[3, 7]]);
  ok('n=11 classes', satinClasses(11), [[2, 5, 6, 9], [3, 4, 7, 8]]);
  ok('n=12 classes', satinClasses(12), [[5, 7]]);
  ok('n=13 classes', satinClasses(13), [[2, 6, 7, 11], [3, 4, 9, 10], [5, 8]]);
  const counts = {};
  for (let n = 4; n <= 16; n++) counts[n] = satinClasses(n).length;
  ok('number of satin classes, n=4..16', counts,
    { 4: 0, 5: 1, 6: 0, 7: 1, 8: 1, 9: 1, 10: 1, 11: 2, 12: 1, 13: 3, 14: 1, 15: 2, 16: 2 });
  let first3 = null;
  for (let n = 4; n <= 40 && first3 === null; n++) if (satinClasses(n).length >= 3) first3 = n;
  ok('smallest repeat with three or more inequivalent regular satins', first3, 13);
}

/* ------------------------------------------------------------------ */
/* 5. Loose strands: the trivial way to fall apart.                    */
/* ------------------------------------------------------------------ */

function hasLooseStrand(rows, n) {
  const FULL = (1 << n) - 1;
  for (let i = 0; i < n; i++) if (rows[i] === 0 || rows[i] === FULL) return true;
  for (let j = 0; j < n; j++) { let a = 0; for (let i = 0; i < n; i++) a += (rows[i] >>> j) & 1; if (a === 0 || a === n) return true; }
  return false;
}
/* Exact count of n x n binary matrices with at least one constant row or
   constant column, by inclusion-exclusion. If r >= 1 rows and c >= 1 columns
   are all constant they must share one value, hence the factor 2. */
function binom(n, k) { let r = 1; for (let i = 0; i < k; i++) r = r * (n - i) / (i + 1); return Math.round(r); }
function looseCountExact(n) {
  let s = 0;
  for (let r = 0; r <= n; r++) for (let c = 0; c <= n; c++) {
    if (r === 0 && c === 0) continue;
    let cnt;
    if (c === 0) cnt = Math.pow(2, r) * Math.pow(2, (n - r) * n);
    else if (r === 0) cnt = Math.pow(2, c) * Math.pow(2, n * (n - c));
    else cnt = 2 * Math.pow(2, (n - r) * (n - c));
    s += ((r + c) % 2 === 1 ? 1 : -1) * binom(n, r) * binom(n, c) * cnt;
  }
  return s;
}

section('5. a loose strand always breaks the fabric');
{
  let bad = 0;
  for (let code = 0; code < 65536; code++) {
    const rows = [code & 15, (code >> 4) & 15, (code >> 8) & 15, (code >> 12) & 15];
    if (hasLooseStrand(rows, 4) && hangsFast(rows, 4)) bad++;
  }
  ok('4x4 drafts with a loose strand that nevertheless hang', bad, 0);
  for (const n of [2, 3, 4]) {
    let brute = 0;
    for (let code = 0; code < (1 << (n * n)); code++) {
      const rows = []; for (let i = 0; i < n; i++) rows.push((code >>> (i * n)) & ((1 << n) - 1));
      if (hasLooseStrand(rows, n)) brute++;
    }
    ok(`n=${n}: loose-strand count, enumerated vs inclusion-exclusion`, [brute, looseCountExact(n)], [brute, brute]);
  }
}

/* ------------------------------------------------------------------ */
/* 6. The census.                                                      */
/* ------------------------------------------------------------------ */

function census(n) {
  const total = Math.pow(2, n * n);
  const rows = new Int32Array(n), FULL = (1 << n) - 1;
  let good = 0, loose = 0, subtle = 0;
  for (let code = 0; code < total; code++) {
    for (let i = 0; i < n; i++) rows[i] = (code >>> (i * n)) & FULL;
    const h = hangsFast(rows, n);
    if (h) { good++; continue; }
    if (hasLooseStrand(rows, n)) loose++; else subtle++;
  }
  return { total, good, loose, subtle };
}

section('6. exhaustive census of n x n drafts');
{
  const c2 = census(2), c3 = census(3), c4 = census(4);
  ok('n=2: hang / total', [c2.good, c2.total], [2, 16]);
  ok('n=3: hang / total', [c3.good, c3.total], [102, 512]);
  ok('n=4: hang / total', [c4.good, c4.total], [22730, 65536]);
  ok('n=2: failures with a loose strand / subtle failures', [c2.loose, c2.subtle], [14, 0]);
  ok('n=3: failures with a loose strand / subtle failures', [c3.loose, c3.subtle], [410, 0]);
  ok('n=4: failures with a loose strand / subtle failures', [c4.loose, c4.subtle], [42662, 144]);
  ok('n=4: loose-strand count matches inclusion-exclusion', c4.loose, looseCountExact(4));

  /* the two 2x2 survivors are exactly the two permutation drafts */
  const surv = [];
  for (let code = 0; code < 16; code++) {
    const rows = [code & 3, (code >> 2) & 3];
    if (hangsFast(rows, 2)) surv.push(matOf(rows, 2));
  }
  ok('the 2x2 survivors', surv.sort((a, b) => a[0][0] - b[0][0]), [[[0, 1], [1, 0]], [[1, 0], [0, 1]]]);

  const pct = x => Number((100 * x.good / x.total).toFixed(4));
  ok('hanging percentages n=2,3,4', [pct(c2), pct(c3), pct(c4)], [12.5, 19.9219, 34.6832]);
  ok('the hanging fraction rises with n', pct(c2) < pct(c3) && pct(c3) < pct(c4), true);
}

section('6b. the 144 subtle failures at 4x4 are all double cloths');
{
  const subtleCodes = [];
  for (let code = 0; code < 65536; code++) {
    const rows = [code & 15, (code >> 4) & 15, (code >> 8) & 15, (code >> 12) & 15];
    if (hasLooseStrand(rows, 4)) continue;
    if (hangsFast(rows, 4)) continue;
    subtleCodes.push(code);
  }
  ok('subtle failures at 4x4', subtleCodes.length, 144);
  const shapes = new Set();
  for (const code of subtleCodes) {
    const rows = [code & 15, (code >> 4) & 15, (code >> 8) & 15, (code >> 12) & 15];
    for (const w of decide(matOf(rows, 4)).witnesses) shapes.add(`${w.W.length}w+${w.F.length}f`);
  }
  ok('witness shapes among the 144', [...shapes], ['2w+2f']);

  /* symmetry reduction: cyclic row shift, cyclic column shift, transpose,
     complement (turning the cloth over), row reversal, column reversal */
  const toM = rs => rs.map(r => [0, 1, 2, 3].map(j => (r >>> j) & 1));
  const fromM = M => M.map(r => r.reduce((a, b, j) => a | (b << j), 0));
  const OPS = [
    M => M.map((_, i) => M[(i + 1) % 4]),
    M => M.map(r => r.map((_, j) => r[(j + 1) % 4])),
    M => M[0].map((_, j) => M.map(r => r[j])),
    M => M.map(r => r.map(v => 1 - v)),
    M => M.slice().reverse(),
    M => M.map(r => r.slice().reverse())
  ];
  let breaks = 0;
  for (let code = 0; code < 65536; code += 7) {
    const rows = [code & 15, (code >> 4) & 15, (code >> 8) & 15, (code >> 12) & 15];
    const h = hangsFast(rows, 4);
    for (const op of OPS) if (hangsFast(fromM(op(toM(rows))), 4) !== h) breaks++;
  }
  ok('all six symmetry operations preserve hanging-together (violations)', breaks, 0);

  const codeOf = rs => rs.reduce((a, r, i) => a | (r << (4 * i)), 0);
  const set = new Set(subtleCodes), seen = new Set();
  let orbits = 0;
  for (const code of subtleCodes) {
    if (seen.has(code)) continue;
    orbits++;
    const stack = [code];
    while (stack.length) {
      const c = stack.pop();
      if (seen.has(c)) continue;
      seen.add(c);
      const rows = [c & 15, (c >> 4) & 15, (c >> 8) & 15, (c >> 12) & 15];
      for (const op of OPS) { const q = codeOf(fromM(op(toM(rows)))); if (!seen.has(q)) stack.push(q); }
    }
  }
  ok('symmetry classes among the 144', orbits, 4);
  ok('every orbit member is itself a subtle failure', [...seen].every(c => set.has(c)), true);
  ok('the 4x4 double cloth is one of the 144', set.has(rowsOf(DOUBLE).reduce((a, r, i) => a | (r << (4 * i)), 0)), true);
}

if (!QUICK) {
  section('6c. exhaustive 5x5 census (33,554,432 drafts; ~14 s)');
  const t0 = Date.now();
  const c5 = census(5);
  ok('n=5: hang / total', [c5.good, c5.total], [17564070, 33554432]);
  ok('n=5: failures with a loose strand', c5.loose, 15920762);
  ok('n=5: subtle failures', c5.subtle, 69600);
  ok('n=5: loose-strand count matches inclusion-exclusion', c5.loose, looseCountExact(5));
  ok('n=5: hanging fraction exceeds one half', Number((100 * c5.good / c5.total).toFixed(4)), 52.345);
  console.log(`  (5x5 census took ${((Date.now() - t0) / 1000).toFixed(1)} s)`);
} else {
  console.log('\n== 6c. 5x5 census SKIPPED (--quick)');
}

/* ------------------------------------------------------------------ */
/* 7. Where the failures go as n grows.                                */
/* ------------------------------------------------------------------ */

section('7. the loose-strand fraction, exactly');
{
  const frac = n => looseCountExact(n) / Math.pow(2, n * n);
  ok('n=12 loose-strand fraction (%), 4 dp', Number((100 * frac(12)).toFixed(4)), 1.1653);
  ok('n=16 loose-strand fraction (%), 4 dp', Number((100 * frac(16)).toFixed(4)), 0.0976);
  ok('it is decreasing from n=4 to n=20', (() => {
    for (let n = 4; n < 20; n++) if (!(frac(n) > frac(n + 1))) return false;
    return true;
  })(), true);
  /* 4n * 2^-n is the leading term: 2n rows + 2n columns, each constant with
     probability 2^{1-n}, so 4n*2^{-n}. Check the ratio tends to 1. */
  const ratio = n => frac(n) / (4 * n * Math.pow(2, -n));
  ok('frac(n) / (4n*2^-n) at n=20, 4 dp', Number(ratio(20).toFixed(4)), 1.0);
}

section('7b. deterministic Monte Carlo sampler (same generator the page uses)');
{
  /* xorshift128, seeded identically to the page's default seed */
  function mkrng(a, b, c, d) {
    return function () {
      let t = d; const s = a; d = c; c = b; b = s;
      t ^= t << 11; t ^= t >>> 8; a = (t ^ s ^ (s >>> 19)) >>> 0; return a;
    };
  }
  const rng = mkrng(123456789, 362436069, 521288629, 88675123);
  function sample(n, N) {
    const FULL = (1 << n) - 1, rows = new Int32Array(n);
    let g = 0;
    for (let k = 0; k < N; k++) { for (let i = 0; i < n; i++) rows[i] = rng() & FULL; if (hangsFast(rows, n)) g++; }
    return g / N;
  }
  /* the sampler must land near the exact answers where we know them */
  const p4 = sample(4, 200000);
  ok('sampled 4x4 fraction within 0.5 pp of the exact 34.6832%', Math.abs(100 * p4 - 34.6832) < 0.5, true);
  const p5 = sample(5, 200000);
  ok('sampled 5x5 fraction within 0.5 pp of the exact 52.3450%', Math.abs(100 * p5 - 52.3450) < 0.5, true);
  /* and it must agree with the loose-strand lower bound at large n */
  const p12 = sample(12, 200000);
  const lb = 1 - looseCountExact(12) / Math.pow(2, 144);
  ok('sampled 12x12 fraction within 0.3 pp of the loose-strand bound', Math.abs(p12 - lb) < 0.003, true);
}

/* ------------------------------------------------------------------ */
/* 8. Interlacement statistics the Thread Pull instrument shows.       */
/* ------------------------------------------------------------------ */

function threadStats(M) {
  const n = M.length, m = M[0].length;
  function runs(seq) {
    const L = seq.length;
    let changes = 0;
    for (let k = 0; k < L; k++) if (seq[k] !== seq[(k + 1) % L]) changes++;
    if (changes === 0) return { binds: 0, longest: L };
    let longest = 0, start = 0;
    while (seq[start] === seq[(start - 1 + L) % L]) start++;
    let run = 0;
    for (let k = 0; k < L; k++) {
      const a = seq[(start + k) % L], b = seq[(start + k + 1) % L];
      run++;
      if (a !== b) { if (run > longest) longest = run; run = 0; }
    }
    if (run > longest) longest = run;
    return { binds: changes, longest };
  }
  const warps = [], wefts = [];
  for (let j = 0; j < m; j++) warps.push(runs(Array.from({ length: n }, (_, i) => M[i][j])));
  for (let i = 0; i < n; i++) wefts.push(runs(M[i].slice()));
  return { warps, wefts };
}

section('8. binding points and float lengths');
{
  const p = threadStats(PLAIN);
  ok('plain weave: binds per warp per repeat', p.warps.map(w => w.binds), [2, 2]);
  ok('plain weave: longest float', p.warps.map(w => w.longest), [1, 1]);
  const s5 = threadStats(satin(5, 2));
  ok('5-end satin: binds per warp per repeat', s5.warps.map(w => w.binds), [2, 2, 2, 2, 2]);
  ok('5-end satin: longest warp float', s5.warps.map(w => w.longest), [4, 4, 4, 4, 4]);
  ok('5-end satin: longest weft float', s5.wefts.map(w => w.longest), [4, 4, 4, 4, 4]);
  const t = threadStats(TWILL22);
  ok('2/2 twill: binds per warp per repeat', t.warps.map(w => w.binds), [2, 2, 2, 2]);
  ok('2/2 twill: longest float', t.warps.map(w => w.longest), [2, 2, 2, 2]);
  const bad6 = threadStats(satin(6, 2));
  /* risers pile up two-deep on warps 1,3,5 and never touch warps 2,4,6 */
  ok('six-end step 2: binds per warp (three warps bind nothing)', bad6.warps.map(w => w.binds), [4, 0, 4, 0, 4, 0]);
  ok('six-end step 2: unbound warps float across the whole repeat', bad6.warps.map(w => w.longest), [2, 6, 2, 6, 2, 6]);
  const i6 = threadStats(IRREG6);
  ok('irregular six-end: binds per warp', i6.warps.map(w => w.binds), [2, 2, 2, 2, 2, 2]);
  ok('irregular six-end: longest warp float', i6.warps.map(w => w.longest), [5, 5, 5, 5, 5, 5]);
  /* the interlacement ratio the page quotes for plain vs 5-end satin */
  const perPick = (M, st) => st.warps.reduce((a, w) => a + w.binds, 0) / (M.length * M[0].length);
  ok('binds per crossing: plain weave', Number(perPick(PLAIN, p).toFixed(4)), 1);
  ok('binds per crossing: 5-end satin', Number(perPick(satin(5, 2), s5).toFixed(4)), 0.4);
  ok('plain weave binds 2.5x as often as 5-end satin',
    Number((perPick(PLAIN, p) / perPick(satin(5, 2), s5)).toFixed(4)), 2.5);
}

/* ------------------------------------------------------------------ */
/* 9. The drawdown really is a boolean matrix product.                 */
/* ------------------------------------------------------------------ */

function boolProduct(A, B) {   // A: p x q, B: q x r
  const p = A.length, q = B.length, r = B[0].length;
  return Array.from({ length: p }, (_, i) =>
    Array.from({ length: r }, (_, k) => {
      for (let j = 0; j < q; j++) if (A[i][j] && B[j][k]) return 1;
      return 0;
    }));
}
function distinctColumns(M) {
  const s = new Set();
  for (let j = 0; j < M[0].length; j++) s.add(M.map(r => r[j]).join(''));
  return s.size;
}
function distinctRows(M) { return new Set(M.map(r => r.join(''))).size; }

section('9. drawdown = treadling x tie-up x threading, over the boolean semiring');
{
  const n = 5, s = 2;
  const T = Array.from({ length: n }, (_, sh) => Array.from({ length: n }, (_, j) => sh === j ? 1 : 0));   // straight draw
  const U = Array.from({ length: n }, (_, t) => Array.from({ length: n }, (_, sh) => sh === t ? 1 : 0));   // direct tie-up
  const R = Array.from({ length: n }, (_, i) => Array.from({ length: n }, (_, t) => t === (s * i) % n ? 1 : 0));
  const D = boolProduct(R, boolProduct(U, T));
  ok('R x U x T reproduces the 5-end satin', D, satin(n, s));
  ok('5-end satin: distinct warp columns = minimum shafts', distinctColumns(satin(5, 2)), 5);
  ok('5-end satin: distinct picks = minimum treadles', distinctRows(satin(5, 2)), 5);
  ok('plain weave: minimum shafts', distinctColumns(PLAIN), 2);
  ok('2/2 twill: minimum shafts', distinctColumns(TWILL22), 4);
  ok('4x4 double cloth: minimum shafts', distinctColumns(DOUBLE), 4);
  /* a six-end step-2 draft needs only three shafts: half its warps are identical */
  ok('six-end step 2: distinct warp columns', distinctColumns(satin(6, 2)), 4);
  /* threading two ends on one shaft forces identical drawdown columns */
  let viol = 0;
  for (let trial = 0; trial < 200; trial++) {
    const ends = 6, shafts = 4, picks = 6;
    const th = Array.from({ length: shafts }, () => new Array(ends).fill(0));
    const assign = Array.from({ length: ends }, () => Math.floor(Math.random() * shafts));
    assign.forEach((sh, j) => th[sh][j] = 1);
    const tu = Array.from({ length: picks }, () => Array.from({ length: shafts }, () => Math.random() < 0.5 ? 1 : 0));
    const tr = Array.from({ length: picks }, (_, i) => Array.from({ length: picks }, (_, t) => t === i ? 1 : 0));
    const Dd = boolProduct(tr, boolProduct(tu, th));
    if (distinctColumns(Dd) > new Set(assign).size) viol++;
  }
  ok('random looms: distinct drawdown columns never exceed shafts used', viol, 0);
}

/* ------------------------------------------------------------------ */

console.log(`\n${'-'.repeat(64)}`);
if (FAILS.length) {
  console.log(`FAILED: ${FAILS.length} assertion(s) of ${PASS + FAILS.length}`);
  FAILS.forEach(f => console.log('  * ' + f));
  process.exit(1);
}
console.log(`ALL ${PASS} ASSERTIONS PASS.`);
process.exit(0);
