// verify.mjs — Langton's Ant, the genuine deterministic 2-state cellular automaton.
//
// THE RULE (Langton 1986). A single ant sits on an infinite grid of cells, each
// white (0) or black (1), all white to start. The ant carries a heading. Each step:
//   • read the cell under the ant;
//   • if WHITE: turn 90° RIGHT,  flip the cell to black, step one cell forward;
//   • if BLACK: turn 90° LEFT,   flip the cell to white, step one cell forward.
// Two lines of rule. Nothing random. Nothing tuned.
//
// THE FACT we are here to confirm, not assert from memory: from the empty grid the
// trajectory looks chaotic for thousands of steps, then — with no intervention —
// the ant locks into a "highway": a single periodic motif that repeats forever and
// drags the ant off diagonally. We DETECT the period and the onset step and the
// per-period displacement directly from the simulation and print them; the stratum
// and the WLTV system quote only what this script prints.
//
// (The unboundedness of the trajectory from any finite start is a theorem —
// Bunimovich & Troubetzkoy, J. Stat. Phys. 67 (1992) 289–302: an ant whose
// trajectory were bounded would be impossible because each cell visited infinitely
// often forces a contradiction. We do not "prove" it here; we exhibit the highway
// the theorem's most famous instance produces, and confirm it is exactly periodic.)
//
// Run:  node research/langtons-ant/verify.mjs
import { writeFileSync } from 'node:fs';

// Heading 0,1,2,3 = N,E,S,W. dx/dy for a forward step (y grows downward).
const DX = [0, 1, 0, -1];
const DY = [-1, 0, 1, 0];

function run(maxSteps) {
  const cells = new Map();           // "x,y" -> 1 (black). absent = white (0).
  const key = (x, y) => x + ',' + y;
  let x = 0, y = 0, dir = 0;
  const turns = new Uint8Array(maxSteps);   // 1 = turned right (cell was white), 0 = left
  const px = new Int32Array(maxSteps + 1);
  const py = new Int32Array(maxSteps + 1);
  px[0] = x; py[0] = y;
  for (let s = 0; s < maxSteps; s++) {
    const k = key(x, y);
    const black = cells.get(k) === 1;
    if (black) { dir = (dir + 3) & 3; cells.delete(k); turns[s] = 0; }   // turn left, flip to white
    else       { dir = (dir + 1) & 3; cells.set(k, 1); turns[s] = 1; }   // turn right, flip to black
    x += DX[dir]; y += DY[dir];
    px[s + 1] = x; py[s + 1] = y;
  }
  return { turns, px, py, blackCount: cells.size, end: { x, y, dir } };
}

// Find the highway: the smallest onset t0 such that the turn-sequence is exactly
// P-periodic from t0 to the end, for the known candidate period. We do NOT hardcode
// the period — we discover the smallest P>1 for which a long suffix is P-periodic,
// then report the onset for that P.
function detectHighway({ turns }, N) {
  // The tail must sit ENTIRELY past the highway onset (~10k), or it straddles the
  // pre-highway chaos and no single period fits. The last ~1500 steps are clean.
  const tail = Math.min(1500, N >> 2);                 // search periods using a clean tail
  let bestP = 0;
  for (let P = 2; P <= 2000; P++) {                     // smallest period that the tail obeys
    let ok = true;
    for (let i = N - 1; i >= N - tail; i--) {
      if (turns[i] !== turns[i - P]) { ok = false; break; }
    }
    if (ok) { bestP = P; break; }
  }
  if (!bestP) return { period: 0, onset: -1 };
  // walk the onset back as far as the periodicity holds continuously to the end
  let t0 = N - 1;
  while (t0 - bestP >= 0 && turns[t0] === turns[t0 - bestP]) t0--;
  t0 += 1;                                              // first index where period holds to N
  return { period: bestP, onset: t0 };
}

const N = 12000;
const sim = run(N);
const { period, onset } = detectHighway(sim, N);

// per-period displacement, measured once the highway is established
const a = onset + period * 2, b = a + period;          // two full periods in, to be safely on-highway
const disp = { dx: sim.px[b] - sim.px[a], dy: sim.py[b] - sim.py[a] };
const turnsInPeriod = (() => { let r = 0; for (let i = a; i < a + period; i++) r += sim.turns[i]; return { right: r, left: period - r }; })();

// sanity: re-confirm the period really holds across many cycles, not just the tail
let cyclesConfirmed = 0;
for (let t = onset; period > 0 && t + period <= N; t += period) {
  let same = true;
  for (let i = 0; i < period; i++) if (sim.turns[t + i] !== sim.turns[onset + ((i) % period)]) { same = false; break; }
  // (compare each cycle's turn-pattern to the first on-highway cycle)
  let same2 = true;
  for (let i = 0; i < period && t + period + i < N; i++) if (sim.turns[t + i] !== sim.turns[t + period + i]) { same2 = false; break; }
  if (same2) cyclesConfirmed++;
}

const out = {
  rule: "white: turn right, paint black, step; black: turn left, paint white, step",
  steps_simulated: N,
  highway_period: period,
  highway_onset_step: onset,
  displacement_per_period: disp,
  diagonal_speed_cells_per_period: Math.abs(disp.dx) + Math.abs(disp.dy),
  turns_per_period: turnsInPeriod,
  black_cells_at_end: sim.blackCount,
  full_highway_cycles_confirmed: cyclesConfirmed,
  theorem: "Bunimovich & Troubetzkoy 1992: the trajectory is unbounded from any finite configuration",
};
console.log(JSON.stringify(out, null, 2));

// assertions — the script FAILS loudly if the famous facts don't hold
const A = (c, m) => { if (!c) { console.error('FAIL: ' + m); process.exit(1); } };
A(period === 104, `highway period should be 104, got ${period}`);
A(onset > 9000 && onset < 11000, `highway onset should be ~10k, got ${onset}`);
A(Math.abs(disp.dx) === 2 && Math.abs(disp.dy) === 2, `displacement should be (±2,±2), got (${disp.dx},${disp.dy})`);
console.log('\nOK — Langton highway confirmed: period 104, diagonal (2,2) drift, onset ~' + onset + '.');

writeFileSync(new URL('./highway.json', import.meta.url), JSON.stringify(out, null, 2) + '\n');
