Star Battle

/**
 * Everything the rules and the solvers need about a grid:
 *   n, k (stars per unit), rows, cols, regions (each a list of cells),
 *   units (rows, then columns, then regions), unitsOf (per cell, its row,
 *   column and region unit), regionOf (per cell), near (per cell, the up to
 *   eight cells touching it), kind (per unit: 'row', 'column' or 'region').
 */
export function shape(puzzle) {
  const { n, stars: k, regions: regionOf } = puzzle;
  const rows = [], cols = [], regions = Array.from({ length: n }, () => []);
  for (let r = 0; r < n; r++) {
    rows.push(Array.from({ length: n }, (_, c) => r * n + c));
    cols.push(Array.from({ length: n }, (_, c) => c * n + r));
  }
  for (let i = 0; i < n * n; i++) regions[regionOf[i]].push(i);
  const units = [...rows, ...cols, ...regions];
  const kind = units.map((_, u) => (u < n ? 'row' : u < 2 * n ? 'column' : 'region'));
  const unitsOf = Array.from({ length: n * n }, (_, i) => [Math.floor(i / n), n + (i % n), 2 * n + regionOf[i]]);
  const near = Array.from({ length: n * n }, (_, i) => {
    const r = Math.floor(i / n), c = i % n, out = [];
    for (let dr = -1; dr <= 1; dr++) for (let dc = -1; dc <= 1; dc++) {
      const rr = r + dr, cc = c + dc;
      if ((dr || dc) && rr >= 0 && cc >= 0 && rr < n && cc < n) out.push(rr * n + cc);
    }
    return out;
  });
  return { n, k, rows, cols, regions, units, kind, unitsOf, regionOf, near };
}

/**
 * Whether `answer` (a list of star cells) solves the puzzle: whole-number
 * cells on the grid, none twice, exactly `stars` in every row, column and
 * region, and no two touching. Any answer that does counts.
 */
export function check(puzzle, answer) {
  if (!wellFormed(puzzle) || !Array.isArray(answer)) return false;
  const { n, stars: k, regions } = puzzle;
  if (answer.length !== n * k || !answer.every(i => Number.isInteger(i) && i >= 0 && i < n * n)) return false;
  if (new Set(answer).size !== answer.length) return false;
  const row = new Array(n).fill(0), col = new Array(n).fill(0), reg = new Array(n).fill(0);
  for (const i of answer) { row[Math.floor(i / n)]++; col[i % n]++; reg[regions[i]]++; }
  if (![row, col, reg].every(counts => counts.every(c => c === k))) return false;
  for (const a of answer) for (const b of answer) if (a < b && touching(n, a, b)) return false;
  return true;
}

/**
 * The puzzle for a code:
 *   { engine, slug, code, size, difficulty, n, stars, regions: [n × n] },
 * as engine `version` made it (one of VERSIONS; the latest unless asked).
 * Throws if the code, size, difficulty or version isn't one the game makes.
 * `stats`, if given, is told how the making went (for tools/puzzles/):
 * attempts, the grids that reached one answer, how each of those rated, and
 * how many rated right but were too shallow.
 */
export function generate(code, size, difficulty = SIZES[Number(size)]?.difficulty, stats = {}, version = ENGINE_VERSION) {
  size = Number(size);
  version = Number(version);
  if (!Object.hasOwn(SIZES, size) || SIZES[size].difficulty !== difficulty || !CODE_RE.test(code) || !VERSIONS.includes(version)) throw new Error('Not a puzzle the game makes.');
  const { n, stars: k } = SIZES[size];
  const depth = version >= 2 ? DEPTH[difficulty] : 0;
  const r = stream(`${SLUG}|${version}|${size}|${difficulty}|${code}`);
  Object.assign(stats, { attempts: 0, failed: { stars: 0, regions: 0, nudge: 0 }, unique: 0, rated: {}, shallow: 0 });
  for (let attempt = 0; attempt < ATTEMPTS; attempt++) {
    stats.attempts++;
    const stars = layStars(r, n, k);
    if (!stars) { stats.failed.stars++; continue; }
    const regions = growRegions(r, n, k, stars, LEAN[k][difficulty]);
    if (!regions || !fair(n, regions)) { stats.failed.regions++; continue; }
    const puzzle = { engine: version, slug: SLUG, code, size, difficulty, n, stars: k, regions };
    if (!nudge(r, puzzle, stars) || !fair(n, puzzle.regions)) { stats.failed.nudge++; continue; }
    puzzle.regions = renumber(puzzle.regions);
    // (what solver.js's rate() says, with the steps it took)
    const got = solve(puzzle, 3);
    const rated = got.solved ? Object.keys(TIERS).find(name => TIERS[name] === got.tier) : null;
    stats.unique++;
    stats.rated[rated] = (stats.rated[rated] || 0) + 1;
    if (rated !== difficulty) continue;
    if (deep(got.used, TIERS[difficulty]) < depth) { stats.shallow++; continue; }
    return puzzle;
  }
  throw new Error(`No ${difficulty} ${n}×${n} puzzle came of ${code}.`);
}

// Grow blobs from seed cells until they fill the grid. `lean` (a whole
// number) lets big blobs grow faster, leaving some small regions, which are
// easy to read; 0 grows them evenly. Returns the blob of each cell.
function growBlobs(r, n, seeds, lean) {
  const owner = new Int16Array(n * n).fill(-1);
  const size = seeds.map(() => 1);
  seeds.forEach((cell, b) => { owner[cell] = b; });
  let left = n * n - seeds.length;
  while (left > 0) {
    // Each blob's open edge: unowned cells beside it.
    const edge = seeds.map(() => []);
    for (let i = 0; i < n * n; i++) {
      if (owner[i] >= 0) continue;
      for (const j of sides(n, i)) if (owner[j] >= 0) edge[owner[j]].push(i);
    }
    // Whole-number weights (size to the power `lean`), so every browser
    // picks the same blob: no fractional powers, which engines may round apart.
    const weights = size.map((s, b) => (edge[b].length ? s ** lean : 0));
    let x = r.int(weights.reduce((a, w) => a + w, 0)), b = 0;
    while ((x -= weights[b]) >= 0) b++;
    const cell = r.pick(edge[b]);
    owner[cell] = b;
    size[b]++;
    left--;
  }
  return owner;
}

// How lopsided regions grow, by stars and difficulty: lopsided grids leave
// small regions, which give easy starts. For one star it's the power of a
// blob's size its growth is weighted by; for two, how many times over the
// grid's cells to try handing one to a bigger region. Tuned so each
// difficulty's grids rate as asked often (tools/puzzles/check.mjs).
const LEAN = {
  1: { easy: 1, medium: 0, hard: 0 },
  2: { easy: 2, medium: 1, hard: 1 },
};

// Nudge region borders until `stars` is the only answer: find another
// answer, and hand one of its stars that isn't one of ours to a neighboring
// region, which breaks that answer and keeps ours. Returns whether it got there.
function nudge(r, puzzle, stars) {
  const { n, regions } = puzzle;
  const ours = new Set(stars);
  for (let k = 0; k < NUDGES; k++) {
    const found = count(puzzle, 2);
    if (found.count === 1) return true;
    const other = found.answers.find(a => a.some(i => !ours.has(i)));
    const moves = [];
    for (const c of other) {
      if (ours.has(c) || !stillWhole(n, regions, c)) continue;
      for (const j of sides(n, c)) if (regions[j] !== regions[c] && !moves.some(([cc, g]) => cc === c && g === regions[j])) moves.push([c, regions[j]]);
    }
    if (!moves.length) return false;
    const [c, g] = r.pick(moves);
    regions[c] = g;
  }
  return count(puzzle, 2).count === 1;
}

// Whether stars in these open cells would crowd out some row, column or
// region: their neighbors ruled out, and any unit they complete finished
// off, would leave a unit without room for the stars it still needs (too
// few open cells, or none that don't touch). One look, no chain of guesses.
function crowds(sh, s, stars) {
  const { k } = sh;
  const gone = new Set(stars);
  const added = new Map(); // unit → stars these add to it
  for (const i of stars) {
    for (const j of sh.near[i]) if (s.cell[j] === OPEN) gone.add(j);
    for (const u of sh.unitsOf[i]) added.set(u, (added.get(u) || 0) + 1);
  }
  for (const [u, more] of added) {
    const cells = sh.units[u];
    const have = cells.filter(j => s.cell[j] === STAR).length + more;
    if (have > k) return true;
    if (have === k) for (const j of cells) if (s.cell[j] === OPEN) gone.add(j);
  }
  const affected = new Set();
  for (const j of gone) for (const u of sh.unitsOf[j]) affected.add(u);
  for (const u of affected) {
    const cells = sh.units[u];
    const need = k - cells.filter(j => s.cell[j] === STAR).length - (added.get(u) || 0);
    if (need <= 0) continue;
    const open = cells.filter(j => s.cell[j] === OPEN && !gone.has(j));
    // ways() returns null past MAX_WAYS: too many to be crowded out.
    if (open.length < need || (need > 1 && ways(sh, open, need)?.length === 0)) return true;
  }
  return false;
}

// How many steps of its own tier a puzzle must need (from version 2), so a
// medium isn't an easy puzzle with a single medium step, nor a hard one a
// medium with one look ahead.
export const DEPTH = { easy: 0, medium: 3, hard: 2 };

KIND = Kind(
    slug="star-battle",
    title="Star Battle",
    engine_file="games/static/games/star-battle/engine/generate.js",
    # Boards say the stars a row holds, as the game does: "10×10 ★★".
    sizes={"6": "6×6 ★", "8": "8×8 ★", "10": "10×10 ★★"},
    # The bigger the grid, the deeper the reasoning: a size is a difficulty,
    # and a board is named by its size alone (docs/adr/0027).
    size_difficulty={"6": "easy", "8": "medium", "10": "hard"},
    daily=(("6", "easy"), ("8", "medium"), ("10", "hard")),
    # Roughly the time it takes just to place every star with the answer in
    # front of you: 6, 8 and 20 stars.
    min_seconds={"6": 6, "8": 10, "10": 20},
    clean=clean,
    wrong="Those stars don’t solve this puzzle.",
    since=date(2026, 10, 12),
)

def clean(answer, size):
    """An answer is the cells holding stars (row * n + column): whole
    numbers on the grid, none twice, n × stars of them. Written increasing."""
    n, stars = GRIDS[size]
    if not isinstance(answer, list) or len(answer) != n * stars:
        raise ValueError("not the right number of stars")
    # Exactly integers: not a bool (an int to Python), a fraction or text.
    if not all(type(i) is int and 0 <= i < n * n for i in answer) or len(set(answer)) != len(answer):
        raise ValueError("not cells of the grid")
    return sorted(answer)