Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 | 1x 17x 17x 17x 17x 17x 34x 6x 34x 28x 28x 34x 17x 17x 3x 3x 3x 3x 3x 14x 14x 14x 14x 17x 79x 78x 78x 78x 78x 78x 65x 65x 15x 15x 65x 78x 79x 14x 14x 14x 17x 65x 65x 115x 107x 107x 115x 65x 13x 13x 65x 14x 14x 14x 14x 14x 14x 65x 107x 107x 60x 14x 14x 14x 14x 17x 17x 17x 17x 17x 17x 17x 1x 78x 78x 78x 78x 78x 78x 78x 78x 78x 78x 78x 78x 319x 1677x 1677x 319x 78x 78x 78x 78x 133x 133x 133x 124x 124x 133x 133x 78x 78x 78x 78x 78x 78x 1x 133x 133x 133x 133x 133x 266x 266x 266x 266x 883x 3614x 3614x 2492x 2492x 3614x 883x 266x 133x 133x 124x 124x 124x 124x 124x 124x 133x 1x 124x 124x 124x 411x 222x 411x 189x 189x 411x 124x 1x 1x 3624x 3624x 3624x 3624x 1832x 3624x 1792x 1792x 3621x 3621x 3621x 3621x 3624x 12276x 12276x 12276x 12276x 12276x 903x 143x 143x 12276x 2861x 2861x 3624x 25x 25x 2836x 2836x 3624x 1466x 874x 874x 872x 872x 874x 874x 1466x 2498x 2498x 3624x 913x 442x 442x 913x 2496x 2496x 3624x 8893x 8893x 8893x 8893x 4490x 4490x 8980x 8980x 76x 76x 105x 105x 105x 76x 76x 76x 8980x 8893x 4403x 4403x 8806x 8806x 108x 168x 168x 168x 108x 108x 108x 8806x 4403x 8893x 8893x 8893x 3624x 1x 917x 917x 4243x 4243x 4243x 20287x 20287x 20287x 20287x 4231x 905x 917x 1x 907x 907x 485x 485x 188x 188x 485x 485x 907x 422x 422x 154x 154x 422x 422x 907x 1x 442x 442x 227x 2x 2x 2x 227x 442x 215x 215x 215x 442x 1x 78x 78x 155x 155x 215x 215x 155x 78x 78x 1x 222x 222x 222x 222x 222x 222x 840x 2612x 2612x 2982x 2982x 2612x 2612x 728x 110x 110x 222x 354x 872x 872x 1112x 1112x 872x 872x 257x 13x 13x 222x 1x 1x 31x 31x 31x 31x 31x 31x 31x 31x 31x 31x 120x 120x 710x 710x 240x 710x 470x 43x 43x 43x 43x 43x 43x 43x 43x 43x 470x 470x 710x 120x 31x 31x 31x 128x 128x 718x 718x 240x 718x 478x 31x 31x 31x 31x 31x 31x 31x 31x 31x 478x 478x 718x 128x 31x 31x 31x 31x 31x 120x 590x 240x 240x 590x 261x 261x 261x 590x 19x 19x 19x 17x 17x 17x 17x 17x 17x 17x 19x 590x 120x 31x 31x 31x 73x 144x 144x 59x 59x 59x 59x 144x 14x 14x 14x 6x 6x 6x 6x 6x 6x 14x 144x 8x 73x 31x 31x 31x 31x 68x 68x 68x 68x 68x 1x 1x 1x 68x 68x 4x 4x 4x 68x 68x 4x 4x 3x 1x 1x 1x 3x 4x 68x 68x 64x 68x 4x 1x 4x 1x 3x 2x 2x 4x 68x 31x 31x 31x 64x 66x 66x 66x 35x 35x 35x 35x 4x 4x 35x 66x 64x 31x 31x 31x 64x 66x 66x 66x 35x 35x 35x 35x 2x 2x 35x 66x 64x 31x 31x 31x 5x 10x 16x 16x 8x 8x 8x 8x 8x 10x 10x 2x 2x 10x 5x 31x 31x 31x 1x 19x 19x 19x | export function make_grids(words, width, height, timeout, all_cross, allow_diagonals, allow_reverse, progressCallback) {
const deadline = Date.now() + timeout;
const lost_words = [];
const validWords = [];
for (const word of words) {
if (word.length > width && word.length > height) {
lost_words.push(word);
} else {
validWords.push(word);
}
}
if (validWords.length === 0) {
return {
info: { message: 'No valid words to place', lost_words, used_words: [] },
payload: []
};
}
const candidates = [];
const maxCandidates = 5;
for (let attempt = 0; attempt < 50 && candidates.length < maxCandidates; attempt++) {
if (Date.now() >= deadline) break;
const result = generateOneGrid(validWords, width, height, all_cross, deadline);
if (result) {
const { grid, usedWords } = result;
if (!isDuplicateGrid(grid, candidates)) {
candidates.push(grid);
if (progressCallback) {
progressCallback(candidates.length, maxCandidates);
}
}
}
}
// Determine used/lost words based on best candidate (most words placed)
let bestUsed = new Set();
for (const grid of candidates) {
const wordsInGrid = new Set();
for (const word of validWords) {
if (findWordInGrid(grid, word)) {
wordsInGrid.add(word);
}
}
if (wordsInGrid.size > bestUsed.size) {
bestUsed = wordsInGrid;
}
}
const used_words = validWords.filter(w => bestUsed.has(w));
const finalLost = [...lost_words, ...validWords.filter(w => !bestUsed.has(w))];
// Filter candidates to only include grids that contain all used_words
const filteredCandidates = candidates.filter(grid => {
for (const word of used_words) {
if (!findWordInGrid(grid, word)) return false;
}
return true;
});
return {
info: {
message: filteredCandidates.length > 0 ? `Generated ${filteredCandidates.length} candidate(s)` : 'Could not generate any grids',
lost_words: finalLost,
used_words
},
payload: filteredCandidates
};
}
function generateOneGrid(words, width, height, all_cross, deadline) {
const grid = Array.from({ length: height }, () => Array(width).fill(''));
const placements = [];
const shuffled = [...words].sort(() => Math.random() - 0.5);
const usedWords = [];
for (let retry = 0; retry < 5; retry++) {
const wordsToTry = retry === 0 ? shuffled : shuffled.slice(0, shuffled.length - retry);
if (wordsToTry.length === 0) break;
// Reset grid
for (let r = 0; r < height; r++) {
for (let c = 0; c < width; c++) {
grid[r][c] = '';
}
}
placements.length = 0;
usedWords.length = 0;
for (const word of wordsToTry) {
if (Date.now() >= deadline) return null;
const placed = tryPlaceWord(word, grid, placements, width, height, all_cross);
if (placed) {
usedWords.push(word);
}
// If word can't be placed, skip it (it becomes a lost word)
}
if (usedWords.length > 0) {
return { grid: grid.map(row => [...row]), usedWords: [...usedWords] };
}
}
return null;
}
function tryPlaceWord(word, grid, placements, width, height, all_cross) {
const positions = [];
// Collect all valid positions
for (const direction of ['horizontal', 'vertical']) {
const maxRow = direction === 'horizontal' ? height : height - word.length + 1;
const maxCol = direction === 'horizontal' ? width - word.length + 1 : width;
for (let row = 0; row < maxRow; row++) {
for (let col = 0; col < maxCol; col++) {
const placement = { word, row, col, direction };
if (isValidPlacement(placement, grid, placements, width, height, all_cross)) {
positions.push(placement);
}
}
}
}
if (positions.length === 0) return false;
// Shuffle and pick one
const chosen = positions[Math.floor(Math.random() * positions.length)];
applyPlacement(chosen, grid);
placements.push(chosen);
return true;
}
function applyPlacement(placement, grid) {
const { word, row, col, direction } = placement;
for (let i = 0; i < word.length; i++) {
if (direction === 'horizontal') {
grid[row][col + i] = word[i];
} else {
grid[row + i][col] = word[i];
}
}
}
export function isValidPlacement(placement, grid, existingPlacements, width, height, all_cross) {
const { word, row, col, direction } = placement;
// Bounds check
if (direction === 'horizontal') {
if (col + word.length > width || row >= height) return false;
} else {
if (row + word.length > height || col >= width) return false;
}
let hasIntersection = false;
// Check each cell the word would occupy
for (let i = 0; i < word.length; i++) {
const r = direction === 'horizontal' ? row : row + i;
const c = direction === 'horizontal' ? col + i : col;
const existing = grid[r][c];
if (existing !== '') {
if (existing !== word[i]) return false;
hasIntersection = true;
}
}
// all_cross: must intersect if there are existing placements
if (all_cross && existingPlacements.length > 0 && !hasIntersection) {
return false;
}
// Check perpendicular adjacency with same-direction words
for (const ep of existingPlacements) {
if (ep.direction === direction) {
// Parallel intersection check - same direction words sharing cells
if (sharesCell(placement, ep)) return false;
// Perpendicular adjacency check - same direction words touching
if (areSameDirectionAdjacent(placement, ep)) return false;
}
}
// Check that placement doesn't extend or touch endpoints of existing same-direction words
for (const ep of existingPlacements) {
if (ep.direction === direction) {
if (extendsWord(placement, ep, direction)) return false;
}
}
// Check perpendicular adjacency: new word cells adjacent to same-direction existing word cells
for (let i = 0; i < word.length; i++) {
const r = direction === 'horizontal' ? row : row + i;
const c = direction === 'horizontal' ? col + i : col;
if (direction === 'horizontal') {
// Check above and below
for (const dr of [-1, 1]) {
const nr = r + dr;
if (nr >= 0 && nr < height && grid[nr][c] !== '') {
// Is this cell part of a same-direction (horizontal) word?
const isIntersectionWithPerp = existingPlacements.some(ep =>
ep.direction === 'vertical' &&
c === ep.col &&
nr >= ep.row && nr < ep.row + ep.word.length
);
if (!isIntersectionWithPerp) {
// Check if cell is part of a horizontal word
const isPartOfSameDir = existingPlacements.some(ep =>
ep.direction === 'horizontal' &&
nr === ep.row &&
c >= ep.col && c < ep.col + ep.word.length
);
if (isPartOfSameDir) return false;
}
}
}
} else {
// Check left and right
for (const dc of [-1, 1]) {
const nc = c + dc;
if (nc >= 0 && nc < width && grid[r][nc] !== '') {
const isIntersectionWithPerp = existingPlacements.some(ep =>
ep.direction === 'horizontal' &&
r === ep.row &&
nc >= ep.col && nc < ep.col + ep.word.length
);
if (!isIntersectionWithPerp) {
const isPartOfSameDir = existingPlacements.some(ep =>
ep.direction === 'vertical' &&
nc === ep.col &&
r >= ep.row && r < ep.row + ep.word.length
);
if (isPartOfSameDir) return false;
}
}
}
}
}
return true;
}
function sharesCell(p1, p2) {
for (let i = 0; i < p1.word.length; i++) {
const r1 = p1.direction === 'horizontal' ? p1.row : p1.row + i;
const c1 = p1.direction === 'horizontal' ? p1.col + i : p1.col;
for (let j = 0; j < p2.word.length; j++) {
const r2 = p2.direction === 'horizontal' ? p2.row : p2.row + j;
const c2 = p2.direction === 'horizontal' ? p2.col + j : p2.col;
if (r1 === r2 && c1 === c2) return true;
}
}
return false;
}
function areSameDirectionAdjacent(p1, p2) {
if (p1.direction === 'horizontal' && p2.direction === 'horizontal') {
const rowDiff = Math.abs(p1.row - p2.row);
if (rowDiff !== 1) return false;
const start1 = p1.col, end1 = p1.col + p1.word.length - 1;
const start2 = p2.col, end2 = p2.col + p2.word.length - 1;
return start1 <= end2 && start2 <= end1;
}
if (p1.direction === 'vertical' && p2.direction === 'vertical') {
const colDiff = Math.abs(p1.col - p2.col);
if (colDiff !== 1) return false;
const start1 = p1.row, end1 = p1.row + p1.word.length - 1;
const start2 = p2.row, end2 = p2.row + p2.word.length - 1;
return start1 <= end2 && start2 <= end1;
}
return false;
}
function extendsWord(newP, existingP, direction) {
if (direction === 'horizontal') {
if (newP.row !== existingP.row) return false;
const existingEnd = existingP.col + existingP.word.length;
const newEnd = newP.col + newP.word.length;
// Check if new word starts right at existing word's end or ends right before existing word's start
if (newP.col === existingEnd || newEnd === existingP.col) return true;
} else {
if (newP.col !== existingP.col) return false;
const existingEnd = existingP.row + existingP.word.length;
const newEnd = newP.row + newP.word.length;
if (newP.row === existingEnd || newEnd === existingP.row) return true;
}
return false;
}
function isDuplicateGrid(grid, candidates) {
return candidates.some(existing =>
existing.length === grid.length &&
existing.every((row, r) =>
row.length === grid[r].length &&
row.every((cell, c) => cell === grid[r][c])
)
);
}
function findWordInGrid(grid, word) {
const height = grid.length;
const width = grid[0].length;
// Horizontal
for (let r = 0; r < height; r++) {
for (let c = 0; c <= width - word.length; c++) {
let match = true;
for (let i = 0; i < word.length; i++) {
if (grid[r][c + i] !== word[i]) { match = false; break; }
}
if (match) return true;
}
}
// Vertical
for (let c = 0; c < width; c++) {
for (let r = 0; r <= height - word.length; r++) {
let match = true;
for (let i = 0; i < word.length; i++) {
if (grid[r + i][c] !== word[i]) { match = false; break; }
}
if (match) return true;
}
}
return false;
}
export function validateGrid(grid, words, options) {
const { all_cross, allow_diagonals, allow_reverse } = options;
const issues = [];
const height = grid.length;
const width = grid[0] ? grid[0].length : 0;
// Find all letter runs in the grid
const foundPlacements = [];
// Horizontal runs
for (let r = 0; r < height; r++) {
let runStart = -1;
for (let c = 0; c <= width; c++) {
const cell = c < width ? grid[r][c] : '';
if (cell !== '') {
if (runStart === -1) runStart = c;
} else {
if (runStart !== -1 && c - runStart >= 2) {
const run = [];
for (let i = runStart; i < c; i++) run.push(grid[r][i]);
foundPlacements.push({
text: run.join(''),
row: r, col: runStart,
direction: 'horizontal',
length: c - runStart
});
}
runStart = -1;
}
}
}
// Vertical runs
for (let c = 0; c < width; c++) {
let runStart = -1;
for (let r = 0; r <= height; r++) {
const cell = r < height ? grid[r][c] : '';
if (cell !== '') {
if (runStart === -1) runStart = r;
} else {
if (runStart !== -1 && r - runStart >= 2) {
const run = [];
for (let i = runStart; i < r; i++) run.push(grid[i][c]);
foundPlacements.push({
text: run.join(''),
row: runStart, col: c,
direction: 'vertical',
length: r - runStart
});
}
runStart = -1;
}
}
}
// Diagonal runs (if allow_diagonals)
const diagonalPlacements = [];
// Down-right diagonals
for (let r = 0; r < height; r++) {
for (let c = 0; c < width; c++) {
if (grid[r][c] === '') continue;
let run = '';
let len = 0;
for (let i = 0; r + i < height && c + i < width && grid[r + i][c + i] !== ''; i++) {
run += grid[r + i][c + i];
len++;
}
if (len >= 2) {
// Only record if this is the start (no letter diagonally before)
const prevR = r - 1, prevC = c - 1;
if (prevR < 0 || prevC < 0 || grid[prevR][prevC] === '') {
diagonalPlacements.push({
text: run,
row: r, col: c,
direction: 'diagonal-dr',
length: len
});
}
}
}
}
// Find word positions within runs (handles overlapping words like NAMEDAM)
function findWordInRuns(word, runs) {
for (const p of runs) {
const idx = p.text.indexOf(word);
if (idx !== -1) {
const row = p.direction === 'horizontal' ? p.row : p.row + idx;
const col = p.direction === 'horizontal' ? p.col + idx : p.col;
return { word, text: word, row, col, direction: p.direction, length: word.length };
}
if (allow_reverse) {
const rev = reverseStr(p.text);
const ridx = rev.indexOf(word);
if (ridx !== -1) {
// Found reversed within this run
const actualIdx = p.text.length - 1 - ridx - (word.length - 1);
const row = p.direction === 'horizontal' ? p.row : p.row + actualIdx;
const col = p.direction === 'horizontal' ? p.col + actualIdx : p.col;
return { word, text: word, row, col, direction: p.direction, length: word.length, reversed: true };
}
}
}
return null;
}
// Check each expected word
const wordPlacements = [];
for (const word of words) {
let placement = findWordInRuns(word, foundPlacements);
let foundOnlyDiagonal = false;
let foundOnlyReversed = false;
if (!placement && allow_diagonals) {
placement = findWordInRuns(word, diagonalPlacements);
if (placement) foundOnlyDiagonal = true;
}
if (!placement && !allow_diagonals) {
const diagP = findWordInRuns(word, diagonalPlacements);
if (diagP) foundOnlyDiagonal = true;
}
if (!placement && !allow_reverse) {
// Check if word exists reversed in standard runs
for (const p of foundPlacements) {
if (p.text.includes(reverseStr(word)) || reverseStr(p.text).includes(word)) {
foundOnlyReversed = true;
break;
}
}
}
if (placement) {
wordPlacements.push(placement);
} else {
if (foundOnlyDiagonal && !allow_diagonals) {
issues.push(`Missing word: ${word} (found diagonally but allow_diagonals is false)`);
} else if (foundOnlyReversed && !allow_reverse) {
issues.push(`Missing word: ${word} (found reversed but allow_reverse is false)`);
} else {
issues.push(`Missing word: ${word}`);
}
}
}
// Perpendicular adjacency check
for (let i = 0; i < wordPlacements.length; i++) {
for (let j = i + 1; j < wordPlacements.length; j++) {
const a = wordPlacements[i];
const b = wordPlacements[j];
if (a.direction === b.direction) {
if (areSameDirectionAdjacent(
{ ...a, word: a.text },
{ ...b, word: b.text }
)) {
issues.push(`Invalid perpendicular adjacency between ${a.word} and ${b.word}`);
}
}
}
}
// Parallel intersection check
for (let i = 0; i < wordPlacements.length; i++) {
for (let j = i + 1; j < wordPlacements.length; j++) {
const a = wordPlacements[i];
const b = wordPlacements[j];
if (a.direction === b.direction) {
if (sharesCell(
{ ...a, word: a.text },
{ ...b, word: b.text }
)) {
issues.push(`Parallel intersection between ${a.word} and ${b.word}`);
}
}
}
}
// all_cross check
if (all_cross && wordPlacements.length >= 2) {
for (const wp of wordPlacements) {
const intersects = wordPlacements.some(other => {
if (other === wp) return false;
if (other.direction === wp.direction) return false;
// Check if they share a cell
return sharesCell(
{ ...wp, word: wp.text },
{ ...other, word: other.text }
);
});
if (!intersects) {
issues.push(`${wp.word} does not intersect any other word`);
}
}
}
return { valid: issues.length === 0, issues };
}
function reverseStr(s) {
return s.split('').reverse().join('');
}
|