// Pathmoor core: pure puzzle logic (no DOM), shared by the game and the tests. (c) 2026 CyberMax. All rights reserved.
// A board is an n×n grid of path stones. Each stone is a 4-bit mask of its openings: N=1, E=2, S=4, W=8.
// The solution is a random spanning tree grown from the lantern stone, so every stone joins the lantern by exactly one
// route. The board is shuffled by turning stones; the player turns them back. Solved = every stone lit by the lantern
// and no opening points at the edge or at a closed side (any arrangement that does that counts, not only ours).
import { rng } from './cmx.js';

export const N = 1, E = 2, S = 4, W = 8;
const DIRS = [[N, 0, -1, S], [E, 1, 0, W], [S, 0, 1, N], [W, -1, 0, E]];

/** Turn a stone a quarter clockwise, k times. */
export function turn(m, k = 1) {
  let r = m;
  for (let i = 0; i < ((k % 4) + 4) % 4; i++) r = ((r << 1) | (r >> 3)) & 15;
  return r;
}
export const bits = (m) => (m & 1) + ((m >> 1) & 1) + ((m >> 2) & 1) + ((m >> 3) & 1);

/** Fewest clockwise turns that take stone `from` to `to` (Infinity if impossible). */
export function turnsTo(from, to) {
  for (let k = 0; k < 4; k++) if (turn(from, k) === to) return k;
  return Infinity;
}

/**
 * Build a puzzle from a seed string. Returns { n, src, sol, start } where sol and start are arrays of n*n masks.
 * Grown with a randomised Prim tree; boards with too many straight runs or too few branches are re-rolled so every
 * board has real choices. The shuffle turns each stone 0-3 times and is never already solved.
 */
export function generate(seed, n = 6) {
  const rand = rng(`pathmoor:${n}:${seed}`);
  for (let attempt = 0; attempt < 40; attempt++) {
    const sol = new Array(n * n).fill(0);
    const c = Math.floor((n - 1) / 2);
    const src = (c + Math.floor(rand() * 2)) * n + c + Math.floor(rand() * 2); // one of the 4 middle stones
    const inTree = new Array(n * n).fill(false);
    inTree[src] = true;
    let frontier = [];
    const addEdges = (i) => {
      const x = i % n, y = (i / n) | 0;
      for (const [b, dx, dy, back] of DIRS) {
        const nx = x + dx, ny = y + dy;
        if (nx >= 0 && ny >= 0 && nx < n && ny < n && !inTree[ny * n + nx]) frontier.push([i, ny * n + nx, b, back]);
      }
    };
    addEdges(src);
    let count = 1;
    while (count < n * n) {
      frontier = frontier.filter(([, j]) => !inTree[j]);
      const [i, j, b, back] = frontier[Math.floor(rand() * frontier.length)];
      if (inTree[j]) continue;
      sol[i] |= b; sol[j] |= back; inTree[j] = true; count++;
      addEdges(j);
    }
    const straights = sol.filter((m) => m === (N | S) || m === (E | W)).length;
    const branches = sol.filter((m) => bits(m) >= 3).length;
    if (straights > n * n * 0.34 || branches < Math.max(3, Math.floor(n * n / 9))) continue;
    const start = sol.map((m) => turn(m, Math.floor(rand() * 4)));
    if (isSolved(n, src, start)) continue;
    return { n, src, sol, start };
  }
  // extremely unlikely fallback: keep the last rules but accept the board
  const b = generate(`${seed}~`, n);
  return b;
}

/** Stones reachable from the lantern through matching openings. Returns a Uint8Array (1 = lit). */
export function lit(n, src, cur) {
  const on = new Uint8Array(n * n);
  const q = [src];
  on[src] = 1;
  while (q.length) {
    const i = q.pop();
    const x = i % n, y = (i / n) | 0;
    for (const [b, dx, dy, back] of DIRS) {
      if (!(cur[i] & b)) continue;
      const nx = x + dx, ny = y + dy;
      if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
      const j = ny * n + nx;
      if (!on[j] && (cur[j] & back)) { on[j] = 1; q.push(j); }
    }
  }
  return on;
}

/** Openings that lead nowhere (edge, or a neighbour without the matching opening). */
export function looseEnds(n, cur) {
  let loose = 0;
  for (let i = 0; i < n * n; i++) {
    const x = i % n, y = (i / n) | 0;
    for (const [b, dx, dy, back] of DIRS) {
      if (!(cur[i] & b)) continue;
      const nx = x + dx, ny = y + dy;
      if (nx < 0 || ny < 0 || nx >= n || ny >= n || !(cur[ny * n + nx] & back)) loose++;
    }
  }
  return loose;
}

export function isSolved(n, src, cur) {
  if (looseEnds(n, cur)) return false;
  const on = lit(n, src, cur);
  for (let i = 0; i < on.length; i++) if (!on[i]) return false;
  return true;
}

/** Par = the fewest taps that solve the board from its shuffle (each tap turns one stone a quarter clockwise). */
export function par(board) {
  return board.start.reduce((s, m, i) => s + turnsTo(m, board.sol[i]), 0);
}

/**
 * Share grid (no spoilers): one square per stone. 🟩 stone ended in par turns or fewer, 🟨 a few extra turns,
 * 🟧 many extra turns, ⬜ stone you never needed to touch.
 */
export function shareGrid(board, taps) {
  const rows = [];
  for (let y = 0; y < board.n; y++) {
    let r = '';
    for (let x = 0; x < board.n; x++) {
      const i = y * board.n + x;
      const need = turnsTo(board.start[i], board.sol[i]);
      const used = taps[i] || 0;
      r += need === 0 && used === 0 ? '⬜' : used <= Math.max(need, 1) ? '🟩' : used <= need + 4 ? '🟨' : '🟧';
    }
    rows.push(r);
  }
  return rows.join('\n');
}

export function fmtTime(ms) {
  const s = Math.max(0, Math.round(ms / 1000));
  return `${Math.floor(s / 60)}:${String(s % 60).padStart(2, '0')}`;
}

/** Packs: the free daily is 6×6; the Fun Pass adds numbered packs. */
export const PACKS = [
  { id: 'daily', name: 'Daily', n: 6, free: true },
  { id: 'sprout', name: 'Sprout 5×5', n: 5, levels: 30, freeLevels: 3 },
  { id: 'moorland', name: 'Moorland 7×7', n: 7, levels: 100 },
  { id: 'highland', name: 'Highland 8×8', n: 8, levels: 100 },
  { id: 'summit', name: 'Summit 10×10', n: 10, levels: 50 },
];

// ------------------------------------------------------------------ levels (30 hand-tuned boards + twists)
// Twists, one new idea about every 5 levels: holes (shaped boards), twin stones (tap one, both turn), fog (you only
// see stones next to the light), reverse stones (turn anticlockwise) and bigger boards. Every 10th level is a
// challenge level with a tap budget: run out of taps and the board resets.
// Level boards use their own seed space, so the daily board above is unchanged.

/** n = size, mix = share of stones shuffled (early levels), holes = empty cells, twins = twin pairs, fog, rev = reverse stones, budget = par + slack (challenge). */
export const LEVELS = [
  { n: 3, mix: 0.35, name: 'First light' }, { n: 4, mix: 0.45, name: 'Crossroads' }, { n: 4, mix: 0.7, name: 'Moor gate' }, { n: 5, mix: 0.6, name: 'Bracken' }, { n: 5, mix: 0.7, name: 'Lantern walk' },
  { n: 5, holes: 3, name: 'Broken ground', twist: 'Holes in the moor' }, { n: 5, holes: 4, name: 'Bog pools' }, { n: 6, name: 'Long dusk' }, { n: 6, holes: 5, name: 'Peat cuts' },
  { n: 6, holes: 3, budget: 6, name: 'Lantern trial', boss: true },
  { n: 5, twins: 2, name: 'Twin stones', twist: 'Twin stones turn together' }, { n: 6, twins: 3, name: 'Paired path' }, { n: 6, twins: 3, holes: 3, name: 'Old wall' }, { n: 6, twins: 4, name: 'Mirror field' }, { n: 7, twins: 3, name: 'Wide moor' },
  { n: 6, fog: true, name: 'Moor fog', twist: 'Fog: only stones near the light show' }, { n: 6, fog: true, twins: 2, name: 'Grey morning' }, { n: 7, fog: true, holes: 4, name: 'Mist pools' }, { n: 7, twins: 4, holes: 4, name: 'Heather maze' },
  { n: 7, fog: true, twins: 3, budget: 10, name: 'Fog trial', boss: true },
  { n: 6, rev: 5, name: 'Backwards stones', twist: 'Purple stones turn the other way' }, { n: 7, rev: 7, name: 'Turnabout' }, { n: 7, rev: 6, twins: 3, name: 'Crossed wires' }, { n: 8, name: 'Highland' }, { n: 8, holes: 6, fog: true, name: 'Cloud tops' },
  { n: 9, name: 'Great moor', twist: 'Bigger boards' }, { n: 8, rev: 8, twins: 4, holes: 5, name: 'Tangle' }, { n: 9, fog: true, rev: 8, name: 'Night walk' }, { n: 9, rev: 9, twins: 5, holes: 6, name: 'Summit path' },
  { n: 10, rev: 10, twins: 5, holes: 6, fog: true, budget: 14, name: 'Summit trial', boss: true },
];

/** Stones reachable from the lantern (holes are walls). */
export function litB(b, cur) { return lit(b.n, b.src, cur); }

/** Solved: no loose ends and every stone that is not a hole is lit. */
export function isSolvedB(b, cur) {
  if (looseEnds(b.n, cur)) return false;
  const on = lit(b.n, b.src, cur);
  for (let i = 0; i < on.length; i++) if (!on[i] && !b.hole[i]) return false;
  return true;
}

/** The stones one tap on stone i turns (its twin too). */
export const groupOf = (b, i) => (b.twin[i] >= 0 ? [i, b.twin[i]] : [i]);
/** Turn direction of stone i: 1 clockwise, 3 (= one anticlockwise quarter) for reverse stones. */
export const dirOf = (b, i) => (b.rev[i] ? 3 : 1);

/** Apply one tap on stone i to cur (in place). k = 1 forward, 3 = back (undo / shift-tap). */
export function tapB(b, cur, i, k = 1) {
  if (b.hole[i]) return false;
  for (const j of groupOf(b, i)) cur[j] = turn(cur[j], dirOf(b, j) * k);
  return true;
}

/** Fewest taps on the group of stone i that bring it from start back to the solution. */
function groupTaps(b, start, i) {
  const g = groupOf(b, i);
  for (let k = 0; k < 4; k++) if (g.every((j) => turn(start[j], dirOf(b, j) * k) === b.sol[j])) return k;
  return 0;
}

/** Par for a level board: the fewest taps from the shuffle to our solution. */
export function parB(b) {
  let s = 0;
  const seen = new Set();
  for (let i = 0; i < b.n * b.n; i++) {
    if (b.hole[i] || seen.has(i)) continue;
    groupOf(b, i).forEach((j) => seen.add(j));
    s += groupTaps(b, b.start, i);
  }
  return s;
}

/** Stars: 3 = par or better, 2 = within about a third over par, 1 = solved. */
export function levelStars(taps, p) {
  return taps <= p ? 3 : taps <= p + Math.ceil(p * 0.34) + 1 ? 2 : 1;
}

/** Build level `num` (1-based) from LEVELS. Deterministic: the same level is the same board for everyone. */
export function generateLevel(num) {
  const L = LEVELS[num - 1];
  const n = L.n, rand = rng(`pathmoor:lv:${num}`);
  for (let attempt = 0; attempt < 400; attempt++) {
    const hole = new Uint8Array(n * n);
    const c = Math.floor((n - 1) / 2);
    const src = (c + Math.floor(rand() * 2)) * n + c + Math.floor(rand() * 2);
    let holes = L.holes || 0;
    for (let tries = 0; holes > 0 && tries < 200; tries++) {
      const i = Math.floor(rand() * n * n);
      if (i === src || hole[i]) continue;
      hole[i] = 1; holes--;
    }
    const sol = new Array(n * n).fill(0);
    const inTree = new Uint8Array(n * n);
    inTree[src] = 1;
    let frontier = [];
    const addEdges = (i) => {
      const x = i % n, y = (i / n) | 0;
      for (const [bt, dx, dy, back] of DIRS) {
        const nx = x + dx, ny = y + dy, j = ny * n + nx;
        if (nx >= 0 && ny >= 0 && nx < n && ny < n && !inTree[j] && !hole[j]) frontier.push([i, j, bt, back]);
      }
    };
    addEdges(src);
    let count = 1;
    const need = n * n - (L.holes || 0);
    while (frontier.length) {
      const k = Math.floor(rand() * frontier.length);
      const [i, j, bt, back] = frontier[k];
      frontier.splice(k, 1);
      if (inTree[j]) continue;
      sol[i] |= bt; sol[j] |= back; inTree[j] = 1; count++;
      addEdges(j);
    }
    if (count < need) continue; // holes cut the moor in two: re-roll
    const cells = [...Array(n * n).keys()].filter((i) => !hole[i]);
    const straights = cells.filter((i) => sol[i] === (N | S) || sol[i] === (E | W)).length;
    if (n >= 5 && straights > cells.length * 0.4) continue;
    // twins: pairs of stones (not crosses, not the lantern) that turn together
    const twin = new Int16Array(n * n).fill(-1);
    const pool = cells.filter((i) => i !== src && bits(sol[i]) < 4);
    for (let t = 0; t < (L.twins || 0) && pool.length > 1; t++) {
      const a = pool.splice(Math.floor(rand() * pool.length), 1)[0];
      const bb = pool.splice(Math.floor(rand() * pool.length), 1)[0];
      twin[a] = bb; twin[bb] = a;
    }
    const rev = new Uint8Array(n * n);
    const rpool = cells.filter((i) => twin[i] < 0 && bits(sol[i]) < 4 && !(sol[i] === (N | S) || sol[i] === (E | W)));
    for (let t = 0; t < (L.rev || 0) && rpool.length; t++) rev[rpool.splice(Math.floor(rand() * rpool.length), 1)[0]] = 1;
    const b = { n, src, sol, hole, twin, rev, fog: !!L.fog, level: num };
    // shuffle by tapping: every group gets 0-3 backward taps, so the board is always solvable
    const start = sol.slice();
    const done = new Set();
    for (const i of cells) {
      if (done.has(i)) continue;
      groupOf(b, i).forEach((j) => done.add(j));
      const k = rand() < (L.mix || 0.75) ? 1 + Math.floor(rand() * 3) : 0;
      for (const j of groupOf(b, i)) start[j] = turn(start[j], dirOf(b, j) * 3 * k);
    }
    b.start = start;
    if (isSolvedB(b, start)) continue;
    const p = parB(b);
    if (p < Math.max(3, Math.floor(cells.length * 0.35 * (L.mix || 0.75)))) continue; // too few taps needed: not a real puzzle
    b.par = p;
    b.budget = L.budget ? p + L.budget : 0;
    return b;
  }
  throw new Error(`level ${num}: no board`);
}