crosswords/server/crossword_generator.py

883 lines
28 KiB
Python

# load stuff
import json
import random
import numpy as np
from string import digits, ascii_lowercase
import pathlib
import logging
def get_difficulty_threshold(lang: str, difficulty: int):
return get_difficulty_threshold.thresholds[lang][difficulty]
get_difficulty_threshold.thresholds = {
'de': {
0: 5,
1: 3,
2: 1
},
'en': {
0: 5,
1: 3,
2: 1
},
'hp': {
0: 0,
1: 0,
2: 0
}
}
def get_database(lang: str = "en", difficulty: int = -1) -> dict:
if lang not in get_database._dbs:
try:
file = __file__
except:
file = "./.tmp"
current_folder = pathlib.Path(file).parents[0]
db_file = str(current_folder / f"{lang}.json")
logging.info("loading database: %s", lang)
with open(db_file, "r") as f:
db = json.load(f)
get_database._dbs[lang] = {}
get_database._dbs[lang][-1] = db
logging.info("database loaded")
if difficulty not in get_database._dbs[lang]:
t = get_difficulty_threshold(lang, difficulty)
logging.info(
"generate sub database for lang %s with difficulty %s", lang, str(difficulty))
db = get_database._dbs[lang][-1]
new_db = {}
for word_key, item in db.items():
frequency = item['frequency']
if frequency >= t:
new_db[word_key] = item
get_database._dbs[lang][difficulty] = new_db
return get_database._dbs[lang][difficulty]
get_database._dbs = {}
def build_inverted_index(db):
inverted_db = {}
inverted_db['#'] = {}
number_db = inverted_db['#']
for letter in ascii_lowercase:
inverted_db[letter] = {}
for key, item in db.items():
try:
word = item['word']
norm_word = normalize_word(word)
n = len(norm_word)
if norm_word.isalnum():
for i, letter in enumerate(norm_word):
letter_db = inverted_db[letter]
if i not in letter_db:
letter_db[i] = {}
letter_db_i = letter_db[i]
if n not in letter_db_i:
letter_db_i[n] = []
if n not in number_db:
number_db[n] = []
letter_db_i[n].append(key)
number_db[n].append(key)
except:
pass
#print("error processing " + word)
return inverted_db
def get_inverted_database(lang: str, difficulty: int = -1) -> dict:
if lang not in get_inverted_database._dbs:
get_inverted_database._dbs[lang] = {}
if difficulty not in get_inverted_database._dbs[lang]:
get_inverted_database._dbs[lang][difficulty] = build_inverted_index(
get_database(lang, difficulty))
return get_inverted_database._dbs[lang][difficulty]
get_inverted_database._dbs = {}
remove_digits = str.maketrans('', '', digits)
def normalize_word(word: str):
word = word.translate(remove_digits)
return word.lower()
def find_suitable_words(constraints: list, db: dict, inverted_db: dict):
sets = []
n = len(constraints)
for i, letter in enumerate(constraints):
if letter == ' ':
continue
letter_db = inverted_db[letter]
if i in letter_db:
i_list = letter_db[i]
if not n in i_list:
return set()
sets.append(set(i_list[n]))
else:
return set()
# at least one constraint must be set
if len(sets) == 0:
# set first letter random and try again
if n in inverted_db['#']:
return inverted_db['#'][n]
return set()
return set.intersection(*sets)
class NoDataException(Exception):
pass
class WordInfo(object):
def __init__(self, word: str, y: int, x: int, is_vertical: bool, database: dict, opposite_prefix: str = "opposite of", synonym_prefix: str = "other word for"):
self._dictionary_database = database
self._y = y
self._x = x
self._word = word
self._hint = None
self._is_vertical = is_vertical
self.opposite_prefix = opposite_prefix
self.synonym_prefix = synonym_prefix
self.choose_info()
def get_attribute(self, attr: str):
attr = self._dictionary_database[self._word][attr]
if attr is None or len(attr) == 0:
raise NoDataException
return attr
def get_best_antonym(self) -> str:
antonyms = self.get_attribute("antonyms")
return random.choice(antonyms)
def get_best_synonym(self) -> str:
synonyms = self.get_attribute("synonyms")
return random.choice(synonyms)
def get_best_sense(self) -> str:
senses = self.get_attribute("senses")
return random.choice(senses)
def choose_info(self, n: int = 1):
assert n <= 4
# first choose antonyms, then synonyms, then senses
hints = []
try:
antonyms = self.get_attribute("antonyms")
antonyms = [f"{self.opposite_prefix} {w}" for w in antonyms]
hints = hints + antonyms
except NoDataException:
pass
try:
synonyms = self.get_attribute("synonyms")
synonyms = [f"{self.synonym_prefix} {w}" for w in synonyms]
hints = hints + synonyms
except NoDataException:
pass
try:
senses = self.get_attribute("senses")
hints = hints + senses
except NoDataException:
pass
final_hints = []
for i in range(n):
choice = random.choice(hints)
hints.remove(choice)
final_hints.append(choice)
if n == 1:
self._hint = final_hints[0]
return
hint_symbols = ['a)', 'b)', 'c)', 'd)']
self._hint = ""
for i in range(n):
self._hint += hint_symbols[i] + " " + final_hints[i] + ". "
def get_hint(self) -> str:
return self._hint
def get_hint_location(self):
x = self._x if self._is_vertical else self._x - 1
y = self._y - 1 if self._is_vertical else self._y
return (y, x)
def is_vertical(self):
return self._is_vertical
TYPE_EMPTY = -1
TYPE_NEIGHBOR = -2
TYPE_BLOCKED = -3
class GridCreationWord(object):
def __init__(self, y: int, x: int, length: int, is_vertical: bool, id: int) -> None:
self.y = y
self.x = x
self.length = length
self.is_vertical = is_vertical
self.id = id
self.word_key = None
self.connected_words = []
def get_letters(self, letter_grid: np.ndarray) -> list:
if self.is_vertical:
return letter_grid[self.y:self.y+self.length, self.x].flatten()
return letter_grid[self.y, self.x: self.x + self.length].flatten()
def write(self, word: str, letter_grid: np.ndarray, x_grid: np.ndarray, y_grid: np.ndarray):
letters = list(word)
if self.is_vertical:
xmin = max(self.x - 1, 0)
xmax = min(self.x + 2, letter_grid.shape[1])
ymin = self.y
ymax = self.y + self.length
letter_grid[ymin:ymax, self.x] = letters
conflicts = np.argwhere(
x_grid[ymin:ymax, self.x] == TYPE_NEIGHBOR
)
if len(conflicts) > 0:
corrected_conflicts = np.zeros(
shape=(len(conflicts), 2), dtype=np.int)
corrected_conflicts[:, 0] = ymin + conflicts.flatten()
corrected_conflicts[:, 1] = self.x
conflicts = corrected_conflicts
x_neighbors = x_grid[ymin:ymax, xmin:xmax]
x_neighbors[x_neighbors == TYPE_EMPTY] = TYPE_NEIGHBOR
x_grid[ymin:ymax, xmin:xmax] = x_neighbors
x_grid[ymin:ymax, self.x] = self.id
fields_to_block = y_grid[ymin:ymax, self.x]
fields_to_block[fields_to_block < 0] = TYPE_BLOCKED
y_grid[ymin:ymax, self.x] = fields_to_block
if ymin > 0:
x_grid[ymin - 1, self.x] = TYPE_BLOCKED
y_grid[ymin - 1, self.x] = TYPE_BLOCKED
if ymax < letter_grid.shape[0]:
x_grid[ymax, self.x] = TYPE_BLOCKED
y_grid[ymax, self.x] = TYPE_BLOCKED
else:
xmin = self.x
xmax = self.x + self.length
ymin = max(self.y - 1, 0)
ymax = min(self.y + 2, letter_grid.shape[0])
letter_grid[self.y, xmin:xmax] = letters
conflicts = np.argwhere(
y_grid[self.y, xmin:xmax] == TYPE_NEIGHBOR,
)
if len(conflicts) > 0:
corrected_conflicts = np.zeros(
shape=(len(conflicts), 2), dtype=np.int)
corrected_conflicts[:, 1] = xmin + conflicts.flatten()
corrected_conflicts[:, 0] = self.y
conflicts = corrected_conflicts
y_neighbors = y_grid[ymin:ymax, xmin:xmax]
y_neighbors[y_neighbors == TYPE_EMPTY] = TYPE_NEIGHBOR
y_grid[ymin:ymax, xmin:xmax] = y_neighbors
fields_to_block = x_grid[self.y, xmin:xmax]
fields_to_block[fields_to_block < 0] = TYPE_BLOCKED
x_grid[self.y, xmin:xmax] = fields_to_block
y_grid[self.y, xmin:xmax] = self.id
if xmin > 0:
x_grid[self.y, xmin - 1] = TYPE_BLOCKED
y_grid[self.y, xmin - 1] = TYPE_BLOCKED
if xmax < letter_grid.shape[1]:
x_grid[self.y, xmax] = TYPE_BLOCKED
y_grid[self.y, xmax] = TYPE_BLOCKED
return conflicts
def set_word_key(self, word_key: str):
self.word_key = word_key
def connect_word(self, grid_word):
self.connected_words.append(grid_word)
def get_connected_words(self):
return self.connected_words
def check_connected(self, grid_word):
if self.is_vertical == grid_word.is_vertical:
return False
if self.is_vertical:
if self.y > grid_word.y:
return False
if self.y + self.length <= grid_word.y:
return False
if self.x >= grid_word.x + grid_word.length:
return False
if self.x < grid_word.x:
return False
else:
if self.x > grid_word.x:
return False
if self.x + self.length <= grid_word.x:
return False
if self.y >= grid_word.y + grid_word.length:
return False
if self.y < grid_word.y:
return False
return True
class GridCreationState(object):
def __init__(self, h: int, w: int, db, inverted_db, old_state=None) -> None:
if old_state is not None:
self.h = h
self.w = w
self.db = db
self.inverted_db = inverted_db
self.x_grid = old_state.x_grid.copy()
self.y_grid = old_state.y_grid.copy()
self.letter_grid = old_state.letter_grid.copy()
self.placed_words = old_state.placed_words.copy()
self.used_word_keys = old_state.used_word_keys.copy()
return
self.h = h
self.w = w
self.x_grid = np.full(shape=(h, w), dtype=np.int,
fill_value=TYPE_EMPTY)
self.y_grid = np.full(shape=(h, w), dtype=np.int,
fill_value=TYPE_EMPTY)
self.letter_grid = np.full(
shape=(h, w), dtype=np.unicode, fill_value=' ')
self.placed_words = []
self.used_word_keys = set()
self.db = db
self.inverted_db = inverted_db
def write_word(self, word_key: str, y: int, x: int, is_vertical: bool):
id = len(self.placed_words)
word_raw = self.db[word_key]['word']
word_normalized = normalize_word(word_raw)
grid_word = GridCreationWord(y=y,
x=x,
length=len(word_normalized),
is_vertical=is_vertical, id=id)
grid_word.set_word_key(word_key=word_key)
conflicts = grid_word.write(word=word_normalized,
letter_grid=self.letter_grid,
x_grid=self.x_grid,
y_grid=self.y_grid)
self.placed_words.append(grid_word)
self.used_word_keys.add(word_key)
return conflicts
def copy(self):
return GridCreationState(self.h, self.w, self.db, self.inverted_db, self)
def get_density(self):
blocked_fields_x = np.logical_or(
self.x_grid >= 0, self.x_grid == TYPE_BLOCKED)
blocked_fields_y = np.logical_or(
self.y_grid >= 0, self.y_grid == TYPE_BLOCKED)
blocked_fields = np.logical_or(blocked_fields_x, blocked_fields_y)
return np.sum(blocked_fields) / (self.w * self.h)
def get_letters(self, y: int, x: int, length: int, is_vertical: bool):
if is_vertical:
return self.letter_grid[y:y+length, x].flatten()
return self.letter_grid[y, x:x+length].flatten()
def get_max_extents(self, y: int, x: int, is_vertical: bool):
# check min max offsets
if is_vertical:
min_coord = y - 1
if min_coord < 0 or self.y_grid[min_coord, x] == TYPE_BLOCKED:
min_coord = y
else:
while min_coord > 0 and self.y_grid[min_coord - 1, x] != TYPE_BLOCKED:
min_coord -= 1
max_coord = y + 1
while max_coord < self.h and self.y_grid[max_coord, x] != TYPE_BLOCKED:
max_coord += 1
return min_coord, max_coord
else:
min_coord = x - 1
if min_coord < 0 or self.x_grid[y, min_coord] == TYPE_BLOCKED:
min_coord = x
else:
while min_coord > 0 and self.x_grid[y, min_coord - 1] != TYPE_BLOCKED:
min_coord -= 1
max_coord = x + 1
while max_coord < self.w and self.x_grid[y, max_coord] != TYPE_BLOCKED:
max_coord += 1
return min_coord, max_coord
def expand_coordinates(self, y: int, x: int, length: int, is_vertical: bool):
if is_vertical:
min_coord = y
max_coord = y + length
while min_coord > 0 and self.y_grid[min_coord - 1, x] >= 0:
min_coord -= 1
while max_coord < self.h and self.y_grid[max_coord, x] >= 0:
max_coord += 1
return min_coord, max_coord
else:
min_coord = x
max_coord = x + length
while min_coord > 0 and self.x_grid[y, min_coord - 1] >= 0:
min_coord -= 1
while max_coord < self.w and self.x_grid[y, max_coord] >= 0:
max_coord += 1
return min_coord, max_coord
def place_random_word(self, min_length: int = 4, max_length: int = 15):
# first, find a random intersection
letter_locations = np.argwhere(self.letter_grid != ' ')
if len(letter_locations) == 0:
# if nothing is placed so far, just choose a random place
length = np.random.randint(min_length, max_length)
length = min(length, max_length)
y = np.random.randint(0, self.h - 1)
x = np.random.randint(0, self.w - length)
is_vertical = False
word_template = " " * length
else:
# possible candidates are fields where words are placed
# only horizontally or only vertically
candidates = np.argwhere(
np.logical_xor(self.x_grid >= 0, self.y_grid >= 0)
)
if len(candidates) == 0:
#print("field is full")
return None
candidate_index = random.randint(0, len(candidates) - 1)
y, x = candidates[candidate_index]
is_vertical = self.x_grid[y, x] == TYPE_BLOCKED
min_coord, max_coord = self.get_max_extents(y, x, is_vertical)
extent = max_coord - min_coord
if extent < min_length:
#print("not enough space to place a word")
return None
min_length = min(extent, min_length)
max_length = min(extent, max_length)
length = random.randint(min_length, max_length)
offset = random.randint(0, extent - length)
min_coord += offset
if is_vertical:
if min_coord + length <= y:
min_coord = y - length + 1
max_coord = min_coord + length
if min_coord > y:
min_coord = y
max_coord = min_coord + length
min_coord, max_coord = self.expand_coordinates(y=min_coord,
x=x,
length=length,
is_vertical=is_vertical)
length = max_coord - min_coord
letters = self.get_letters(min_coord, x, length, is_vertical)
y = min_coord
else:
if min_coord + length <= x:
min_coord = x - length + 1
max_coord = min_coord + length
if min_coord > x:
min_coord = x
max_coord = min_coord + length
min_coord, max_coord = self.expand_coordinates(y=y,
x=min_coord,
length=length,
is_vertical=is_vertical)
length = max_coord - min_coord
letters = self.get_letters(y, min_coord, length, is_vertical)
x = min_coord
word_template = "".join(letters)
word_candidates = list(find_suitable_words(
word_template, self.db, self.inverted_db))
if len(word_candidates) == 0:
#print("no word available for given combination")
return None
word_candidate_index = random.randint(0, len(word_candidates) - 1)
word_key = word_candidates[word_candidate_index]
if word_key in self.used_word_keys:
return None
return self.write_word(word_key, y, x, is_vertical)
def solve_conflicts(self, conflicts, n_retries=3, max_depth=5, depth=0):
if len(conflicts) == 0:
return self
# else:
# return None
if depth > max_depth:
return None
new_conflictes = []
for conflict in conflicts:
y, x = conflict
if self.x_grid[y, x] >= 0 and self.y_grid[y, x] >= 0:
# conflict already solved
continue
# find out whether the conflict is vertical or horizontal
is_vertical = self.y_grid[y, x] == TYPE_NEIGHBOR
# calculate the minimum and maximum extend to fix the conflict
if is_vertical:
max_ymin = y
while max_ymin > 0 and self.y_grid[max_ymin-1, x] >= 0:
max_ymin -= 1
min_ymax = y + 1
while min_ymax < self.h and self.y_grid[min_ymax, x] >= 0:
min_ymax += 1
min_ymin = max_ymin
while min_ymin > 0 and self.y_grid[min_ymin - 1, x] != TYPE_BLOCKED:
min_ymin -= 1
max_ymax = min_ymax
while max_ymax < self.h and self.y_grid[max_ymax, x] != TYPE_BLOCKED:
max_ymax += 1
min_coord_min = min_ymin
max_coord_min = max_ymin
min_coord_max = min_ymax
max_coord_max = max_ymax
else:
max_xmin = x
while max_xmin > 0 and self.x_grid[y, max_xmin - 1] >= 0:
max_xmin -= 1
min_xmax = x + 1
while min_xmax < self.w and self.x_grid[y, min_xmax] >= 0:
min_xmax += 1
min_xmin = max_xmin
while min_xmin > 0 and self.x_grid[y, min_xmin - 1] != TYPE_BLOCKED:
min_xmin -= 1
max_xmax = min_xmax
while max_xmax < self.w and self.x_grid[y, max_xmax] != TYPE_BLOCKED:
max_xmax += 1
min_coord_min = min_xmin
max_coord_min = max_xmin
min_coord_max = min_xmax
max_coord_max = max_xmax
n_options = (max_coord_max - min_coord_max) * (max_coord_min - min_coord_min)
solved = False
for _ in range(int(n_options * 1.5)):
coord_min = random.randint(min_coord_min, max_coord_min)
coord_max = random.randint(min_coord_max, max_coord_max)
length = coord_max - coord_min
if length < 2:
continue
if is_vertical:
coord_min, coord_max = self.expand_coordinates(y=coord_min,
x=x,
length=length,
is_vertical=is_vertical)
length = coord_max - coord_min
y = coord_min
else:
coord_min, coord_max = self.expand_coordinates(y=y,
x=coord_min,
length=length,
is_vertical=is_vertical)
length = coord_max - coord_min
x = coord_min
letters = self.get_letters(y, x, length, is_vertical)
word_template = "".join(letters)
candidates = list(find_suitable_words(
word_template, self.db, self.inverted_db))
if len(candidates) == 0:
continue
candidate_index = random.randint(0, len(candidates) - 1)
word_key = candidates[candidate_index]
if word_key in self.used_word_keys:
continue
word_conflicts = self.write_word(word_key, y, x, is_vertical)
if len(word_conflicts) > 0:
new_conflictes.append(word_conflicts)
solved = True
break
if not solved:
return None
if len(new_conflictes) == 0:
return self
new_conflictes = np.concatenate(new_conflictes)
for _ in range(n_retries):
next_state = self.copy()
solved_state = next_state.solve_conflicts(
new_conflictes, n_retries, max_depth, depth + 1)
if solved_state is not None:
return solved_state
return None
def fill_grid(self, target_density: float = 0.6, inner_retries: int = 5, conflict_solver_depth=5, min_length: int = 4, max_length: int = 10, max_iterations: int = 1000):
i = 0
state = self.copy()
current_density = state.get_density()
while i < max_iterations and current_density < target_density:
current_density = state.get_density()
i += 1
new_state = state.copy()
# try semi-dynamic word length (try longer words at the beginning)
min_length_offset = 0
max_length_offset = 0
#min_length_offset = int((i / max_iterations) * (max_length - min_length))
#if current_density < 0.5 * target_density:
# min_length_offset = int(0.5 * (max_length - min_length) * (1 - (current_density / target_density)))
# #logging.info("mi %s",str(min_length_offset))
#if current_density > 0.9 * target_density:
# max_length_offset = - int(0.5 * (max_length - min_length) * ((current_density / target_density)))
# #logging.info("max %s",str(max_length_offset))
conflicts = new_state.place_random_word(min_length + min_length_offset, max_length + max_length_offset)
if conflicts is None:
continue
if len(conflicts) == 0:
state = new_state
if len(conflicts) > 0:
solved_state = new_state.solve_conflicts(
conflicts, inner_retries, conflict_solver_depth)
if solved_state is not None:
state = solved_state
logging.info("finished after %s iterations, with a density of %s (desired density: %s)", str(
i), str(state.get_density()), str(target_density))
return state
def create_word_grid(w: int,
h: int,
lang_code: str = "en",
target_density: float = 0.8,
difficulty: int = 0):
logging.info("generate new crossword with params: w:%s h:%s lang:%s density:%s difficulty:%s",
str(w),
str(h),
lang_code,
str(target_density),
str(difficulty))
db = get_database(lang_code, difficulty=difficulty)
inverted_db = get_inverted_database(lang_code, difficulty=difficulty)
base_grid = GridCreationState(h=h, w=w, db=db, inverted_db=inverted_db)
final_state = base_grid.fill_grid(target_density=target_density,
inner_retries=10,
conflict_solver_depth=10,
min_length=3,
max_length=int(min(w,h) * 0.6),
max_iterations=5000)
# generate word hints
word_hints = {}
opposite_prefix = "opposite of:" if lang_code == "en" else "Gegenteil von:"
synonym_prefix = "other word for:" if lang_code == "en" else "anderes Wort für:"
for placed_word in final_state.placed_words:
word_key = placed_word.word_key
word = normalize_word(db[word_key]['word'])
y = placed_word.y
x = placed_word.x
is_vertical = placed_word.is_vertical
word_info = WordInfo(word_key, y, x, is_vertical,
db, opposite_prefix, synonym_prefix)
#logging.info("word: %s, (%s,%s,%s): %s", word, str(y), str(x), str(is_vertical), word_info.get_hint())
word_hints[word_key] = word_info
# create a solution word
char_locations = {}
for char in list("abcdefghijklmnopqrstuvwxyz"):
char_locations[char] = np.argwhere(
final_state.letter_grid == char).tolist()
words = list(db.keys())
n_words = len(words)
min_solution_length = 12
max_solution_length = 30
solution_word_locations = None
while solution_word_locations is None:
random_index = random.randint(0, n_words - 1)
random_word_key = words[random_index]
random_word = db[random_word_key]['word']
normalized_random_word = normalize_word(random_word)
if len(normalized_random_word) < min_solution_length or len(normalized_random_word) > max_solution_length:
continue
char_locations_copy = {}
for char in char_locations:
char_locations_copy[char] = char_locations[char].copy()
solution = []
aborted = False
for char in list(normalized_random_word):
if char not in char_locations_copy:
aborted = True
break
locations = char_locations_copy[char]
if len(locations) == 0:
aborted = True
break
i = random.randint(0, len(locations) - 1)
location = locations[i]
del(locations[i])
solution.append(location)
if aborted:
continue
logging.info("solution word: %s", str(random_word))
solution_word_locations = solution
return final_state.letter_grid, word_hints, solution_word_locations