406 lines
14 KiB
Python
406 lines
14 KiB
Python
from __future__ import annotations
|
|
|
|
from dataclasses import dataclass
|
|
import sys
|
|
import time
|
|
from typing import Dict, Iterable, List, Optional, Sequence, Set, Tuple
|
|
|
|
|
|
Coordinate = Tuple[int, int]
|
|
Grid = Dict[Coordinate, str]
|
|
|
|
|
|
WORDS = [
|
|
"automobile",
|
|
"re",
|
|
"magia",
|
|
"montagna",
|
|
"principe",
|
|
"ambiente",
|
|
"per",
|
|
"calcio",
|
|
"pesce",
|
|
"cane",
|
|
"vedere",
|
|
"finestra",
|
|
"ancora",
|
|
"altro",
|
|
"volta",
|
|
"atleta",
|
|
"sempre",
|
|
"nuovo",
|
|
"libro",
|
|
]
|
|
|
|
|
|
HORIZONTAL = "H"
|
|
VERTICAL = "V"
|
|
DIFFXY = 7
|
|
|
|
|
|
@dataclass(frozen=True)
|
|
class Placement:
|
|
word: str
|
|
x: int
|
|
y: int
|
|
direction: str
|
|
intersections: int
|
|
|
|
@property
|
|
def cells(self) -> List[Coordinate]:
|
|
if self.direction == HORIZONTAL:
|
|
return [(self.x + offset, self.y) for offset in range(len(self.word))]
|
|
return [(self.x, self.y + offset) for offset in range(len(self.word))]
|
|
|
|
|
|
@dataclass
|
|
class CrosswordState:
|
|
grid: Grid
|
|
placements: List[Placement]
|
|
intersections: int
|
|
|
|
def copy(self) -> "CrosswordState":
|
|
return CrosswordState(
|
|
grid=dict(self.grid),
|
|
placements=list(self.placements),
|
|
intersections=self.intersections,
|
|
)
|
|
|
|
@property
|
|
def placed_words(self) -> int:
|
|
return len(self.placements)
|
|
|
|
def bounds(self) -> Tuple[int, int, int, int]:
|
|
xs = [x for x, _ in self.grid]
|
|
ys = [y for _, y in self.grid]
|
|
return min(xs), min(ys), max(xs), max(ys)
|
|
|
|
def area(self) -> int:
|
|
x_min, y_min, x_max, y_max = self.bounds()
|
|
return (x_max - x_min + 1) * (y_max - y_min + 1)
|
|
|
|
def width(self) -> int:
|
|
x_min, _, x_max, _ = self.bounds()
|
|
return x_max - x_min + 1
|
|
|
|
def height(self) -> int:
|
|
_, y_min, _, y_max = self.bounds()
|
|
return y_max - y_min + 1
|
|
|
|
def shape_difference(self) -> int:
|
|
return abs(self.width() - self.height())
|
|
|
|
def score(self, diffxy: int) -> Tuple[int, int, int, int, int]:
|
|
# Prefer valid shapes first; within those, maximize placed words and intersections,
|
|
# then prefer squarer and more compact grids.
|
|
is_shape_valid = 1 if self.shape_difference() <= diffxy else 0
|
|
return (
|
|
is_shape_valid,
|
|
self.placed_words,
|
|
self.intersections,
|
|
-self.shape_difference(),
|
|
-self.area(),
|
|
)
|
|
|
|
|
|
class CrosswordGenerator:
|
|
def __init__(
|
|
self,
|
|
words: Sequence[str],
|
|
*,
|
|
max_candidates_per_word: int = 12,
|
|
time_limit_seconds: float = 8.0,
|
|
diffxy: int = DIFFXY,
|
|
) -> None:
|
|
normalized = [self._normalize(word) for word in words]
|
|
unique_words = list(dict.fromkeys(word for word in normalized if len(word) >= 2))
|
|
self.words = sorted(unique_words, key=lambda word: (-len(word), word))
|
|
self.best_state = CrosswordState(grid={}, placements=[], intersections=0)
|
|
self.max_candidates_per_word = max_candidates_per_word
|
|
self.time_limit_seconds = time_limit_seconds
|
|
self.diffxy = diffxy
|
|
self.started_at = 0.0
|
|
self.visited: Dict[Tuple[frozenset, Tuple[str, ...]], Tuple[int, int, int]] = {}
|
|
self.nodes_visited = 0
|
|
self.spinner_frames = ["-", "/", "|", "\\"]
|
|
self.spinner_index = 0
|
|
self.last_spinner_update = 0.0
|
|
|
|
@staticmethod
|
|
def _normalize(word: str) -> str:
|
|
return word.strip().lower()
|
|
|
|
@staticmethod
|
|
def _step(direction: str) -> Coordinate:
|
|
return (1, 0) if direction == HORIZONTAL else (0, 1)
|
|
|
|
@staticmethod
|
|
def _perpendicular(direction: str) -> Coordinate:
|
|
return (0, 1) if direction == HORIZONTAL else (1, 0)
|
|
|
|
@staticmethod
|
|
def _build_letter_index(words: Sequence[str]) -> Dict[str, Set[str]]:
|
|
index: Dict[str, Set[str]] = {}
|
|
for word in words:
|
|
for letter in set(word):
|
|
index.setdefault(letter, set()).add(word)
|
|
return index
|
|
|
|
def solve(self) -> CrosswordState:
|
|
if not self.words:
|
|
return self.best_state
|
|
|
|
self.started_at = time.perf_counter()
|
|
self.last_spinner_update = self.started_at
|
|
self.nodes_visited = 0
|
|
first_word = self.words[0]
|
|
initial_state = self._place_first_word(first_word)
|
|
self.best_state = initial_state
|
|
remaining = [word for word in self.words if word != first_word]
|
|
self._search(initial_state, remaining)
|
|
self._clear_spinner()
|
|
return self.best_state
|
|
|
|
def _place_first_word(self, word: str) -> CrosswordState:
|
|
grid = {(offset, 0): letter for offset, letter in enumerate(word)}
|
|
placement = Placement(word=word, x=0, y=0, direction=HORIZONTAL, intersections=0)
|
|
return CrosswordState(grid=grid, placements=[placement], intersections=0)
|
|
|
|
def _search(self, state: CrosswordState, remaining_words: Sequence[str]) -> None:
|
|
self.nodes_visited += 1
|
|
self._tick_spinner(state)
|
|
|
|
if time.perf_counter() - self.started_at > self.time_limit_seconds:
|
|
return
|
|
|
|
if state.score(self.diffxy) > self.best_state.score(self.diffxy):
|
|
self.best_state = state.copy()
|
|
|
|
if not remaining_words:
|
|
return
|
|
|
|
if state.placed_words + len(remaining_words) < self.best_state.placed_words:
|
|
return
|
|
|
|
if state.placed_words + len(remaining_words) == self.best_state.placed_words:
|
|
max_possible_intersections = state.intersections + sum(len(word) for word in remaining_words)
|
|
if max_possible_intersections <= self.best_state.intersections:
|
|
return
|
|
|
|
signature = (frozenset(state.grid.items()), tuple(sorted(remaining_words)))
|
|
best_seen = self.visited.get(signature)
|
|
current_score = state.score(self.diffxy)
|
|
if best_seen is not None and best_seen >= current_score:
|
|
return
|
|
self.visited[signature] = current_score
|
|
|
|
next_word = self._select_next_word(state, remaining_words)
|
|
candidates = self._generate_candidates(state, next_word)
|
|
|
|
if not candidates:
|
|
self._search(state, [word for word in remaining_words if word != next_word])
|
|
return
|
|
|
|
candidates.sort(
|
|
key=lambda placement: (
|
|
placement.intersections,
|
|
len(placement.word),
|
|
-self._candidate_area_after(state, placement),
|
|
),
|
|
reverse=True,
|
|
)
|
|
candidates = candidates[: self.max_candidates_per_word]
|
|
|
|
next_remaining = [word for word in remaining_words if word != next_word]
|
|
for placement in candidates:
|
|
child_state = self._apply_placement(state, placement)
|
|
self._search(child_state, next_remaining)
|
|
|
|
# Also explore skipping the current word, but only after trying all placements.
|
|
self._search(state, next_remaining)
|
|
|
|
def _tick_spinner(self, state: CrosswordState) -> None:
|
|
now = time.perf_counter()
|
|
if now - self.last_spinner_update < 0.08:
|
|
return
|
|
|
|
frame = self.spinner_frames[self.spinner_index]
|
|
elapsed = now - self.started_at
|
|
message = (
|
|
f"\r{frame} elaborazione... "
|
|
f"nodi={self.nodes_visited} "
|
|
f"migliore={self.best_state.placed_words} parole, {self.best_state.intersections} incroci, diff={self.best_state.shape_difference()} "
|
|
f"attuale={state.placed_words} parole, diff={state.shape_difference()} "
|
|
f"t={elapsed:0.1f}s"
|
|
)
|
|
print(message, end="", file=sys.stderr, flush=True)
|
|
self.spinner_index = (self.spinner_index + 1) % len(self.spinner_frames)
|
|
self.last_spinner_update = now
|
|
|
|
@staticmethod
|
|
def _clear_spinner() -> None:
|
|
print("\r" + " " * 120 + "\r", end="", file=sys.stderr, flush=True)
|
|
|
|
def _select_next_word(self, state: CrosswordState, remaining_words: Sequence[str]) -> str:
|
|
ranked_words = sorted(
|
|
remaining_words,
|
|
key=lambda word: (
|
|
-sum(1 for letter in set(word) if letter in state.grid.values()),
|
|
-len(word),
|
|
word,
|
|
),
|
|
)
|
|
|
|
best_word = ranked_words[0]
|
|
best_key: Optional[Tuple[int, int, int, str]] = None
|
|
for word in ranked_words[:5]:
|
|
candidate_count = len(self._generate_candidates(state, word))
|
|
key = (
|
|
0 if candidate_count > 0 else 1,
|
|
candidate_count if candidate_count > 0 else 10**9,
|
|
-len(word),
|
|
word,
|
|
)
|
|
if best_key is None or key < best_key:
|
|
best_key = key
|
|
best_word = word
|
|
return best_word
|
|
|
|
def _generate_candidates(self, state: CrosswordState, word: str) -> List[Placement]:
|
|
if not state.grid:
|
|
return [Placement(word=word, x=0, y=0, direction=HORIZONTAL, intersections=0)]
|
|
|
|
candidates: Dict[Tuple[int, int, str], Placement] = {}
|
|
for index, letter in enumerate(word):
|
|
for x, y in self._cells_with_letter(state.grid, letter):
|
|
for direction in (HORIZONTAL, VERTICAL):
|
|
start_x = x - index if direction == HORIZONTAL else x
|
|
start_y = y if direction == HORIZONTAL else y - index
|
|
placement = self._validate_placement(state.grid, word, start_x, start_y, direction)
|
|
if placement is None:
|
|
continue
|
|
candidates[(placement.x, placement.y, placement.direction)] = placement
|
|
return list(candidates.values())
|
|
|
|
@staticmethod
|
|
def _cells_with_letter(grid: Grid, letter: str) -> Iterable[Coordinate]:
|
|
for coordinate, grid_letter in grid.items():
|
|
if grid_letter == letter:
|
|
yield coordinate
|
|
|
|
def _validate_placement(
|
|
self,
|
|
grid: Grid,
|
|
word: str,
|
|
start_x: int,
|
|
start_y: int,
|
|
direction: str,
|
|
) -> Optional[Placement]:
|
|
dx, dy = self._step(direction)
|
|
pdx, pdy = self._perpendicular(direction)
|
|
intersections = 0
|
|
|
|
before = (start_x - dx, start_y - dy)
|
|
after = (start_x + dx * len(word), start_y + dy * len(word))
|
|
if before in grid or after in grid:
|
|
return None
|
|
|
|
for offset, letter in enumerate(word):
|
|
x = start_x + dx * offset
|
|
y = start_y + dy * offset
|
|
current = grid.get((x, y))
|
|
|
|
if current is not None:
|
|
if current != letter:
|
|
return None
|
|
intersections += 1
|
|
continue
|
|
|
|
side_a = (x + pdx, y + pdy)
|
|
side_b = (x - pdx, y - pdy)
|
|
if side_a in grid or side_b in grid:
|
|
return None
|
|
|
|
if intersections == 0 and grid:
|
|
return None
|
|
|
|
return Placement(
|
|
word=word,
|
|
x=start_x,
|
|
y=start_y,
|
|
direction=direction,
|
|
intersections=intersections,
|
|
)
|
|
|
|
def _apply_placement(self, state: CrosswordState, placement: Placement) -> CrosswordState:
|
|
child = state.copy()
|
|
dx, dy = self._step(placement.direction)
|
|
for offset, letter in enumerate(placement.word):
|
|
x = placement.x + dx * offset
|
|
y = placement.y + dy * offset
|
|
child.grid[(x, y)] = letter
|
|
child.placements.append(placement)
|
|
child.intersections += placement.intersections
|
|
return child
|
|
|
|
def _candidate_area_after(self, state: CrosswordState, placement: Placement) -> int:
|
|
xs = [x for x, _ in state.grid]
|
|
ys = [y for _, y in state.grid]
|
|
pxs = [x for x, _ in placement.cells]
|
|
pys = [y for _, y in placement.cells]
|
|
if not xs:
|
|
return len(placement.word)
|
|
x_min = min(min(xs), min(pxs))
|
|
x_max = max(max(xs), max(pxs))
|
|
y_min = min(min(ys), min(pys))
|
|
y_max = max(max(ys), max(pys))
|
|
return (x_max - x_min + 1) * (y_max - y_min + 1)
|
|
|
|
|
|
def render_grid(grid: Grid, placements: Sequence[Placement]) -> str:
|
|
if not grid:
|
|
return "(griglia vuota)"
|
|
|
|
x_min = min(x for x, _ in grid)
|
|
x_max = max(x for x, _ in grid)
|
|
y_min = min(y for _, y in grid)
|
|
y_max = max(y for _, y in grid)
|
|
|
|
header = " " + " ".join(f"{x:>2}" for x in range(x_min, x_max + 1))
|
|
separator = " " + " ".join("--" for _ in range(x_min, x_max + 1))
|
|
lines = [header]
|
|
lines.append(separator)
|
|
for y in range(y_min, y_max + 1):
|
|
row = [f"{y:>3} "]
|
|
for x in range(x_min, x_max + 1):
|
|
row.append(grid.get((x, y), ".").upper().rjust(2))
|
|
lines.append(" ".join(row))
|
|
|
|
lines.append("")
|
|
lines.append("Parole inserite:")
|
|
for index, placement in enumerate(sorted(placements, key=lambda item: (item.y, item.x, item.direction)), start=1):
|
|
direction = "orizzontale" if placement.direction == HORIZONTAL else "verticale"
|
|
lines.append(
|
|
f"{index:>2}. {placement.word.upper():<12} ({placement.x:>2}, {placement.y:>2}) {direction}, "
|
|
f"intersezioni: {placement.intersections}"
|
|
)
|
|
return "\n".join(lines)
|
|
|
|
|
|
def main() -> None:
|
|
generator = CrosswordGenerator(WORDS)
|
|
solution = generator.solve()
|
|
|
|
print("Miglior soluzione trovata")
|
|
print(f"Parole inserite: {solution.placed_words}/{len(generator.words)}")
|
|
print(f"Intersezioni totali: {solution.intersections}")
|
|
print(f"Dimensioni: {solution.width()} colonne x {solution.height()} righe")
|
|
print(f"Differenza righe/colonne: {solution.shape_difference()} (vincolo DIFFXY={generator.diffxy})")
|
|
print(f"Area occupata: {solution.area()}")
|
|
print()
|
|
print(render_grid(solution.grid, solution.placements))
|
|
|
|
|
|
if __name__ == "__main__":
|
|
main()
|