Spaces:
Running
Running
| from __future__ import annotations | |
| import random | |
| import hashlib # NEW | |
| from typing import Dict, List, Optional, Union # UPDATED | |
| from .word_loader import load_word_list | |
| from .models import Coord, Word, Puzzle | |
| def _fits_and_free(cells: List[Coord], used: set[Coord], size: int) -> bool: | |
| for c in cells: | |
| if not c.in_bounds(size) or c in used: | |
| return False | |
| return True | |
| def _build_cells(start: Coord, length: int, direction: str) -> List[Coord]: | |
| if direction == "H": | |
| return [Coord(start.x, start.y + i) for i in range(length)] | |
| else: | |
| return [Coord(start.x + i, start.y) for i in range(length)] | |
| def _chebyshev_distance(a: Coord, b: Coord) -> int: | |
| return max(abs(a.x - b.x), abs(a.y - b.y)) | |
| def _seed_from_id(puzzle_id: str) -> int: | |
| """Derive a deterministic 64-bit seed from a string id.""" | |
| h = hashlib.sha256(puzzle_id.encode("utf-8")).digest() | |
| return int.from_bytes(h[:8], "big", signed=False) | |
| def generate_puzzle( | |
| grid_size: int = 12, | |
| words_by_len: Optional[Dict[int, List[str]]] = None, | |
| seed: Optional[Union[int, str]] = None, | |
| max_attempts: int = 5000, | |
| spacer: int = 1, | |
| puzzle_id: Optional[str] = None, # NEW | |
| _retry: int = 0, # NEW internal for deterministic retries | |
| target_words: Optional[List[str]] = None, # NEW: for loading shared games | |
| may_overlap: bool = False, # NEW: for future crossword-style gameplay | |
| ) -> Puzzle: | |
| """ | |
| Place exactly six words: 2x4, 2x5, 2x6, horizontal or vertical, | |
| no cell overlaps. Radar pulses are last-letter cells. | |
| Ensures the same word text is not selected more than once. | |
| Parameters | |
| - grid_size: grid dimension (default 12) | |
| - words_by_len: preloaded word pools by length | |
| - seed: optional RNG seed | |
| - max_attempts: cap for placement attempts before restarting | |
| - spacer: separation constraint between different words (0–2 supported) | |
| - 0: words may touch | |
| - 1: at least 1 blank tile between words (default) | |
| - 2: at least 2 blank tiles between words | |
| - target_words: optional list of exactly 6 words to use (for shared games) | |
| - may_overlap: whether words can overlap (default False, for future use) | |
| Determinism: | |
| - If puzzle_id is provided, it's used to derive the RNG seed. Retries use f"{puzzle_id}:{_retry}". | |
| - Else if seed is provided (int or str), it's used (retries offset deterministically). | |
| - Else RNG is non-deterministic as before. | |
| """ | |
| # Compute deterministic seed if requested | |
| if puzzle_id is not None: | |
| seed_val = _seed_from_id(f"{puzzle_id}:{_retry}") | |
| elif isinstance(seed, str): | |
| seed_val = _seed_from_id(f"{seed}:{_retry}") | |
| elif isinstance(seed, int): | |
| seed_val = seed + _retry | |
| else: | |
| seed_val = None | |
| rng = random.Random(seed_val) if seed_val is not None else random.Random() | |
| # If target_words is provided, use those specific words | |
| if target_words: | |
| if len(target_words) != 6: | |
| raise ValueError(f"target_words must contain exactly 6 words, got {len(target_words)}") | |
| # Group target words by length | |
| pools: Dict[int, List[str]] = {} | |
| for word in target_words: | |
| L = len(word) | |
| if L not in pools: | |
| pools[L] = [] | |
| pools[L].append(word.upper()) | |
| target_lengths = sorted([len(w) for w in target_words]) | |
| else: | |
| # Normal random word selection | |
| words_by_len = words_by_len or load_word_list() | |
| target_lengths = [4, 4, 5, 5, 6, 6] | |
| # Pre-shuffle the word pools for variety but deterministic with seed. | |
| pools: Dict[int, List[str]] = {} | |
| for L in (4, 5, 6): | |
| unique_words = list(dict.fromkeys(words_by_len.get(L, []))) | |
| rng.shuffle(unique_words) | |
| pools[L] = unique_words | |
| used: set[Coord] = set() | |
| used_texts: set[str] = set() | |
| placed: List[Word] = [] | |
| attempts = 0 | |
| for L in target_lengths: | |
| placed_ok = False | |
| pool = pools[L] | |
| if not pool: | |
| raise RuntimeError(f"No words available for length {L}") | |
| word_try_order = pool[:] # copy | |
| rng.shuffle(word_try_order) | |
| for cand_text in word_try_order: | |
| if attempts >= max_attempts: | |
| break | |
| attempts += 1 | |
| if cand_text in used_texts: | |
| continue | |
| for _ in range(50): | |
| direction = rng.choice(["H", "V"]) | |
| if direction == "H": | |
| row = rng.randrange(0, grid_size) | |
| col = rng.randrange(0, grid_size - L + 1) | |
| else: | |
| row = rng.randrange(0, grid_size - L + 1) | |
| col = rng.randrange(0, grid_size) | |
| cells = _build_cells(Coord(row, col), L, direction) | |
| if _fits_and_free(cells, used, grid_size): | |
| w = Word(cand_text, Coord(row, col), direction) | |
| placed.append(w) | |
| used.update(cells) | |
| used_texts.add(cand_text) | |
| try: | |
| pool.remove(cand_text) | |
| except ValueError: | |
| pass | |
| placed_ok = True | |
| break | |
| if placed_ok: | |
| break | |
| if not placed_ok: | |
| # Hard reset and retry whole generation if we hit a wall | |
| if attempts >= max_attempts: | |
| raise RuntimeError("Puzzle generation failed: max attempts reached") | |
| return generate_puzzle( | |
| grid_size=grid_size, | |
| words_by_len=words_by_len, | |
| seed=rng.randrange(1 << 30), | |
| max_attempts=max_attempts, | |
| spacer=spacer, | |
| ) | |
| puzzle = Puzzle(words=placed, spacer=spacer, may_overlap=may_overlap) | |
| try: | |
| validate_puzzle(puzzle, grid_size=grid_size) | |
| except AssertionError: | |
| # Deterministic retry on validation failure | |
| # Regenerate on validation failure (e.g., spacer rule violation) | |
| return generate_puzzle( | |
| grid_size=grid_size, | |
| words_by_len=words_by_len, | |
| seed=seed, | |
| max_attempts=max_attempts, | |
| spacer=spacer, | |
| puzzle_id=puzzle_id, | |
| _retry=_retry + 1, | |
| ) | |
| return puzzle | |
| def validate_puzzle(puzzle: Puzzle, grid_size: int = 12) -> None: | |
| # Bounds and overlap checks | |
| seen: set[Coord] = set() | |
| counts: Dict[int, int] = {4: 0, 5: 0, 6: 0} | |
| for w in puzzle.words: | |
| if len(w.text) not in (4, 5, 6): | |
| raise AssertionError("Word length invalid") | |
| counts[len(w.text)] += 1 | |
| for c in w.cells: | |
| if not c.in_bounds(grid_size): | |
| raise AssertionError("Cell out of bounds") | |
| if c in seen: | |
| raise AssertionError("Overlapping words detected") | |
| seen.add(c) | |
| # Last cell must match radar pulse for that word | |
| if w.last_cell not in puzzle.radar: | |
| raise AssertionError("Radar pulse missing for last cell") | |
| if counts[4] != 2 or counts[5] != 2 or counts[6] != 2: | |
| raise AssertionError("Incorrect counts of word lengths") | |
| # Enforce spacer rule (supports 0–2). Default spacer is 1 (from models.Puzzle). | |
| spacer_val = getattr(puzzle, "spacer", 1) | |
| if spacer_val in (1, 2): | |
| word_cells = [set(w.cells) for w in puzzle.words] | |
| for i in range(len(word_cells)): | |
| for j in range(i + 1, len(word_cells)): | |
| for c1 in word_cells[i]: | |
| for c2 in word_cells[j]: | |
| if _chebyshev_distance(c1, c2) <= spacer_val: | |
| raise AssertionError(f"Spacing violation (spacer={spacer_val}): {c1} vs {c2}") | |
| def sort_word_file(filepath: str) -> List[str]: | |
| """ | |
| Reads a word list file, skips header/comment lines, and returns words sorted | |
| by length (ascending), then alphabetically within each length group. | |
| """ | |
| with open(filepath, "r", encoding="utf-8") as f: | |
| lines = f.readlines() | |
| # Skip header/comment lines | |
| words = [line.strip() for line in lines if line.strip() and not line.strip().startswith("#")] | |
| # Sort by length, then alphabetically | |
| sorted_words = sorted(words, key=lambda w: (len(w), w)) | |
| return sorted_words |