/**
 * Deterministic human-technique grader, version 1.
 * This describes one reproducible logical solve path, not a universal difficulty
 * score. It never guesses; puzzles that need an unsupported technique are rejected.
 */
export type RatedDifficulty = "easy" | "medium" | "hard" | "expert";
export type PuzzleTechnique = "naked-single" | "hidden-single" | "locked-candidates" | "naked-pair" | "hidden-pair";

export const PUZZLE_TECHNIQUES: readonly PuzzleTechnique[] = [
  "naked-single", "hidden-single", "locked-candidates", "naked-pair", "hidden-pair",
];

export interface PuzzleRating {
  difficulty: RatedDifficulty;
  hardestTechnique: PuzzleTechnique;
  /** Placements for singles; productive elimination passes for other techniques. */
  steps: Record<PuzzleTechnique, number>;
  clues: number;
}

export type PuzzleRatingResult =
  | { status: "invalid" | "stalled" }
  | { status: "solved"; solution: number[]; rating: PuzzleRating };

export interface CellDigit { cell: number; digit: number }
export interface LogicalPosition { values: number[]; candidates: number[][] }
export interface TechniqueStep {
  technique: PuzzleTechnique;
  variant: "pointing" | "claiming" | null;
  supportCells: number[];
  units: number[][];
  digits: number[];
  placements: CellDigit[];
  eliminations: CellDigit[];
  before: LogicalPosition;
  after: LogicalPosition;
}

export const TRACE_VERSION = "v1-first-supported-2026-09-06";

const ALL = 0b1111111110;
const ROWS = Array.from({ length: 9 }, (_, row) => Array.from({ length: 9 }, (_, column) => row * 9 + column));
const COLUMNS = Array.from({ length: 9 }, (_, column) => Array.from({ length: 9 }, (_, row) => row * 9 + column));
const BOXES = Array.from({ length: 9 }, (_, box) => Array.from({ length: 9 }, (_, cell) =>
  (Math.floor(box / 3) * 3 + Math.floor(cell / 3)) * 9 + (box % 3) * 3 + cell % 3));
const UNITS = [...ROWS, ...COLUMNS, ...BOXES];
const BOX_OF = Array.from({ length: 81 }, (_, index) => Math.floor(index / 27) * 3 + Math.floor((index % 9) / 3));
const PEERS = Array.from({ length: 81 }, (_, index) => [...new Set([
  ...ROWS[Math.floor(index / 9)], ...COLUMNS[index % 9], ...BOXES[BOX_OF[index]],
])].filter((peer) => peer !== index));

function bitCount(mask: number) {
  let count = 0;
  for (let rest = mask; rest; rest &= rest - 1) count += 1;
  return count;
}

export function ratePuzzle(puzzle: string, onStep?: (step: TechniqueStep) => void): PuzzleRatingResult {
  if (!/^[0-9]{81}$/.test(puzzle)) return { status: "invalid" };
  const values = [...puzzle].map(Number);
  for (const unit of UNITS) {
    let used = 0;
    for (const index of unit) {
      if (values[index] === 0) continue;
      const bit = 1 << values[index];
      if (used & bit) return { status: "invalid" };
      used |= bit;
    }
  }
  const candidates = values.map((value, index) => value ? 0 : PEERS[index].reduce(
    (mask, peer) => mask & ~(1 << values[peer]), ALL,
  ));
  const steps: Record<PuzzleTechnique, number> = {
    "naked-single": 0, "hidden-single": 0, "locked-candidates": 0, "naked-pair": 0, "hidden-pair": 0,
  };
  const clues = values.filter(Boolean).length;
  const digitsOf = (mask: number) => Array.from({ length: 9 }, (_, i) => i + 1).filter((digit) => mask & (1 << digit));
  const snapshot = (): LogicalPosition => ({ values: [...values], candidates: candidates.map(digitsOf) });
  let evidence: Pick<TechniqueStep, "supportCells" | "units" | "digits" | "variant"> = { supportCells: [], units: [], digits: [], variant: null };
  let placements: CellDigit[] = [];
  let eliminations: CellDigit[] = [];

  function assign(index: number, bit: number) {
    if (onStep) placements.push({ cell: index, digit: Math.log2(bit) });
    values[index] = Math.log2(bit);
    candidates[index] = 0;
    for (const peer of PEERS[index]) candidates[peer] &= ~bit;
  }

  function eliminate(indexes: readonly number[], mask: number, reason: typeof evidence) {
    let changed = false;
    for (const index of indexes) {
      if (candidates[index] & mask) {
        if (onStep) {
          evidence = reason;
          eliminations.push(...digitsOf(candidates[index] & mask).map((digit) => ({ cell: index, digit })));
        }
        candidates[index] &= ~mask;
        changed = true;
      }
    }
    return changed;
  }

  function nakedSingle() {
    for (let index = 0; index < 81; index += 1) {
      const mask = candidates[index];
      if (mask && (mask & (mask - 1)) === 0) {
        if (onStep) evidence = { supportCells: [index], units: [], digits: digitsOf(mask), variant: null };
        assign(index, mask);
        return true;
      }
    }
    return false;
  }

  function hiddenSingle() {
    for (const unit of UNITS) {
      for (let digit = 1; digit <= 9; digit += 1) {
        const bit = 1 << digit;
        const positions = unit.filter((index) => candidates[index] & bit);
        if (positions.length === 1) {
          if (onStep) evidence = { supportCells: positions, units: [unit], digits: [digit], variant: null };
          assign(positions[0], bit);
          return true;
        }
      }
    }
    return false;
  }

  function lockedCandidates() {
    // Pointing: all candidates in a box occupy a single row or column.
    for (let box = 0; box < 9; box += 1) {
      for (let digit = 1; digit <= 9; digit += 1) {
        const bit = 1 << digit;
        const positions = BOXES[box].filter((index) => candidates[index] & bit);
        if (positions.length < 2) continue;
        const row = Math.floor(positions[0] / 9);
        const column = positions[0] % 9;
        if (positions.every((index) => Math.floor(index / 9) === row)
          && eliminate(ROWS[row].filter((index) => BOX_OF[index] !== box), bit, { supportCells: positions, units: [BOXES[box], ROWS[row]], digits: [digit], variant: "pointing" })) return true;
        if (positions.every((index) => index % 9 === column)
          && eliminate(COLUMNS[column].filter((index) => BOX_OF[index] !== box), bit, { supportCells: positions, units: [BOXES[box], COLUMNS[column]], digits: [digit], variant: "pointing" })) return true;
      }
    }
    // Claiming: all candidates in a row or column occupy one box.
    for (const unit of [...ROWS, ...COLUMNS]) {
      for (let digit = 1; digit <= 9; digit += 1) {
        const bit = 1 << digit;
        const positions = unit.filter((index) => candidates[index] & bit);
        if (positions.length < 2) continue;
        const box = BOX_OF[positions[0]];
        if (positions.every((index) => BOX_OF[index] === box)
          && eliminate(BOXES[box].filter((index) => !unit.includes(index)), bit, { supportCells: positions, units: [unit, BOXES[box]], digits: [digit], variant: "claiming" })) return true;
      }
    }
    return false;
  }

  function nakedPair() {
    for (const unit of UNITS) {
      for (const index of unit) {
        const mask = candidates[index];
        if (bitCount(mask) !== 2) continue;
        const positions = unit.filter((other) => candidates[other] === mask);
        if (positions.length === 2 && eliminate(unit.filter((other) => !positions.includes(other)), mask, { supportCells: positions, units: [unit], digits: digitsOf(mask), variant: null })) return true;
      }
    }
    return false;
  }

  function hiddenPair() {
    for (const unit of UNITS) {
      for (let first = 1; first < 9; first += 1) {
        const positions = unit.filter((index) => candidates[index] & (1 << first));
        if (positions.length !== 2) continue;
        for (let second = first + 1; second <= 9; second += 1) {
          const otherPositions = unit.filter((index) => candidates[index] & (1 << second));
          if (otherPositions.length !== 2 || positions[0] !== otherPositions[0] || positions[1] !== otherPositions[1]) continue;
          if (eliminate(positions, ALL & ~((1 << first) | (1 << second)), { supportCells: positions, units: [unit], digits: [first, second], variant: null })) return true;
        }
      }
    }
    return false;
  }

  const techniques: [PuzzleTechnique, () => boolean][] = [
    ["naked-single", nakedSingle], ["hidden-single", hiddenSingle],
    ["locked-candidates", lockedCandidates], ["naked-pair", nakedPair], ["hidden-pair", hiddenPair],
  ];
  while (values.some((value) => value === 0)) {
    if (values.some((value, index) => value === 0 && candidates[index] === 0)) return { status: "invalid" };
    let progressed = false;
    for (const [technique, apply] of techniques) {
      const before = onStep ? snapshot() : null;
      if (onStep) { placements = []; eliminations = []; }
      if (!apply()) continue;
      if (onStep && before) onStep({
        technique, ...evidence,
        supportCells: [...evidence.supportCells], units: evidence.units.map((unit) => [...unit]), digits: [...evidence.digits],
        placements, eliminations, before, after: snapshot(),
      });
      steps[technique] += 1;
      progressed = true;
      break;
    }
    if (!progressed) return { status: "stalled" };
  }
  // Validate the result independently of the candidate eliminations.
  if (UNITS.some((unit) => unit.reduce((mask, index) => mask | (1 << values[index]), 0) !== ALL)) return { status: "invalid" };
  const hardestTechnique = [...PUZZLE_TECHNIQUES].reverse().find((technique) => steps[technique] > 0) ?? "naked-single";
  const difficulty: RatedDifficulty = hardestTechnique === "naked-single" ? "easy"
    : hardestTechnique === "hidden-single" ? "medium"
      : hardestTechnique === "locked-candidates" ? "hard" : "expert";
  return { status: "solved", solution: values, rating: { difficulty, hardestTechnique, steps, clues } };
}

/** Observe the existing deterministic path; no new solving rules or grading order. */
export function tracePuzzle(puzzle: string) {
  const steps: TechniqueStep[] = [];
  const result = ratePuzzle(puzzle, (step) => steps.push(step));
  return { result, steps };
}