fertig-classic-games/server/words/wordLadderEngine.js

// Server-side Word Ladder dictionary + puzzle generator + skill-based AI.
//
// Word Ladder: transform a START word into a TARGET word by changing exactly one
// letter at a time, where every intermediate rung is a real word of the same
// length (COLD → CORD → CARD → WARD → WARM).
//
// The word graph (one node per word, an edge between words differing in exactly
// one position) is implicit: neighbours are generated on demand by trying all 25
// substitutions at each position and testing membership in a Set. The graphs are
// small (a few thousand 3/4-letter words), so BFS over them is cheap.

const LENGTHS = [3, 4];
const A = 'A'.charCodeAt(0);

// Optimal-path length ranges that make a satisfying puzzle, per word length.
const PAR_RANGE = {
  3: [3, 5],
  4: [4, 6],
};

// Skill profiles for the AI opponent. `wander` = chance of stepping onto a
// non-progress neighbour (a detour it must later recover from). `delay` =
// "thinking" time [lo, hi] ms before each rung (pacing, not intelligence).
const SKILL = {
  1: { wander: 0.70, delay: [9000, 15000] },
  2: { wander: 0.55, delay: [7000, 11000] },
  3: { wander: 0.42, delay: [5000, 8000] },
  4: { wander: 0.28, delay: [3500, 6000] },
  5: { wander: 0.15, delay: [2500, 4500] },
};

const wordSets = {};   // length → Set<string>
const wordArrays = {}; // length → string[]

export function initWordLadderDictionary(words3, words4) {
  setFor(3, words3);
  setFor(4, words4);
}

function setFor(length, words) {
  const arr = (words ?? []).map(w => String(w).toUpperCase()).filter(w => w.length === length);
  wordSets[length] = new Set(arr);
  wordArrays[length] = [...wordSets[length]];
}

export function dictionaryReady() {
  return LENGTHS.every(L => wordArrays[L]?.length > 0);
}

// ── Graph ──────────────────────────────────────────────────────────────────────

// Valid words differing from `word` in exactly one position.
export function neighbors(word) {
  const W = String(word).toUpperCase();
  const set = wordSets[W.length];
  if (!set) return [];
  const out = [];
  for (let i = 0; i < W.length; i++) {
    const before = W.slice(0, i);
    const after = W.slice(i + 1);
    const orig = W[i];
    for (let c = 0; c < 26; c++) {
      const ch = String.fromCharCode(A + c);
      if (ch === orig) continue;
      const cand = before + ch + after;
      if (set.has(cand)) out.push(cand);
    }
  }
  return out;
}

// BFS from `start`; returns Map<word, distance> over the connected component.
// `maxDepth` (optional) bounds the search for puzzle generation.
function bfsDistances(start, maxDepth = Infinity) {
  const dist = new Map([[start, 0]]);
  const queue = [start];
  let i = 0;
  while (i < queue.length) {
    const w = queue[i++];
    const d = dist.get(w);
    if (d >= maxDepth) continue;
    for (const n of neighbors(w)) {
      if (!dist.has(n)) {
        dist.set(n, d + 1);
        queue.push(n);
      }
    }
  }
  return dist;
}

// Shortest path between two words (inclusive of both ends), or null.
export function shortestPath(from, to) {
  const start = String(from).toUpperCase();
  const goal = String(to).toUpperCase();
  if (start === goal) return [start];
  if (start.length !== goal.length) return null;

  const prev = new Map([[start, null]]);
  const queue = [start];
  let i = 0;
  while (i < queue.length) {
    const w = queue[i++];
    for (const n of neighbors(w)) {
      if (prev.has(n)) continue;
      prev.set(n, w);
      if (n === goal) {
        const path = [];
        for (let cur = goal; cur !== null; cur = prev.get(cur)) path.unshift(cur);
        return path;
      }
      queue.push(n);
    }
  }
  return null;
}

// ── Puzzle generation ────────────────────────────────────────────────────────

// Build a puzzle whose optimal solution is exactly `par` steps. Retries with
// fresh random starts; relaxes to the deepest reachable target if `par` proves
// hard to hit for the chosen start.
function generatePuzzleWithPar(length, par, attempts = 300) {
  const pool = wordArrays[length] ?? [];
  if (pool.length === 0) return null;

  for (let a = 0; a < attempts; a++) {
    const start = randomFrom(pool);
    const dist = bfsDistances(start, par);
    const exact = [];
    let deepest = null, deepestD = 0;
    for (const [word, d] of dist) {
      if (word === start) continue;
      if (d === par) exact.push(word);
      if (d > deepestD) { deepest = word; deepestD = d; }
    }
    if (exact.length > 0) {
      const target = randomFrom(exact);
      return { start, target, par };
    }
    // Last few attempts: accept the deepest target we can reach (>= 2 steps).
    if (a >= attempts - 5 && deepest && deepestD >= 2) {
      return { start, target: deepest, par: deepestD };
    }
  }
  return null;
}

function pickPar(length) {
  const [lo, hi] = PAR_RANGE[length] ?? [3, 5];
  return lo + Math.floor(Math.random() * (hi - lo + 1));
}

// Single puzzle (solo mode).
export function generatePuzzle(length) {
  const L = LENGTHS.includes(length) ? length : 4;
  return generatePuzzleWithPar(L, pickPar(L)) ?? fallbackPuzzle(L);
}

// Two distinct puzzles of equal par (versus mode — fair race).
export function generateVersusPuzzles(length) {
  const L = LENGTHS.includes(length) ? length : 4;
  const par = pickPar(L);
  const player = generatePuzzleWithPar(L, par) ?? fallbackPuzzle(L);
  let opponent = null;
  for (let a = 0; a < 20; a++) {
    const cand = generatePuzzleWithPar(L, player.par);
    if (cand && cand.start !== player.start && cand.target !== player.target) {
      opponent = cand;
      break;
    }
  }
  return { player, opponent: opponent ?? generatePuzzleWithPar(L, player.par) ?? fallbackPuzzle(L) };
}

// Degenerate safety net: a start word and one neighbour (par 1). Only reached if
// the dictionary is empty/broken.
function fallbackPuzzle(length) {
  const pool = wordArrays[length] ?? [];
  const start = pool[0] ?? 'CATS'.slice(0, length);
  const ns = neighbors(start);
  return { start, target: ns[0] ?? start, par: ns.length ? 1 : 0 };
}

// ── AI opponent ────────────────────────────────────────────────────────────────

function profileFor(skill) {
  return SKILL[Math.max(1, Math.min(5, skill | 0))] ?? SKILL[3];
}

// Advance the AI one rung from `current` toward `target`. Skill sets both pace
// (delayMs) and accuracy (chance of a detour that lengthens its path).
export function chooseAIMove(current, target, skill) {
  const cur = String(current).toUpperCase();
  const goal = String(target).toUpperCase();
  if (cur === goal) return { word: cur, delayMs: 0, done: true };

  const profile = profileFor(skill);
  const ns = neighbors(cur);
  if (ns.length === 0) return { word: cur, delayMs: 0, done: false };

  // Distances to the goal, so we know which neighbours make progress.
  const dist = bfsDistances(goal);
  const d = dist.get(cur);
  const progress = ns.filter(n => dist.get(n) === d - 1);
  const detour = ns.filter(n => dist.get(n) !== d - 1);

  let word;
  if (detour.length > 0 && Math.random() < profile.wander) {
    word = randomFrom(detour);
  } else if (progress.length > 0) {
    word = randomFrom(progress);
  } else {
    word = randomFrom(ns);
  }

  const [lo, hi] = profile.delay;
  const delayMs = Math.round(lo + Math.random() * (hi - lo));
  return { word, delayMs, done: word === goal };
}

// ── Hint ─────────────────────────────────────────────────────────────────────

// The next word on a shortest path from `current` to `target`.
export function hintMove(current, target) {
  const path = shortestPath(current, target);
  return path && path.length > 1 ? path[1] : null;
}

// ── Misc ───────────────────────────────────────────────────────────────────────

export function validWordsOfLength(length) {
  return [...(wordArrays[length] ?? [])];
}

function randomFrom(arr) {
  return arr[Math.floor(Math.random() * arr.length)];
}