import { createHash } from "node:crypto";

type TileType =
  | "straight"
  | "elbow"
  | "tee"
  | "cross"
  | "roundabout"
  | "decor"
  | "empty"
  | "blocked";

type Direction = "N" | "E" | "S" | "W";
type DecorKind = "dot" | "person" | "car" | "plane";
export type DifficultyKey = "easy" | "medium" | "hard" | "expert";

type Tile = {
  type: TileType;
  rot: number;
  locked: boolean;
  decor?: DecorKind;
};

export type Level = {
  id: number;
  name: string;
  difficulty: DifficultyKey;
  size: number;
  tiles: Tile[][];
  emptyPos: { x: number; y: number };
  startPos: { x: number; y: number };
  startDir: Direction;
  goalPos: { x: number; y: number };
  goalDir: Direction;
  moveLimit?: number;
  timeLimit?: number;
  solutionMoves?: Direction[];
};

type Pos = { x: number; y: number };

type TrackTier = {
  levels: number;
  size: number;
  blocked: number;
  pathMin: number;
  pathMax: number;
  scrambleMin: number;
  scrambleMax: number;
  moveMargin: number;
  extraLinksMin: number;
  extraLinksMax: number;
  minJunctions: number;
};

const decorKinds: DecorKind[] = ["dot", "person", "car", "plane"];

export const LEVELS_PER_DIFFICULTY = 240;
export const difficultyOrder: DifficultyKey[] = [
  "easy",
  "medium",
  "hard",
  "expert",
];

const getDayOfYear = (date: Date): number => {
  const start = new Date(date.getFullYear(), 0, 1);
  const diff =
    Date.UTC(date.getFullYear(), date.getMonth(), date.getDate()) -
    Date.UTC(start.getFullYear(), start.getMonth(), start.getDate());
  return Math.floor(diff / (1000 * 60 * 60 * 24));
};

const formatDateKey = (date: Date): string => {
  const year = date.getFullYear();
  const month = (date.getMonth() + 1).toString().padStart(2, "0");
  const day = date.getDate().toString().padStart(2, "0");
  return `${year}-${month}-${day}`;
};

export const difficultyLabels: Record<DifficultyKey, string> = {
  easy: "Facile",
  medium: "Moyen",
  hard: "Difficile",
  expert: "Mort subite",
};

const TRACKS: Record<DifficultyKey, TrackTier[]> = {
  easy: [
    {
      levels: 60,
      size: 3,
      blocked: 0,
      pathMin: 5,
      pathMax: 6,
      scrambleMin: 6,
      scrambleMax: 10,
      moveMargin: 6,
      extraLinksMin: 0,
      extraLinksMax: 0,
      minJunctions: 0,
    },
    {
      levels: 60,
      size: 4,
      blocked: 0,
      pathMin: 7,
      pathMax: 9,
      scrambleMin: 10,
      scrambleMax: 14,
      moveMargin: 7,
      extraLinksMin: 0,
      extraLinksMax: 0,
      minJunctions: 0,
    },
    {
      levels: 60,
      size: 4,
      blocked: 0,
      pathMin: 9,
      pathMax: 11,
      scrambleMin: 14,
      scrambleMax: 18,
      moveMargin: 8,
      extraLinksMin: 0,
      extraLinksMax: 0,
      minJunctions: 0,
    },
    {
      levels: 60,
      size: 4,
      blocked: 0,
      pathMin: 11,
      pathMax: 13,
      scrambleMin: 18,
      scrambleMax: 22,
      moveMargin: 9,
      extraLinksMin: 0,
      extraLinksMax: 0,
      minJunctions: 0,
    },
  ],
  medium: [
    {
      levels: 60,
      size: 4,
      blocked: 0,
      pathMin: 6,
      pathMax: 8,
      scrambleMin: 6,
      scrambleMax: 10,
      moveMargin: 8,
      extraLinksMin: 0,
      extraLinksMax: 1,
      minJunctions: 0,
    },
    {
      levels: 60,
      size: 4,
      blocked: 1,
      pathMin: 7,
      pathMax: 9,
      scrambleMin: 10,
      scrambleMax: 14,
      moveMargin: 8,
      extraLinksMin: 0,
      extraLinksMax: 1,
      minJunctions: 0,
    },
    {
      levels: 60,
      size: 5,
      blocked: 1,
      pathMin: 9,
      pathMax: 12,
      scrambleMin: 16,
      scrambleMax: 20,
      moveMargin: 8,
      extraLinksMin: 1,
      extraLinksMax: 2,
      minJunctions: 1,
    },
    {
      levels: 60,
      size: 5,
      blocked: 1,
      pathMin: 11,
      pathMax: 14,
      scrambleMin: 20,
      scrambleMax: 24,
      moveMargin: 8,
      extraLinksMin: 1,
      extraLinksMax: 3,
      minJunctions: 1,
    },
  ],
  hard: [
    {
      levels: 60,
      size: 5,
      blocked: 2,
      pathMin: 13,
      pathMax: 17,
      scrambleMin: 24,
      scrambleMax: 30,
      moveMargin: 7,
      extraLinksMin: 1,
      extraLinksMax: 3,
      minJunctions: 1,
    },
    {
      levels: 60,
      size: 6,
      blocked: 2,
      pathMin: 16,
      pathMax: 21,
      scrambleMin: 30,
      scrambleMax: 36,
      moveMargin: 7,
      extraLinksMin: 1,
      extraLinksMax: 3,
      minJunctions: 1,
    },
    {
      levels: 60,
      size: 6,
      blocked: 3,
      pathMin: 18,
      pathMax: 23,
      scrambleMin: 36,
      scrambleMax: 42,
      moveMargin: 7,
      extraLinksMin: 2,
      extraLinksMax: 4,
      minJunctions: 1,
    },
    {
      levels: 60,
      size: 6,
      blocked: 3,
      pathMin: 20,
      pathMax: 26,
      scrambleMin: 42,
      scrambleMax: 50,
      moveMargin: 8,
      extraLinksMin: 2,
      extraLinksMax: 4,
      minJunctions: 1,
    },
  ],
  expert: [
    {
      levels: 60,
      size: 4,
      blocked: 2,
      pathMin: 9,
      pathMax: 11,
      scrambleMin: 16,
      scrambleMax: 22,
      moveMargin: 3,
      extraLinksMin: 0,
      extraLinksMax: 1,
      minJunctions: 0,
    },
    {
      levels: 60,
      size: 5,
      blocked: 2,
      pathMin: 12,
      pathMax: 16,
      scrambleMin: 24,
      scrambleMax: 30,
      moveMargin: 3,
      extraLinksMin: 1,
      extraLinksMax: 3,
      minJunctions: 1,
    },
    {
      levels: 60,
      size: 6,
      blocked: 2,
      pathMin: 16,
      pathMax: 20,
      scrambleMin: 32,
      scrambleMax: 38,
      moveMargin: 2,
      extraLinksMin: 2,
      extraLinksMax: 4,
      minJunctions: 1,
    },
    {
      levels: 60,
      size: 6,
      blocked: 3,
      pathMin: 18,
      pathMax: 22,
      scrambleMin: 38,
      scrambleMax: 46,
      moveMargin: 2,
      extraLinksMin: 2,
      extraLinksMax: 5,
      minJunctions: 1,
    },
  ],
};

const makeDecor = (x: number, y: number): Tile => ({
  type: "decor",
  rot: (x + y) % 4,
  locked: false,
  decor: decorKinds[(x + y) % decorKinds.length],
});

const makeEmpty = (): Tile => ({
  type: "empty",
  rot: 0,
  locked: false,
});

const makeBlocked = (): Tile => ({
  type: "blocked",
  rot: 0,
  locked: true,
});

const dirOffsets: Record<Direction, Pos> = {
  N: { x: 0, y: -1 },
  E: { x: 1, y: 0 },
  S: { x: 0, y: 1 },
  W: { x: -1, y: 0 },
};

const opposite: Record<Direction, Direction> = {
  N: "S",
  S: "N",
  E: "W",
  W: "E",
};

const allDirections: Direction[] = ["N", "E", "S", "W"];

const mulberry32 = (seed: number) => {
  let t = seed >>> 0;
  return () => {
    t += 0x6d2b79f5;
    let r = Math.imul(t ^ (t >>> 15), 1 | t);
    r ^= r + Math.imul(r ^ (r >>> 7), 61 | r);
    return ((r ^ (r >>> 14)) >>> 0) / 4294967296;
  };
};

const randInt = (min: number, max: number, rand: () => number): number => {
  return Math.floor(rand() * (max - min + 1)) + min;
};

const shuffle = <T>(list: T[], rand: () => number): T[] => {
  const arr = list.slice();
  for (let i = arr.length - 1; i > 0; i -= 1) {
    const j = Math.floor(rand() * (i + 1));
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr;
};

const toKey = (pos: Pos): string => `${pos.x},${pos.y}`;

const manhattan = (a: Pos, b: Pos): number =>
  Math.abs(a.x - b.x) + Math.abs(a.y - b.y);

const directionBetween = (from: Pos, to: Pos): Direction => {
  if (to.x === from.x && to.y === from.y - 1) return "N";
  if (to.x === from.x && to.y === from.y + 1) return "S";
  if (to.x === from.x - 1 && to.y === from.y) return "W";
  if (to.x === from.x + 1 && to.y === from.y) return "E";
  throw new Error("Chemin invalide: positions non adjacentes.");
};

const normalizeKey = (a: Direction, b: Direction): string => {
  return [a, b].sort().join("");
};

const tileFromConnectors = (
  connectors: Direction[],
  rand: () => number,
  forceRoundabout = false,
): Tile => {
  const unique = Array.from(new Set(connectors));
  if (unique.length === 2) {
    const key = normalizeKey(unique[0], unique[1]);
    switch (key) {
      case "NS":
        return { type: "straight", rot: 0, locked: false };
      case "EW":
        return { type: "straight", rot: 1, locked: false };
      case "EN":
        return { type: "elbow", rot: 0, locked: false };
      case "ES":
        return { type: "elbow", rot: 1, locked: false };
      case "SW":
        return { type: "elbow", rot: 2, locked: false };
      case "NW":
        return { type: "elbow", rot: 3, locked: false };
      default:
        throw new Error("Connecteurs incompatibles pour un chemin simple.");
    }
  }

  if (unique.length === 3) {
    const set = new Set(unique);
    const missing = allDirections.find((dir) => !set.has(dir));
    let rot = 0;
    switch (missing) {
      case "S":
        rot = 0;
        break;
      case "W":
        rot = 1;
        break;
      case "N":
        rot = 2;
        break;
      case "E":
        rot = 3;
        break;
      default:
        rot = 0;
        break;
    }
    return { type: "tee", rot, locked: false };
  }

  if (unique.length === 4) {
    if (forceRoundabout) {
      return { type: "roundabout", rot: 0, locked: false };
    }
    const useRoundabout = rand() < 0.35;
    return {
      type: useRoundabout ? "roundabout" : "cross",
      rot: 0,
      locked: false,
    };
  }

  throw new Error("Connecteurs invalides pour une tuile.");
};

const addEdge = (edges: Map<string, Set<Direction>>, from: Pos, to: Pos) => {
  const dir = directionBetween(from, to);
  const fromKey = toKey(from);
  const toKeyValue = toKey(to);
  const fromSet = edges.get(fromKey) ?? new Set<Direction>();
  fromSet.add(dir);
  edges.set(fromKey, fromSet);
  const toSet = edges.get(toKeyValue) ?? new Set<Direction>();
  toSet.add(opposite[dir]);
  edges.set(toKeyValue, toSet);
};

const buildEdgesFromPath = (path: Pos[]) => {
  const edges = new Map<string, Set<Direction>>();
  for (let i = 0; i < path.length - 1; i += 1) {
    addEdge(edges, path[i], path[i + 1]);
  }
  return edges;
};

const getEdgeCandidates = (
  path: Pos[],
  pathSet: Set<string>,
  edges: Map<string, Set<Direction>>,
  size: number,
) => {
  const candidates: { from: Pos; to: Pos }[] = [];
  const seen = new Set<string>();

  for (const pos of path) {
    const fromKey = toKey(pos);
    const connected = edges.get(fromKey);
    for (const dir of allDirections) {
      const offset = dirOffsets[dir];
      const nx = pos.x + offset.x;
      const ny = pos.y + offset.y;
      if (nx < 0 || nx >= size || ny < 0 || ny >= size) {
        continue;
      }
      const neighborKey = `${nx},${ny}`;
      if (!pathSet.has(neighborKey)) {
        continue;
      }
      if (connected?.has(dir)) {
        continue;
      }
      const pairKey = [fromKey, neighborKey].sort().join("|");
      if (seen.has(pairKey)) {
        continue;
      }
      seen.add(pairKey);
      candidates.push({ from: pos, to: { x: nx, y: ny } });
    }
  }

  return candidates;
};

const addExtraEdges = (
  path: Pos[],
  pathSet: Set<string>,
  edges: Map<string, Set<Direction>>,
  size: number,
  count: number,
  rand: () => number,
) => {
  const candidates = getEdgeCandidates(path, pathSet, edges, size);
  let added = 0;

  while (added < count && candidates.length > 0) {
    const index = randInt(0, candidates.length - 1, rand);
    const [{ from, to }] = candidates.splice(index, 1);
    const fromDegree = edges.get(toKey(from))?.size ?? 0;
    const toDegree = edges.get(toKey(to))?.size ?? 0;
    if (fromDegree >= 4 || toDegree >= 4) {
      continue;
    }
    addEdge(edges, from, to);
    added += 1;
  }
};

const countJunctions = (
  path: Pos[],
  edges: Map<string, Set<Direction>>,
  startPos: Pos,
  goalPos: Pos,
) => {
  const startKey = toKey(startPos);
  const goalKey = toKey(goalPos);
  let junctions = 0;
  let crosses = 0;

  for (const pos of path) {
    const key = toKey(pos);
    let connectors = edges.get(key)?.size ?? 0;
    if (key === startKey) {
      connectors += 1;
    }
    if (key === goalKey) {
      connectors += 1;
    }
    if (connectors >= 3) {
      junctions += 1;
    }
    if (connectors === 4) {
      crosses += 1;
    }
  }

  return { junctions, crosses };
};

const getBorderCells = (size: number): { pos: Pos; dirs: Direction[] }[] => {
  const cells: { pos: Pos; dirs: Direction[] }[] = [];
  for (let y = 0; y < size; y += 1) {
    for (let x = 0; x < size; x += 1) {
      const dirs: Direction[] = [];
      if (y === 0) dirs.push("N");
      if (y === size - 1) dirs.push("S");
      if (x === 0) dirs.push("W");
      if (x === size - 1) dirs.push("E");
      if (dirs.length > 0) {
        cells.push({ pos: { x, y }, dirs });
      }
    }
  }
  return cells;
};

const selectStartGoal = (
  size: number,
  rand: () => number,
): { startPos: Pos; startDir: Direction; goalPos: Pos; goalDir: Direction } => {
  const border = getBorderCells(size);

  for (let attempt = 0; attempt < 80; attempt += 1) {
    const startCell = border[randInt(0, border.length - 1, rand)];
    const goalCell = border[randInt(0, border.length - 1, rand)];
    if (
      startCell.pos.x === goalCell.pos.x &&
      startCell.pos.y === goalCell.pos.y
    ) {
      continue;
    }

    const startDir =
      startCell.dirs[randInt(0, startCell.dirs.length - 1, rand)];
    const goalDir = goalCell.dirs[randInt(0, goalCell.dirs.length - 1, rand)];
    return {
      startPos: startCell.pos,
      startDir,
      goalPos: goalCell.pos,
      goalDir,
    };
  }

  throw new Error("Impossible de choisir un start/goal.");
};

const generatePath = (
  size: number,
  startPos: Pos,
  goalPos: Pos,
  length: number,
  rand: () => number,
): Pos[] | null => {
  const visited = new Set<string>();
  const path: Pos[] = [startPos];
  visited.add(toKey(startPos));

  const dfs = (current: Pos, stepsRemaining: number): boolean => {
    const dist = manhattan(current, goalPos);
    if (dist > stepsRemaining) {
      return false;
    }

    if (stepsRemaining === 0) {
      return current.x === goalPos.x && current.y === goalPos.y;
    }

    let neighbors = shuffle(
      (["N", "E", "S", "W"] as Direction[])
        .map((dir) => ({
          dir,
          pos: {
            x: current.x + dirOffsets[dir].x,
            y: current.y + dirOffsets[dir].y,
          },
        }))
        .filter(
          ({ pos }) => pos.x >= 0 && pos.x < size && pos.y >= 0 && pos.y < size,
        ),
      rand,
    );

    for (const next of neighbors) {
      const key = toKey(next.pos);
      if (visited.has(key)) {
        continue;
      }
      if (
        next.pos.x === goalPos.x &&
        next.pos.y === goalPos.y &&
        stepsRemaining > 1
      ) {
        continue;
      }

      visited.add(key);
      path.push(next.pos);
      if (dfs(next.pos, stepsRemaining - 1)) {
        return true;
      }
      path.pop();
      visited.delete(key);
    }

    return false;
  };

  if (dfs(startPos, length - 1)) {
    return path;
  }

  return null;
};

const placeBlocked = (
  size: number,
  path: Pos[],
  blockedCount: number,
  rand: () => number,
): Set<string> => {
  const blocked = new Set<string>();
  const pathSet = new Set(path.map(toKey));
  const candidates: Pos[] = [];

  for (let y = 0; y < size; y += 1) {
    for (let x = 0; x < size; x += 1) {
      const pos = { x, y };
      if (!pathSet.has(toKey(pos))) {
        candidates.push(pos);
      }
    }
  }

  const maxBlocks = Math.max(0, Math.min(blockedCount, candidates.length - 1));
  let pool = shuffle(candidates, rand);
  for (let i = 0; i < maxBlocks; i += 1) {
    blocked.add(toKey(pool[i]));
  }

  return blocked;
};

const scrambleTiles = (
  tiles: Tile[][],
  emptyPos: Pos,
  steps: number,
  rand: () => number,
): { emptyPos: Pos; moves: Direction[] } => {
  const size = tiles.length;
  const directions: Direction[] = ["N", "E", "S", "W"];
  let empty = { ...emptyPos };
  let prevDir: Direction | null = null;
  const moves: Direction[] = [];

  for (let i = 0; i < steps; i += 1) {
    let valid = directions.filter((dir) => {
      if (prevDir && opposite[prevDir] === dir) {
        return false;
      }
      const offset = dirOffsets[dir];
      const nx = empty.x + offset.x;
      const ny = empty.y + offset.y;
      if (nx < 0 || nx >= size || ny < 0 || ny >= size) {
        return false;
      }
      return tiles[ny][nx].type !== "blocked";
    });

    // Evite les arrêts prématurés: autorise un demi-tour si c'est le seul coup possible.
    if (valid.length === 0 && prevDir) {
      valid = directions.filter((dir) => {
        const offset = dirOffsets[dir];
        const nx = empty.x + offset.x;
        const ny = empty.y + offset.y;
        if (nx < 0 || nx >= size || ny < 0 || ny >= size) {
          return false;
        }
        return tiles[ny][nx].type !== "blocked";
      });
    }

    if (valid.length === 0) {
      break;
    }
    const dir = valid[randInt(0, valid.length - 1, rand)];
    const offset = dirOffsets[dir];
    const nx = empty.x + offset.x;
    const ny = empty.y + offset.y;

    const temp = tiles[ny][nx];
    tiles[ny][nx] = tiles[empty.y][empty.x];
    tiles[empty.y][empty.x] = temp;

    empty = { x: nx, y: ny };
    prevDir = dir;
    moves.push(dir);
  }

  return { emptyPos: empty, moves };
};

const getTier = (difficulty: DifficultyKey, index: number): TrackTier => {
  const tiers = TRACKS[difficulty];
  let offset = index;
  for (const tier of tiers) {
    if (offset < tier.levels) {
      return tier;
    }
    offset -= tier.levels;
  }
  return tiers[tiers.length - 1];
};

const getSeed = (difficulty: DifficultyKey, index: number): number => {
  const base = { easy: 1000, medium: 2000, hard: 3000, expert: 4000 }[
    difficulty
  ];
  return base + index * 97 + difficulty.length * 13;
};

const UNIQUE_SEED_SEARCH_LIMIT = 160;

type UniqueLevelCache = {
  levels: Level[];
  seeds: number[];
  signatures: Set<string>;
  duplicates: number;
  attempts: number;
};

const uniqueCaches: Record<DifficultyKey, UniqueLevelCache> = {
  easy: {
    levels: [],
    seeds: [],
    signatures: new Set(),
    duplicates: 0,
    attempts: 0,
  },
  medium: {
    levels: [],
    seeds: [],
    signatures: new Set(),
    duplicates: 0,
    attempts: 0,
  },
  hard: {
    levels: [],
    seeds: [],
    signatures: new Set(),
    duplicates: 0,
    attempts: 0,
  },
  expert: {
    levels: [],
    seeds: [],
    signatures: new Set(),
    duplicates: 0,
    attempts: 0,
  },
};

const buildLevelName = (difficulty: DifficultyKey, index: number): string => {
  return `${difficultyLabels[difficulty]} ${index + 1}`;
};

export const buildLevelSignature = (level: Level): string => {
  const tiles = level.tiles
    .map((row) =>
      row
        .map((tile) => {
          const decor = tile.decor ?? "-";
          return `${tile.type}:${tile.rot}:${tile.locked ? 1 : 0}:${decor}`;
        })
        .join("|"),
    )
    .join("/");
  const raw = [
    level.size,
    `${level.startPos.x},${level.startPos.y},${level.startDir}`,
    `${level.goalPos.x},${level.goalPos.y},${level.goalDir}`,
    `${level.emptyPos.x},${level.emptyPos.y}`,
    tiles,
  ].join("::");
  return createHash("sha256").update(raw).digest("hex");
};

const buildLevelWithSeed = (
  difficulty: DifficultyKey,
  clampedIndex: number,
  seed: number,
): Level => {
  const tier = getTier(difficulty, clampedIndex);
  const rand = mulberry32(seed);

  const size = tier.size;
  let path: Pos[] | null = null;
  let edges: Map<string, Set<Direction>> | null = null;
  let startPos: Pos = { x: 0, y: 0 };
  let goalPos: Pos = { x: size - 1, y: size - 1 };
  let startDir: Direction = "N";
  let goalDir: Direction = "S";
  let length = tier.pathMin;

  for (let attempt = 0; attempt < 80 && !edges; attempt += 1) {
    const selection = selectStartGoal(size, rand);
    startPos = selection.startPos;
    goalPos = selection.goalPos;
    startDir = selection.startDir;
    goalDir = selection.goalDir;

    const minLength = Math.max(tier.pathMin, manhattan(startPos, goalPos) + 1);
    const maxAllowed = size * size - tier.blocked - 1;
    const maxLength = Math.min(tier.pathMax, maxAllowed);

    if (minLength > maxLength) {
      continue;
    }

    length = randInt(minLength, maxLength, rand);
    for (let inner = 0; inner < 4 && !edges; inner += 1) {
      const candidate = generatePath(size, startPos, goalPos, length, rand);
      if (!candidate) {
        continue;
      }
      const candidateEdges = buildEdgesFromPath(candidate);
      const candidateSet = new Set(candidate.map(toKey));
      const extraLinks = randInt(tier.extraLinksMin, tier.extraLinksMax, rand);
      if (extraLinks > 0) {
        addExtraEdges(
          candidate,
          candidateSet,
          candidateEdges,
          size,
          extraLinks,
          rand,
        );
      }
      if (tier.minJunctions > 0) {
        const { junctions } = countJunctions(
          candidate,
          candidateEdges,
          startPos,
          goalPos,
        );
        if (junctions < tier.minJunctions) {
          continue;
        }
      }
      path = candidate;
      edges = candidateEdges;
    }
  }

  if (!path || !edges) {
    throw new Error("Generation de niveau impossible.");
  }

  const blockedSet = placeBlocked(size, path, tier.blocked, rand);
  const tiles: Tile[][] = Array.from({ length: size }, (_, y) =>
    Array.from({ length: size }, (_, x) => makeDecor(x, y)),
  );

  for (const pos of blockedSet) {
    const [xStr, yStr] = pos.split(",");
    const x = Number(xStr);
    const y = Number(yStr);
    tiles[y][x] = makeBlocked();
  }

  const pathSet = new Set(path.map(toKey));
  const startKey = toKey(startPos);
  const goalKey = toKey(goalPos);

  const connectorsMap = new Map<string, Direction[]>();
  for (const current of path) {
    const key = toKey(current);
    const connectors = new Set<Direction>();
    const edgeDirs = edges.get(key);
    if (edgeDirs) {
      edgeDirs.forEach((dir) => connectors.add(dir));
    }
    if (key === startKey) {
      connectors.add(startDir);
    }
    if (key === goalKey) {
      connectors.add(goalDir);
    }
    connectorsMap.set(key, Array.from(connectors));
  }

  const fourWayKeys = Array.from(connectorsMap.entries())
    .filter(([, dirs]) => new Set(dirs).size === 4)
    .map(([key]) => key);
  const roundaboutKey =
    fourWayKeys.length > 0
      ? fourWayKeys[randInt(0, fourWayKeys.length - 1, rand)]
      : null;

  for (const current of path) {
    const key = toKey(current);
    const connectors = connectorsMap.get(key) ?? [];
    tiles[current.y][current.x] = tileFromConnectors(
      connectors,
      rand,
      roundaboutKey === key,
    );
  }

  const emptyCandidates: Pos[] = [];
  const hasFreeNeighbor = (pos: Pos): boolean => {
    return Object.values(dirOffsets).some((offset) => {
      const nx = pos.x + offset.x;
      const ny = pos.y + offset.y;
      if (nx < 0 || nx >= size || ny < 0 || ny >= size) {
        return false;
      }
      return !blockedSet.has(`${nx},${ny}`);
    });
  };
  for (let y = 0; y < size; y += 1) {
    for (let x = 0; x < size; x += 1) {
      const key = `${x},${y}`;
      if (pathSet.has(key) || blockedSet.has(key)) {
        continue;
      }
      const pos = { x, y };
      if (hasFreeNeighbor(pos)) {
        emptyCandidates.push(pos);
      }
    }
  }

  const emptyPos =
    emptyCandidates.length > 0
      ? emptyCandidates[randInt(0, emptyCandidates.length - 1, rand)]
      : { x: 0, y: 0 };
  tiles[emptyPos.y][emptyPos.x] = makeEmpty();

  const scrambleSteps = randInt(tier.scrambleMin, tier.scrambleMax, rand);
  const scramble = scrambleTiles(tiles, emptyPos, scrambleSteps, rand);
  const finalEmptyPos = scramble.emptyPos;
  const solutionMoves = scramble.moves
    .slice()
    .reverse()
    .map((dir) => opposite[dir]);
  const moveLimit = Math.max(
    scramble.moves.length * 3,
    tier.scrambleMin * 3 + tier.moveMargin,
  );

  return {
    id: clampedIndex + 1,
    name: buildLevelName(difficulty, clampedIndex),
    difficulty,
    size,
    tiles,
    emptyPos: finalEmptyPos,
    startPos,
    startDir,
    goalPos,
    goalDir,
    moveLimit,
    solutionMoves,
  };
};

const ensureUniqueLevels = (difficulty: DifficultyKey, targetIndex: number) => {
  const cache = uniqueCaches[difficulty];
  for (let idx = cache.levels.length; idx <= targetIndex; idx += 1) {
    const baseSeed = getSeed(difficulty, idx);
    let seed = baseSeed;
    let level: Level | null = null;
    let signature = "";
    let attempts = 0;

    for (; attempts < UNIQUE_SEED_SEARCH_LIMIT; attempts += 1) {
      const candidate = buildLevelWithSeed(difficulty, idx, seed);
      signature = buildLevelSignature(candidate);
      if (!cache.signatures.has(signature)) {
        level = candidate;
        break;
      }
      seed += 1;
    }

    cache.attempts += attempts + 1;
    if (!level) {
      level = buildLevelWithSeed(difficulty, idx, baseSeed);
      signature = buildLevelSignature(level);
      if (cache.signatures.has(signature)) {
        cache.duplicates += 1;
      }
    }

    cache.seeds[idx] = seed;
    cache.levels[idx] = level;
    cache.signatures.add(signature);
  }
};

export const getUniqueLevelStats = (): Record<
  DifficultyKey,
  { total: number; unique: number; duplicates: number; attempts: number }
> => {
  difficultyOrder.forEach((difficulty) => {
    ensureUniqueLevels(difficulty, LEVELS_PER_DIFFICULTY - 1);
  });
  return difficultyOrder.reduce(
    (acc, difficulty) => {
      const cache = uniqueCaches[difficulty];
      acc[difficulty] = {
        total: cache.levels.length,
        unique: cache.signatures.size,
        duplicates: cache.duplicates,
        attempts: cache.attempts,
      };
      return acc;
    },
    {} as Record<
      DifficultyKey,
      { total: number; unique: number; duplicates: number; attempts: number }
    >,
  );
};

export const getLevelSeed = (
  difficulty: DifficultyKey,
  index: number,
): number => {
  const clampedIndex = Math.max(0, Math.min(index, LEVELS_PER_DIFFICULTY - 1));
  ensureUniqueLevels(difficulty, clampedIndex);
  return (
    uniqueCaches[difficulty].seeds[clampedIndex] ??
    getSeed(difficulty, clampedIndex)
  );
};

export const getLevel = (difficulty: DifficultyKey, index: number): Level => {
  const clampedIndex = Math.max(0, Math.min(index, LEVELS_PER_DIFFICULTY - 1));
  ensureUniqueLevels(difficulty, clampedIndex);
  return uniqueCaches[difficulty].levels[clampedIndex];
};

export const getDailyLevel = (date: Date = new Date()): Level => {
  const dayIndex = getDayOfYear(date);
  const dailyIndex = dayIndex % LEVELS_PER_DIFFICULTY;
  const base = getLevel("medium", dailyIndex);
  return {
    ...base,
    name: `Defi ${formatDateKey(date)}`,
    moveLimit: undefined,
    timeLimit: undefined,
  };
};