394 lines
14 KiB
Python
394 lines
14 KiB
Python
|
"""Crossword grid generation algorithm.
|
||
|
|
|
||
|
|
Uses a greedy placement strategy with two passes:
|
||
|
|
1. Sort words longest-first (harder to place, so do them early).
|
||
|
|
2. Place the first word horizontally in the centre of the grid.
|
||
|
|
3. For each remaining word, find all positions where it intersects an
|
||
|
|
already-placed word at a shared letter, score them, and pick the best.
|
||
|
|
4. Run a second pass for words that failed the first time (the grid has
|
||
|
|
grown, so new opportunities may exist).
|
||
|
|
5. Number the cells in reading order and build the Crossword object.
|
||
|
|
"""
|
||
|
|
|
||
|
|
import logging
|
||
|
|
import random
|
||
|
|
from typing import Optional
|
||
|
|
|
||
|
|
from models import Cell, Crossword, Direction, NumberedClue, PlacedWord, WordClue
|
||
|
|
|
||
|
|
logger = logging.getLogger(__name__)
|
||
|
|
|
||
|
|
|
||
|
|
class _GridBuilder:
|
||
|
|
"""Sparse, mutable grid used during crossword construction.
|
||
|
|
|
||
|
|
Internally stores letters in a dict keyed by (row, col) so we never
|
||
|
|
worry about array resizing. Converts to a dense Cell grid only when
|
||
|
|
`build()` is called.
|
||
|
|
"""
|
||
|
|
|
||
|
|
def __init__(self, size: int):
|
||
|
|
self.size = size
|
||
|
|
self._letters: dict[tuple[int, int], str] = {}
|
||
|
|
self._dirs: dict[tuple[int, int], set[Direction]] = {}
|
||
|
|
self.placed: list[PlacedWord] = []
|
||
|
|
|
||
|
|
# -- low-level helpers ---------------------------------------------------
|
||
|
|
|
||
|
|
def get(self, row: int, col: int) -> Optional[str]:
|
||
|
|
return self._letters.get((row, col))
|
||
|
|
|
||
|
|
def is_occupied(self, row: int, col: int) -> bool:
|
||
|
|
return (row, col) in self._letters
|
||
|
|
|
||
|
|
def in_bounds(self, row: int, col: int) -> bool:
|
||
|
|
return 0 <= row < self.size and 0 <= col < self.size
|
||
|
|
|
||
|
|
# -- mutation ------------------------------------------------------------
|
||
|
|
|
||
|
|
def place(self, word: str, clue: str, row: int, col: int,
|
||
|
|
direction: Direction) -> None:
|
||
|
|
pw = PlacedWord(word=word, clue=clue, row=row, col=col,
|
||
|
|
direction=direction)
|
||
|
|
self.placed.append(pw)
|
||
|
|
for i, (r, c) in enumerate(pw.cells()):
|
||
|
|
self._letters[(r, c)] = word[i]
|
||
|
|
self._dirs.setdefault((r, c), set()).add(direction)
|
||
|
|
|
||
|
|
# -- validation ----------------------------------------------------------
|
||
|
|
|
||
|
|
def is_valid(self, word: str, row: int, col: int,
|
||
|
|
direction: Direction) -> bool:
|
||
|
|
"""Return True if *word* can legally be placed at (row, col)."""
|
||
|
|
length = len(word)
|
||
|
|
|
||
|
|
if direction == Direction.ACROSS:
|
||
|
|
end_col = col + length - 1
|
||
|
|
if col < 0 or row < 0 or end_col >= self.size or row >= self.size:
|
||
|
|
return False
|
||
|
|
|
||
|
|
# Nothing immediately before / after the word
|
||
|
|
if self.is_occupied(row, col - 1):
|
||
|
|
return False
|
||
|
|
if self.is_occupied(row, end_col + 1):
|
||
|
|
return False
|
||
|
|
|
||
|
|
has_cross = False
|
||
|
|
for i in range(length):
|
||
|
|
c = col + i
|
||
|
|
existing = self.get(row, c)
|
||
|
|
if existing is not None:
|
||
|
|
if existing != word[i]:
|
||
|
|
return False
|
||
|
|
# Must cross a DOWN word — overlapping same direction is illegal
|
||
|
|
if Direction.ACROSS in self._dirs.get((row, c), set()):
|
||
|
|
return False
|
||
|
|
has_cross = True
|
||
|
|
else:
|
||
|
|
# Parallel-adjacency guard: no letters directly above/below
|
||
|
|
if self.is_occupied(row - 1, c) or self.is_occupied(row + 1, c):
|
||
|
|
return False
|
||
|
|
|
||
|
|
return has_cross or not self.placed
|
||
|
|
|
||
|
|
else: # DOWN
|
||
|
|
end_row = row + length - 1
|
||
|
|
if row < 0 or col < 0 or end_row >= self.size or col >= self.size:
|
||
|
|
return False
|
||
|
|
|
||
|
|
if self.is_occupied(row - 1, col):
|
||
|
|
return False
|
||
|
|
if self.is_occupied(end_row + 1, col):
|
||
|
|
return False
|
||
|
|
|
||
|
|
has_cross = False
|
||
|
|
for i in range(length):
|
||
|
|
r = row + i
|
||
|
|
existing = self.get(r, col)
|
||
|
|
if existing is not None:
|
||
|
|
if existing != word[i]:
|
||
|
|
return False
|
||
|
|
if Direction.DOWN in self._dirs.get((r, col), set()):
|
||
|
|
return False
|
||
|
|
has_cross = True
|
||
|
|
else:
|
||
|
|
if self.is_occupied(r, col - 1) or self.is_occupied(r, col + 1):
|
||
|
|
return False
|
||
|
|
|
||
|
|
return has_cross or not self.placed
|
||
|
|
|
||
|
|
# -- scoring -------------------------------------------------------------
|
||
|
|
|
||
|
|
def score(self, word: str, row: int, col: int,
|
||
|
|
direction: Direction) -> float:
|
||
|
|
"""Score a valid placement — higher is better."""
|
||
|
|
s = 0.0
|
||
|
|
length = len(word)
|
||
|
|
|
||
|
|
if direction == Direction.ACROSS:
|
||
|
|
for i in range(length):
|
||
|
|
if self.is_occupied(row, col + i):
|
||
|
|
s += 10.0
|
||
|
|
else:
|
||
|
|
for i in range(length):
|
||
|
|
if self.is_occupied(row + i, col):
|
||
|
|
s += 10.0
|
||
|
|
|
||
|
|
# Prefer compact placement near the grid centre
|
||
|
|
centre = self.size / 2.0
|
||
|
|
if direction == Direction.ACROSS:
|
||
|
|
mid_r, mid_c = float(row), col + length / 2.0
|
||
|
|
else:
|
||
|
|
mid_r, mid_c = row + length / 2.0, float(col)
|
||
|
|
s -= (abs(mid_r - centre) + abs(mid_c - centre)) * 0.5
|
||
|
|
|
||
|
|
return s
|
||
|
|
|
||
|
|
# -- candidate search ----------------------------------------------------
|
||
|
|
|
||
|
|
def find_best(self, word: str) -> Optional[tuple[int, int, Direction]]:
|
||
|
|
"""Find the highest-scoring valid position for *word*, or None."""
|
||
|
|
best_pos: Optional[tuple[int, int, Direction]] = None
|
||
|
|
best_score = float("-inf")
|
||
|
|
|
||
|
|
for pw in self.placed:
|
||
|
|
for i, ch_new in enumerate(word):
|
||
|
|
for j, ch_old in enumerate(pw.word):
|
||
|
|
if ch_new != ch_old:
|
||
|
|
continue
|
||
|
|
# Try placing perpendicular to the existing word
|
||
|
|
if pw.direction == Direction.ACROSS:
|
||
|
|
nr, nc, nd = pw.row - i, pw.col + j, Direction.DOWN
|
||
|
|
else:
|
||
|
|
nr, nc, nd = pw.row + j, pw.col - i, Direction.ACROSS
|
||
|
|
|
||
|
|
if self.is_valid(word, nr, nc, nd):
|
||
|
|
sc = self.score(word, nr, nc, nd)
|
||
|
|
if sc > best_score:
|
||
|
|
best_score = sc
|
||
|
|
best_pos = (nr, nc, nd)
|
||
|
|
|
||
|
|
return best_pos
|
||
|
|
|
||
|
|
# -- finalization --------------------------------------------------------
|
||
|
|
|
||
|
|
def build(self) -> Crossword:
|
||
|
|
"""Trim to bounding box, number cells, and return a Crossword."""
|
||
|
|
if not self.placed:
|
||
|
|
return Crossword(grid=[], placed_words=[], width=0, height=0)
|
||
|
|
|
||
|
|
min_r = min(r for r, _ in self._letters)
|
||
|
|
max_r = max(r for r, _ in self._letters)
|
||
|
|
min_c = min(c for _, c in self._letters)
|
||
|
|
max_c = max(c for _, c in self._letters)
|
||
|
|
height = max_r - min_r + 1
|
||
|
|
width = max_c - min_c + 1
|
||
|
|
|
||
|
|
# Re-base coordinates to (0, 0)
|
||
|
|
shifted = [
|
||
|
|
PlacedWord(
|
||
|
|
word=pw.word, clue=pw.clue,
|
||
|
|
row=pw.row - min_r, col=pw.col - min_c,
|
||
|
|
direction=pw.direction,
|
||
|
|
)
|
||
|
|
for pw in self.placed
|
||
|
|
]
|
||
|
|
|
||
|
|
# Dense cell grid
|
||
|
|
grid: list[list[Cell]] = [
|
||
|
|
[Cell() for _ in range(width)] for _ in range(height)
|
||
|
|
]
|
||
|
|
for pw in shifted:
|
||
|
|
for i, (r, c) in enumerate(pw.cells()):
|
||
|
|
grid[r][c].letter = pw.word[i]
|
||
|
|
|
||
|
|
# Assign clue numbers in reading order
|
||
|
|
starts: dict[tuple[int, int], list[PlacedWord]] = {}
|
||
|
|
for pw in shifted:
|
||
|
|
starts.setdefault((pw.row, pw.col), []).append(pw)
|
||
|
|
|
||
|
|
across_clues: list[NumberedClue] = []
|
||
|
|
down_clues: list[NumberedClue] = []
|
||
|
|
num = 1
|
||
|
|
|
||
|
|
for r in range(height):
|
||
|
|
for c in range(width):
|
||
|
|
if (r, c) not in starts:
|
||
|
|
continue
|
||
|
|
grid[r][c].number = num
|
||
|
|
for pw in starts[(r, c)]:
|
||
|
|
pw.number = num
|
||
|
|
nc = NumberedClue(num, pw.clue, pw.word, pw.direction)
|
||
|
|
if pw.direction == Direction.ACROSS:
|
||
|
|
across_clues.append(nc)
|
||
|
|
else:
|
||
|
|
down_clues.append(nc)
|
||
|
|
num += 1
|
||
|
|
|
||
|
|
return Crossword(
|
||
|
|
grid=grid,
|
||
|
|
placed_words=shifted,
|
||
|
|
across_clues=across_clues,
|
||
|
|
down_clues=down_clues,
|
||
|
|
width=width,
|
||
|
|
height=height,
|
||
|
|
)
|
||
|
|
|
||
|
|
|
||
|
|
# ---------------------------------------------------------------------------
|
||
|
|
# Public API
|
||
|
|
# ---------------------------------------------------------------------------
|
||
|
|
|
||
|
|
_PLACEMENT_PASSES = 4
|
||
|
|
|
||
|
|
|
||
|
|
def _build_once(valid: list[WordClue], grid_size: int) -> _GridBuilder:
|
||
|
|
"""Run one placement attempt and return the builder."""
|
||
|
|
builder = _GridBuilder(grid_size)
|
||
|
|
|
||
|
|
first = valid[0]
|
||
|
|
start_row = grid_size // 2
|
||
|
|
start_col = (grid_size - len(first.word)) // 2
|
||
|
|
builder.place(first.word, first.clue, start_row, start_col,
|
||
|
|
Direction.ACROSS)
|
||
|
|
|
||
|
|
# Multiple passes — each pass the grid has grown, opening new slots
|
||
|
|
remaining = list(valid[1:])
|
||
|
|
for _ in range(_PLACEMENT_PASSES):
|
||
|
|
still: list[WordClue] = []
|
||
|
|
for wc in remaining:
|
||
|
|
pos = builder.find_best(wc.word)
|
||
|
|
if pos:
|
||
|
|
builder.place(wc.word, wc.clue, *pos)
|
||
|
|
else:
|
||
|
|
still.append(wc)
|
||
|
|
if not still:
|
||
|
|
break
|
||
|
|
remaining = still
|
||
|
|
|
||
|
|
return builder
|
||
|
|
|
||
|
|
|
||
|
|
def generate_crossword(
|
||
|
|
word_clues: list[WordClue],
|
||
|
|
grid_size: int = 15,
|
||
|
|
rng: Optional[random.Random] = None,
|
||
|
|
) -> Optional[Crossword]:
|
||
|
|
"""Generate a single crossword puzzle from *word_clues*.
|
||
|
|
|
||
|
|
Words longer than *grid_size* are silently skipped. When *rng* is
|
||
|
|
provided, multiple orderings are tried and the best result is kept.
|
||
|
|
Returns None if fewer than two words could be placed.
|
||
|
|
"""
|
||
|
|
if not word_clues:
|
||
|
|
return None
|
||
|
|
|
||
|
|
valid: list[WordClue] = []
|
||
|
|
for wc in word_clues:
|
||
|
|
if len(wc.word) > grid_size:
|
||
|
|
logger.warning("Word %r (%d chars) exceeds grid size %d, skipping.",
|
||
|
|
wc.word, len(wc.word), grid_size)
|
||
|
|
else:
|
||
|
|
valid.append(wc)
|
||
|
|
|
||
|
|
if not valid:
|
||
|
|
return None
|
||
|
|
|
||
|
|
attempts = 4 if rng else 1
|
||
|
|
best_builder: Optional[_GridBuilder] = None
|
||
|
|
|
||
|
|
for _ in range(attempts):
|
||
|
|
# Sort longest-first, then shuffle within same-length groups
|
||
|
|
valid.sort(key=lambda wc: (-len(wc.word), rng.random() if rng else 0))
|
||
|
|
|
||
|
|
builder = _build_once(valid, grid_size)
|
||
|
|
if best_builder is None or len(builder.placed) > len(best_builder.placed):
|
||
|
|
best_builder = builder
|
||
|
|
|
||
|
|
if len(builder.placed) == len(valid):
|
||
|
|
break # perfect — no need to try again
|
||
|
|
|
||
|
|
assert best_builder is not None
|
||
|
|
unplaced = set(wc.word for wc in valid) - {pw.word for pw in best_builder.placed}
|
||
|
|
if unplaced:
|
||
|
|
logger.info("Could not place %d word(s): %s",
|
||
|
|
len(unplaced), ", ".join(sorted(unplaced)))
|
||
|
|
|
||
|
|
crossword = best_builder.build()
|
||
|
|
if crossword.word_count < 2:
|
||
|
|
logger.warning("Only %d word(s) placed — puzzle too small.",
|
||
|
|
crossword.word_count)
|
||
|
|
return None
|
||
|
|
|
||
|
|
return crossword
|
||
|
|
|
||
|
|
|
||
|
|
def generate_batch(
|
||
|
|
word_clues: list[WordClue],
|
||
|
|
count: int = 20,
|
||
|
|
words_per_puzzle: int = 20,
|
||
|
|
grid_size: int = 15,
|
||
|
|
seed: Optional[int] = None,
|
||
|
|
min_density: float = 0.10,
|
||
|
|
max_retries: int = 5,
|
||
|
|
) -> list[Crossword]:
|
||
|
|
"""Generate *count* crossword puzzles by sampling from *word_clues*.
|
||
|
|
|
||
|
|
For each puzzle the word pool is shuffled (using *seed* for
|
||
|
|
reproducibility), a batch of *words_per_puzzle* is drawn, and
|
||
|
|
`generate_crossword` is called. If the result doesn't meet quality
|
||
|
|
thresholds the batch is re-shuffled and retried up to *max_retries*
|
||
|
|
times.
|
||
|
|
"""
|
||
|
|
if len(word_clues) < 3:
|
||
|
|
logger.error("Need at least 3 words to generate puzzles, got %d.",
|
||
|
|
len(word_clues))
|
||
|
|
return []
|
||
|
|
|
||
|
|
rng = random.Random(seed)
|
||
|
|
words = list(word_clues)
|
||
|
|
puzzles: list[Crossword] = []
|
||
|
|
min_placed = max(2, int(words_per_puzzle * 0.4))
|
||
|
|
|
||
|
|
for puzzle_idx in range(count):
|
||
|
|
best: Optional[Crossword] = None
|
||
|
|
|
||
|
|
for attempt in range(max_retries):
|
||
|
|
rng.shuffle(words)
|
||
|
|
batch = words[:words_per_puzzle]
|
||
|
|
candidate = generate_crossword(batch, grid_size, rng)
|
||
|
|
|
||
|
|
if candidate and (best is None
|
||
|
|
or candidate.word_count > best.word_count):
|
||
|
|
best = candidate
|
||
|
|
|
||
|
|
if best and best.word_count >= min_placed and best.density >= min_density:
|
||
|
|
puzzles.append(best)
|
||
|
|
logger.info("Puzzle %d: %d words placed, density %.1f%%.",
|
||
|
|
puzzle_idx + 1, best.word_count,
|
||
|
|
best.density * 100)
|
||
|
|
else:
|
||
|
|
logger.warning(
|
||
|
|
"Failed to generate puzzle %d after %d attempts.",
|
||
|
|
puzzle_idx + 1, max_retries)
|
||
|
|
|
||
|
|
return puzzles
|
||
|
|
|
||
|
|
|
||
|
|
# ---------------------------------------------------------------------------
|
||
|
|
# Debug helper
|
||
|
|
# ---------------------------------------------------------------------------
|
||
|
|
|
||
|
|
def format_grid(crossword: Crossword) -> str:
|
||
|
|
"""Return a human-readable text rendering of the grid."""
|
||
|
|
lines: list[str] = []
|
||
|
|
for row in crossword.grid:
|
||
|
|
parts: list[str] = []
|
||
|
|
for cell in row:
|
||
|
|
if cell.is_empty:
|
||
|
|
parts.append("██")
|
||
|
|
else:
|
||
|
|
parts.append(f" {cell.letter}")
|
||
|
|
lines.append("".join(parts))
|
||
|
|
return "\n".join(lines)
|