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