/**
 * Crossword Grid Generator
 *
 * Pure, deterministic backtracking crossword matrix algorithm.
 *
 *   generateGrid(clues)
 *     -> { rows, cols, cells, placements, word_count }
 *
 *   validateAnswer(grid, placements, userGridState)
 *     -> { correctCount, totalCount, isComplete, perClue: [{ id, isCorrect, ... }] }
 *
 * Design notes
 * ------------
 * 1. Clues are normalized to UPPERCASE letters; non-letters are stripped. This means
 *    "E-mail" and "IBM Corp." are accepted but spaces/punctuation never participate in
 *    matching.
 * 2. Placement tries *intersection first* (most words pack tightly) then falls back to
 *    a fresh row/column (grid expansion). For a fresh placement we try all four edges
 *    of the existing bounding box to keep the grid compact.
 * 3. Backtracking: when a clue cannot be placed, we restart from scratch with the
 *    clue order shuffled. The MAX_ATTEMPTS bound (default 20) caps the worst case so
 *    a hopeless input fails loudly instead of hanging.
 * 4. clue_number is assigned in reading order (top-to-bottom, left-to-right), matching
 *    the convention used by printed crosswords: a cell that starts an across word is
 *    numbered first; if a cell also starts a down word it shares the same number.
 *
 * The grid is serialized as:
 *   cells: [{ row, col, letter, clue_ids: [number,...], is_block: false }]
 *   placements: [{ clue_id, clue_text, answer, direction, start_row, start_col, clue_number }]
 */

'use strict';

const MAX_ATTEMPTS = 20;
const DEFAULT_PADDING = 1;       // empty cell padding between disjoint words on a fresh row/col
const MAX_GRID_SIZE = 30;        // safety cap to prevent runaway growth

/**
 * Normalize an answer: uppercase ASCII letters only. Strips diacritics-ish via
 * the trivial NFKD pass; characters outside [A-Z] are dropped.
 */
function normalizeAnswer(raw) {
  if (raw === null || raw === undefined) return '';
  const s = String(raw);
  // Drop everything that isn't a letter, then uppercase.
  // ASCII only — we're building a school-grade crossword, not a Unicode one.
  return s.replace(/[^A-Za-z]/g, '').toUpperCase();
}

/**
 * Seeded PRNG (mulberry32) for reproducible shuffles. We don't *need* it to be
 * deterministic for production, but it makes debugging and the smoke test easier.
 */
function makeRng(seed) {
  let a = seed >>> 0;
  return function () {
    a = (a + 0x6D2B79F5) >>> 0;
    let t = a;
    t = Math.imul(t ^ (t >>> 15), t | 1);
    t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

function shuffle(arr, rng) {
  const out = arr.slice();
  for (let i = out.length - 1; i > 0; i--) {
    const j = Math.floor(rng() * (i + 1));
    [out[i], out[j]] = [out[j], out[i]];
  }
  return out;
}

/**
 * Compute the bounding box (min/max row/col) of the existing letters.
 * Used when picking a "fresh" anchor for an unintersecting word.
 */
function boundingBox(letters) {
  if (letters.size === 0) return null;
  let minR = Infinity, minC = Infinity, maxR = -Infinity, maxC = -Infinity;
  for (const k of letters.keys()) {
    const [r, c] = k.split(',').map(Number);
    if (r < minR) minR = r;
    if (c < minC) minC = c;
    if (r > maxR) maxR = r;
    if (c > maxC) maxC = c;
  }
  return { minR, minC, maxR, maxC };
}

/**
 * Try every intersection with existing placed words. Returns the first matching
 * (row, col) that satisfies the crossword constraints (no orphan side-letters,
 * no collision on a non-matching letter) or null if nothing fits.
 *
 * direction: 'across' (horizontal) or 'down' (vertical)
 * Existing letters: Map<"r,c", "L">
 */
function findIntersection(answer, direction, letters) {
  if (letters.size === 0) return null;

  for (const [key, existingLetter] of letters) {
    const [r, c] = key.split(',').map(Number);
    for (let i = 0; i < answer.length; i++) {
      if (answer[i] !== existingLetter) continue;
      // For 'across', the letter is at column c — start_col = c - i, start_row = r
      // For 'down',   the letter is at row    r — start_row = r - i, start_col = c
      const startR = direction === 'across' ? r : r - i;
      const startC = direction === 'across' ? c - i : c;
      const placement = tryPlace(answer, direction, startR, startC, letters);
      if (placement) return placement;
    }
  }
  return null;
}

/**
 * Check whether placing `answer` at (startR, startC) in `direction` is legal.
 * Returns { startRow, startCol } if legal, else null.
 *
 * Rules:
 *   - Every cell the word occupies must either be empty or match the existing letter.
 *   - The cell immediately before the word (in the writing direction) must be empty
 *     or out of bounds — prevents accidental concatenation ("CATCHATCH").
 *   - The cell immediately after the word must be empty or out of bounds.
 *   - For each cell the word occupies, the perpendicular neighbours (one cell out
 *     on either side) must be empty — prevents side-touches ("AT" sticking out the
 *     side of a longer across word).
 *   - The word must fit inside MAX_GRID_SIZE bounds.
 */
function tryPlace(answer, direction, startR, startC, letters) {
  const len = answer.length;
  if (startR < 0 || startC < 0) return null;
  if (direction === 'across' && startC + len > MAX_GRID_SIZE) return null;
  if (direction === 'down'   && startR + len > MAX_GRID_SIZE) return null;

  // Letter-matches + checks the perpendicular side-touch rule.
  for (let i = 0; i < len; i++) {
    const r = direction === 'across' ? startR     : startR + i;
    const c = direction === 'across' ? startC + i : startC;
    const key = `${r},${c}`;
    const existing = letters.get(key);

    if (existing && existing !== answer[i]) return null; // letter collision
    if (!existing) {
      // Perpendicular neighbours must be empty (no side-touch into another word).
      const perpR = direction === 'across' ? r - 1 : r;
      const perpR2 = direction === 'across' ? r + 1 : r;
      const perpC = direction === 'across' ? c : c - 1;
      const perpC2 = direction === 'across' ? c : c + 1;
      // The perpendicular neighbour directly on each side must be empty.
      // We do NOT check the corner cells (r-1,c-1) etc — those are allowed.
      const beforeKey = `${perpR},${perpC}`;
      const afterKey  = `${perpR2},${perpC2}`;
      if (letters.has(beforeKey) || letters.has(afterKey)) return null;
    }
  }

  // Before-cell: must be empty/out-of-bounds.
  const beforeR = direction === 'across' ? startR     : startR - 1;
  const beforeC = direction === 'across' ? startC - 1 : startC;
  if (beforeR >= 0 && beforeC >= 0 && letters.has(`${beforeR},${beforeC}`)) return null;

  // After-cell: must be empty/out-of-bounds.
  const afterR = direction === 'across' ? startR         : startR + len;
  const afterC = direction === 'across' ? startC + len   : startC;
  if (afterR >= 0 && afterC >= 0 && letters.has(`${afterR},${afterC}`)) return null;

  return { startRow: startR, startCol: startC };
}

/**
 * Try to find a placement that doesn't intersect any existing letter — used as
 * the fallback when no intersection fits. We try the four "edges" of the current
 * bounding box (top, bottom, left, right) with a small padding gap so disjoint
 * words don't touch.
 */
function findFreshPlacement(answer, direction, letters, box) {
  const len = answer.length;

  // Candidate anchors. We let each direction try both horizontal and vertical
  // placements — a disjoint word could go in any direction as long as the
  // perpendicular-side rule is satisfied.
  const candidates = [];

  if (box) {
    // Place horizontally above the box, intersecting its top edge
    if (direction === 'across') {
      for (let c = box.minC - len - DEFAULT_PADDING; c <= box.maxC + DEFAULT_PADDING; c++) {
        candidates.push({ r: box.minR - DEFAULT_PADDING - 1, c });
      }
      // Place horizontally below the box
      for (let c = box.minC - len - DEFAULT_PADDING; c <= box.maxC + DEFAULT_PADDING; c++) {
        candidates.push({ r: box.maxR + DEFAULT_PADDING + 1, c });
      }
    } else {
      // Place vertically to the left of the box
      for (let r = box.minR - len - DEFAULT_PADDING; r <= box.maxR + DEFAULT_PADDING; r++) {
        candidates.push({ r, c: box.minC - DEFAULT_PADDING - 1 });
      }
      // Place vertically to the right of the box
      for (let r = box.minR - len - DEFAULT_PADDING; r <= box.maxR + DEFAULT_PADDING; r++) {
        candidates.push({ r, c: box.maxC + DEFAULT_PADDING + 1 });
      }
    }
  } else {
    // First word ever: only one valid placement, (0,0).
    candidates.push({ r: 0, c: 0 });
  }

  for (const { r, c } of candidates) {
    const placement = tryPlace(answer, direction, r, c, letters);
    if (placement) return placement;
  }
  return null;
}

/**
 * Place a word at the given coordinates, populating the `letters` map.
 * Returns the new set of occupied cells for this word.
 */
function commitPlacement(answer, direction, startRow, startCol, letters) {
  const cells = [];
  for (let i = 0; i < answer.length; i++) {
    const r = direction === 'across' ? startRow         : startRow + i;
    const c = direction === 'across' ? startCol + i     : startCol;
    const key = `${r},${c}`;
    letters.set(key, answer[i]);
    cells.push(key);
  }
  return cells;
}

/**
 * Compute clue numbers in reading order (top-to-bottom, left-to-right).
 * A cell gets a number if it starts an across or down word. The number is the
 * ordinal of the first such cell in scan order.
 */
function assignClueNumbers(placements, letters) {
  // Collect every cell that starts a word.
  const starters = new Map(); // key -> [clue_id, ...]
  for (const p of placements) {
    const key = `${p.start_row},${p.start_col}`;
    if (!starters.has(key)) starters.set(key, []);
    starters.get(key).push(p.clue_id);
  }
  // Scan the grid in row-major order and assign 1..N to each starter cell.
  let n = 1;
  const numberByKey = new Map();
  const sortedKeys = [...starters.keys()].sort((a, b) => {
    const [ra, ca] = a.split(',').map(Number);
    const [rb, cb] = b.split(',').map(Number);
    return ra - rb || ca - cb;
  });
  for (const k of sortedKeys) numberByKey.set(k, n++);
  // Stamp each placement with its clue_number.
  for (const p of placements) {
    p.clue_number = numberByKey.get(`${p.start_row},${p.start_col}`);
  }
  return numberByKey;
}

/**
 * Serialize the final grid into the { rows, cols, cells } shape we persist.
 */
function serializeGrid(letters, numberByKey, placements = []) {
  const box = boundingBox(letters);
  if (!box) return { rows: 0, cols: 0, cells: [] };

  const rows = box.maxR - box.minR + 1;
  const cols = box.maxC - box.minC + 1;
  const cells = [];

  // Map of "r,c" -> Array of clue_ids
  const clueIdsMap = new Map();
  for (const p of placements) {
    for (let i = 0; i < p.answer.length; i++) {
      const r = p.direction === 'down' ? p.start_row + i : p.start_row;
      const c = p.direction === 'across' ? p.start_col + i : p.start_col;
      const key = `${r},${c}`;
      if (!clueIdsMap.has(key)) {
        clueIdsMap.set(key, []);
      }
      clueIdsMap.get(key).push(p.clue_id);
    }
  }

  for (const [key, letter] of letters) {
    const [r, c] = key.split(',').map(Number);
    const relR = r - box.minR;
    const relC = c - box.minC;
    cells.push({
      row: relR,
      col: relC,
      letter,
      clue_number: numberByKey.get(key) || null,
      clue_ids: clueIdsMap.get(key) || [],
      is_block: false,
    });
  }

  // Sort for stable output (handy for snapshots/tests).
  cells.sort((a, b) => a.row - b.row || a.col - b.col);

  return { rows, cols, cells };
}

/**
 * Compute difficulty from word_count (cached on the game record for filtering).
 *   easy  : < 5 words
 *   medium: 5..10
 *   hard  : > 10
 */
function computeDifficulty(wordCount) {
  if (wordCount < 5) return 'easy';
  if (wordCount <= 10) return 'medium';
  return 'hard';
}

/**
 * Try to lay out all clues in one pass. Returns placements or null on failure.
 */
function attemptLayout(normalizedClues) {
  const letters = new Map();
  const placements = [];
  // IMPORTANT: do NOT shadow `c.idx` here. `c.idx` was baked in at normalize
  // time as the ORIGINAL input-array index. A map-callback parameter named
  // `idx` would shadow-overwrite it with the SORTED position, which made
  // placements[*].clue_id point at the wrong input row. Just spread.
  const cluesWithIds = normalizedClues.map((c) => ({ ...c }));

  // Place the first (longest) clue at (0,0) going across by convention.
  const first = cluesWithIds[0];
  const firstAnswer = first.answer;
  const firstDir = first.direction || 'across';
  const firstPlace = tryPlace(firstAnswer, firstDir, 0, 0, letters);
  if (!firstPlace) {
    // First word must fit at (0,0); if not, this clue set is unusable.
    return null;
  }
  commitPlacement(firstAnswer, firstDir, 0, 0, letters);
  placements.push({
    clue_id: first.idx,
    clue_text: first.clue_text,
    answer: firstAnswer,
    direction: firstDir,
    start_row: 0,
    start_col: 0,
    clue_number: 0, // assigned later
  });

  // Now lay out the rest. Try intersections first, fresh placement second.
  for (let i = 1; i < cluesWithIds.length; i++) {
    const c = cluesWithIds[i];
    const dir = c.direction || 'across';
    let placement = findIntersection(c.answer, dir, letters);
    if (!placement) {
      const box = boundingBox(letters);
      placement = findFreshPlacement(c.answer, dir, letters, box);
    }
    if (!placement) return null;

    commitPlacement(c.answer, dir, placement.startRow, placement.startCol, letters);
    placements.push({
      clue_id: c.idx,
      clue_text: c.clue_text,
      answer: c.answer,
      direction: dir,
      start_row: placement.startRow,
      start_col: placement.startCol,
      clue_number: 0,
    });
  }

  // Re-base everything to (0,0) so the persisted grid is tight.
  const box = boundingBox(letters);
  for (const p of placements) {
    p.start_row -= box.minR;
    p.start_col -= box.minC;
  }
  const rebasedLetters = new Map();
  for (const [key, letter] of letters) {
    const [r, c] = key.split(',').map(Number);
    rebasedLetters.set(`${r - box.minR},${c - box.minC}`, letter);
  }

  const numberByKey = assignClueNumbers(placements, rebasedLetters);
  const grid = serializeGrid(rebasedLetters, numberByKey, placements);

  return { grid, placements, letters: rebasedLetters };
}

/**
 * Public entry point. Takes an array of clues:
 *   [{ clue_text, answer, direction: 'across'|'down' }, ...]
 *
 * Returns:
 *   { rows, cols, cells, placements, word_count, difficulty }
 *
 * Throws if the clues cannot be laid out after `MAX_ATTEMPTS` shuffles.
 */
function generateGrid(rawClues) {
  if (!Array.isArray(rawClues) || rawClues.length === 0) {
    throw new Error('generateGrid: at least one clue is required');
  }

  // Normalize answers and filter out empty clues.
  const normalized = rawClues
    .map((c, idx) => ({
      idx,
      clue_text: String(c.clue_text || '').trim(),
      answer: normalizeAnswer(c.answer),
      direction: (String(c.direction || 'across').toLowerCase() === 'down') ? 'down' : 'across',
    }))
    .filter((c) => c.answer.length >= 2); // single-letter "words" make the puzzle trivial and break the side-touch rule

  if (normalized.length === 0) {
    throw new Error('generateGrid: no clues have answers of length >= 2');
  }

  // Sort by length desc; longest first.
  normalized.sort((a, b) => b.answer.length - a.answer.length);

  // First try the natural (length-desc) order. If that fails, try shuffles.
  let result = attemptLayout(normalized);
  if (!result) {
    // Build a stable RNG so the same input is reproducible across runs.
    const seed = normalized.reduce((acc, c) => acc + c.answer.charCodeAt(0) + c.answer.length, 0) || 1;
    const rng = makeRng(seed);
    for (let attempt = 0; attempt < MAX_ATTEMPTS && !result; attempt++) {
      const order = shuffle(normalized, rng);
      result = attemptLayout(order);
    }
  }

  if (!result) {
    throw new Error(
      `generateGrid: failed to lay out ${normalized.length} clues after ${MAX_ATTEMPTS} attempts`
    );
  }

  const wordCount = result.placements.length;
  return {
    rows: result.grid.rows,
    cols: result.grid.cols,
    cells: result.grid.cells,
    placements: result.placements.map((p) => ({
      clue_id: p.clue_id,
      clue_text: p.clue_text,
      answer: p.answer,
      direction: p.direction,
      start_row: p.start_row,
      start_col: p.start_col,
      clue_number: p.clue_number,
    })),
    word_count: wordCount,
    difficulty: computeDifficulty(wordCount),
  };
}

/**
 * Validate a user's submitted grid state against the server-computed grid.
 *
 *   grid         : the persisted grid_layout from generateGrid()
 *   placements   : the per-clue placement array (same as grid.placements)
 *   userGridState: { "row,col": "letter", ... }
 *
 * Returns:
 *   { correctCount, totalCount, isComplete, perClue: [{ clue_id, clue_number, isCorrect, answer }] }
 */
function validateAnswer(grid, placements, userGridState) {
  const state = userGridState || {};
  const totalCount = placements.length;
  let correctCount = 0;
  const perClue = [];

  for (const p of placements) {
    let userWord = '';
    for (let i = 0; i < p.answer.length; i++) {
      const r = p.direction === 'across' ? p.start_row         : p.start_row + i;
      const c = p.direction === 'across' ? p.start_col + i     : p.start_col;
      const key = `${r},${c}`;
      const letter = state[key];
      userWord += letter ? String(letter).toUpperCase() : '';
    }
    const isCorrect = userWord === p.answer;
    if (isCorrect) correctCount++;
    perClue.push({
      clue_id: p.clue_id,
      clue_number: p.clue_number,
      direction: p.direction,
      user_answer: userWord,
      isCorrect,
    });
  }

  return {
    correctCount,
    totalCount,
    isComplete: correctCount === totalCount,
    perClue,
  };
}

module.exports = {
  generateGrid,
  validateAnswer,
  // Exported for tests / smoke harness:
  _internal: {
    normalizeAnswer,
    attemptLayout,
    computeDifficulty,
  },
};