1import type {2 PlacedRectangle,3 PuzzleGiven,4 ShikakuPuzzle,5} from "@/lib/shikaku/types.ts";67interface GeneratorOptions {8 width: number;9 height: number;10 maxRectSize: number;11}1213interface RectTemplate {14 width: number;15 height: number;16}1718interface GeneratedPartition {19 row: number;20 col: number;21 width: number;22 height: number;23}2425const DEFAULT_OPTIONS: GeneratorOptions = {26 width: 8,27 height: 8,28 maxRectSize: 8,29};3031const MAX_GENERATE_ATTEMPTS = 100;3233export function createSeededRng(seed: string): () => number {34 let hash = 1779033703 ^ seed.length;3536 for (let index = 0; index < seed.length; index++) {37 hash = Math.imul(hash ^ seed.charCodeAt(index), 3432918353);38 hash = (hash << 13) | (hash >>> 19);39 }4041 return () => {42 hash = Math.imul(hash ^ (hash >>> 16), 2246822507);43 hash = Math.imul(hash ^ (hash >>> 13), 3266489909);44 hash ^= hash >>> 16;45 return (hash >>> 0) / 4294967296;46 };47}4849export function createPuzzleFromDailySeed(50 date: string,51 streakIndex = 0,52 options: Partial<GeneratorOptions> = {},53): ShikakuPuzzle {54 const seed = `${date}:${streakIndex}`;55 const puzzle = generatePuzzleFromSeed(seed, options);56 return {57 ...puzzle,58 id: `daily-${date}-${streakIndex}`,59 date,60 streakIndex,61 seed,62 };63}6465export function generatePuzzleFromSeed(66 seed: string,67 options: Partial<GeneratorOptions> = {},68): ShikakuPuzzle {69 const config = { ...DEFAULT_OPTIONS, ...options };70 const rng = createSeededRng(seed);7172 for (let attempt = 0; attempt < MAX_GENERATE_ATTEMPTS; attempt++) {73 const partitions = tryGeneratePartitions(config, rng);74 if (!partitions) continue;7576 const givens: PuzzleGiven[] = [];77 const solution: PlacedRectangle[] = [];78 let allSingles = true;7980 partitions.forEach((partition, index) => {81 const clueCol = partition.col + randomInt(rng, partition.width);82 const clueRow = partition.row + randomInt(rng, partition.height);83 const value = partition.width * partition.height;84 if (value > 1) allSingles = false;8586 givens.push({87 id: index,88 row: clueRow,89 col: clueCol,90 value,91 });9293 solution.push({94 clueId: index,95 row: partition.row,96 col: partition.col,97 width: partition.width,98 height: partition.height,99 value,100 });101 });102103 if (allSingles) continue;104105 return {106 id: `seed-${seed}`,107 date: seed,108 streakIndex: 0,109 width: config.width,110 height: config.height,111 givens,112 solution,113 difficulty: classifyDifficulty(config.maxRectSize),114 seed,115 };116 }117118 throw new Error("Failed to generate shikaku puzzle from seed");119}120121function tryGeneratePartitions(122 options: GeneratorOptions,123 rng: () => number,124): GeneratedPartition[] | null {125 const grid = makeGrid(options.width, options.height, -1);126 const partitions: GeneratedPartition[] = [];127 const templateCache = new Map<string, RectTemplate[]>();128 const failedStates = new Set<string>();129130 const ok = partitionGridRec(131 grid,132 options,133 partitions,134 rng,135 templateCache,136 failedStates,137 options.width * options.height,138 );139140 return ok ? partitions : null;141}142143function partitionGridRec(144 grid: number[][],145 options: GeneratorOptions,146 partitions: GeneratedPartition[],147 rng: () => number,148 templateCache: Map<string, RectTemplate[]>,149 failedStates: Set<string>,150 remaining: number,151): boolean {152 const anchor = selectMostConstrainedAnchor(grid, options, templateCache);153 if (!anchor) return true;154 if (anchor.candidates.length === 0) {155 failedStates.add(156 failedKey(157 anchor.row,158 anchor.col,159 anchor.maxWidth,160 anchor.maxHeight,161 remaining,162 ),163 );164 return false;165 }166167 const failState = failedKey(168 anchor.row,169 anchor.col,170 anchor.maxWidth,171 anchor.maxHeight,172 remaining,173 );174 if (failedStates.has(failState)) {175 return false;176 }177178 const order = [...anchor.candidates];179 shuffle(order, rng);180181 const partitionId = partitions.length;182 for (const candidate of order) {183 place(184 grid,185 anchor.row,186 anchor.col,187 candidate.width,188 candidate.height,189 partitionId,190 );191 partitions.push({192 row: anchor.row,193 col: anchor.col,194 width: candidate.width,195 height: candidate.height,196 });197198 if (199 partitionGridRec(200 grid,201 options,202 partitions,203 rng,204 templateCache,205 failedStates,206 remaining - candidate.width * candidate.height,207 )208 ) {209 return true;210 }211212 partitions.pop();213 clear(grid, anchor.row, anchor.col, candidate.width, candidate.height);214 }215216 failedStates.add(failState);217 return false;218}219220function selectMostConstrainedAnchor(221 grid: number[][],222 options: GeneratorOptions,223 templateCache: Map<string, RectTemplate[]>,224): {225 row: number;226 col: number;227 maxWidth: number;228 maxHeight: number;229 candidates: RectTemplate[];230} | null {231 let best:232 | {233 row: number;234 col: number;235 maxWidth: number;236 maxHeight: number;237 candidates: RectTemplate[];238 }239 | null = null;240241 for (let row = 0; row < options.height; row++) {242 for (let col = 0; col < options.width; col++) {243 if (!isAnchorCell(grid, row, col)) continue;244245 const [maxWidth, maxHeight] = anchorExtents(246 grid,247 row,248 col,249 options.width,250 options.height,251 );252 const templates = candidateTemplatesForAnchor(253 row,254 col,255 maxWidth,256 maxHeight,257 options.maxRectSize,258 templateCache,259 );260 const candidates = templates.filter((template) =>261 fits(grid, row, col, template.width, template.height)262 );263264 if (!best || candidates.length < best.candidates.length) {265 best = { row, col, maxWidth, maxHeight, candidates };266 }267268 if (best && best.candidates.length <= 1) {269 return best;270 }271 }272 }273274 return best;275}276277function candidateTemplatesForAnchor(278 row: number,279 col: number,280 maxWidth: number,281 maxHeight: number,282 maxRectSize: number,283 templateCache: Map<string, RectTemplate[]>,284): RectTemplate[] {285 const key = `${row}:${col}:${maxWidth}:${maxHeight}:${maxRectSize}`;286 const cached = templateCache.get(key);287 if (cached) return cached;288289 const templates: RectTemplate[] = [];290 for (let width = 1; width <= maxWidth; width++) {291 for (let height = 1; height <= maxHeight; height++) {292 if (width * height > maxRectSize) continue;293 templates.push({ width, height });294 }295 }296297 templateCache.set(key, templates);298 return templates;299}300301function anchorExtents(302 grid: number[][],303 row: number,304 col: number,305 width: number,306 height: number,307): [number, number] {308 let maxWidth = 0;309 for (310 let currentCol = col;311 currentCol < width && grid[row][currentCol] === -1;312 currentCol++313 ) {314 maxWidth++;315 }316317 let maxHeight = 0;318 for (319 let currentRow = row;320 currentRow < height && grid[currentRow][col] === -1;321 currentRow++322 ) {323 maxHeight++;324 }325326 return [maxWidth, maxHeight];327}328329function isAnchorCell(grid: number[][], row: number, col: number): boolean {330 if (grid[row][col] !== -1) return false;331 if (col > 0 && grid[row][col - 1] === -1) return false;332 if (row > 0 && grid[row - 1][col] === -1) return false;333 return true;334}335336function fits(337 grid: number[][],338 row: number,339 col: number,340 width: number,341 height: number,342): boolean {343 for (let dy = 0; dy < height; dy++) {344 for (let dx = 0; dx < width; dx++) {345 if (grid[row + dy][col + dx] !== -1) {346 return false;347 }348 }349 }350351 return true;352}353354function place(355 grid: number[][],356 row: number,357 col: number,358 width: number,359 height: number,360 id: number,361): void {362 for (let dy = 0; dy < height; dy++) {363 for (let dx = 0; dx < width; dx++) {364 grid[row + dy][col + dx] = id;365 }366 }367}368369function clear(370 grid: number[][],371 row: number,372 col: number,373 width: number,374 height: number,375): void {376 for (let dy = 0; dy < height; dy++) {377 for (let dx = 0; dx < width; dx++) {378 grid[row + dy][col + dx] = -1;379 }380 }381}382383function makeGrid(width: number, height: number, fill: number): number[][] {384 return Array.from(385 { length: height },386 () => Array.from({ length: width }, () => fill),387 );388}389390function shuffle<T>(values: T[], rng: () => number): void {391 for (let index = values.length - 1; index > 0; index--) {392 const swapIndex = randomInt(rng, index + 1);393 [values[index], values[swapIndex]] = [values[swapIndex], values[index]];394 }395}396397function randomInt(rng: () => number, maxExclusive: number): number {398 return Math.floor(rng() * maxExclusive);399}400401function failedKey(402 row: number,403 col: number,404 maxWidth: number,405 maxHeight: number,406 remaining: number,407): string {408 return `${row}:${col}:${maxWidth}:${maxHeight}:${remaining}`;409}410411function classifyDifficulty(maxRectSize: number): "easy" | "medium" | "hard" {412 if (maxRectSize <= 6) return "easy";413 if (maxRectSize <= 10) return "medium";414 return "hard";415}