Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Letter frequencies for word lengths and positions in word solution in Clear category for Crossword Solver by cerankas
from collections import defaultdict
class Crossing:
def __init__(self, pos, index, other_index, other_posdir):
self.pos = pos
self.index = index
self.other_index = other_index
self.other_posdir = other_posdir
def __repr__(self):
return f'({self.pos},{self.index},{self.other_index},{self.other_posdir})'
class Field:
def __init__(self, row, col, hor, length):
self.posdir = (row, col, hor)
self.row = row
self.col = col
self.hor = hor
self.length = length
self.crossings: list[Crossing] = []
self.word = ''
def __repr__(self):
return f'({self.posdir},{self.length},{str(self.crossings)})'
def contains(self, row, col):
if self.hor == 0 and self.col == col and self.row <= row < self.row + self.length: return True
if self.hor == 1 and self.row == row and self.col <= col < self.col + self.length: return True
return False
def letter_positions(self):
return [(self.row + i * (1 - self.hor), self.col + i * self.hor) for i in range(self.length)]
def solver(crossword, words):
numrows = len(crossword)
numcols = len(crossword[0])
# separate words by length
len_words = {l:[word for word in words if len(word) == l] for l in range(3,11)}
# calculate letter frequencies in words of given length, at given positions
len_pos_letter_freqs = defaultdict(lambda:defaultdict(lambda:defaultdict(int)))
for length in len_words:
for word in len_words[length]:
for i, char in enumerate(word):
len_pos_letter_freqs[length][i][char] += 1
# get length of field starting at (row, col), horizontal or vertical
def field_length(row, col, hor):
if crossword[row][col] == 'X': return 0
if hor == 0 and row and crossword[row - 1][col] == '.': return 0
if hor == 1 and col and crossword[row][col - 1] == '.': return 0
length = 1
while row + length * (1 - hor) < numrows and col + length * hor < numcols and crossword[row + length * (1 - hor)][col + length * hor] == '.':
length += 1
return length if length > 1 else 0
# find fields
fields: dict[tuple[int,int,int], Field] = {}
for row in range(numrows):
for col in range(numcols):
for dir in [0, 1]:
if (length := field_length(row, col, dir)):
field = Field(row, col, dir, length)
fields[field.posdir] = field
# find field crossings
for field in fields.values():
for field2 in fields.values():
if field != field2:
for index, pos in enumerate(field.letter_positions()):
for index2, pos2 in enumerate(field2.letter_positions()):
if pos == pos2:
field.crossings.append(Crossing(pos, index, index2, field2.posdir))
sorted_fields = sorted(fields.values(), key=lambda field: -len(field.crossings))
# fill words into crossword
all_crossings = defaultdict(str) # letters at all crossing in the crossword
result = [list(row) for row in crossword] # result, as lists if single letters
def fill(field_list: list[Field], crossed: int):
if field_list: # fields list not yet exhausted, process
field = field_list[0]
crossings = field.crossings
if crossed < len(crossings): # not all crossings of this field are checked/filled
crossing = crossings[crossed]
if all_crossings[crossing.pos]: # this crossing is already filled
if fill(field_list, crossed + 1): return True
else: # this crossing is not yet filled
field2 = fields[crossing.other_posdir]
letters = []
letter_freqs1 = len_pos_letter_freqs[field.length][crossing.index]
letter_freqs2 = len_pos_letter_freqs[field2.length][crossing.other_index]
for letter in letter_freqs1:
if letter in letter_freqs2:
# for each possible letter, store (letter, product), where
# product = number of matching horizotal words * number of matching veritical words
letters.append((letter, letter_freqs1[letter] * letter_freqs2[letter]))
letters.sort(key=lambda item:-item[1])
for letter,_ in letters:
all_crossings[crossing.pos] = letter
if fill(field_list, crossed + 1): return True
all_crossings[crossing.pos] = ''
else: # all crossings of this field are checked/filled, now fit a word in this field
letters = [(crossing.index, all_crossings[crossing.pos]) for crossing in crossings]
for word in len_words[field.length]:
if any(field.word == word for field in sorted_fields): continue
if all(word[index] == letter for index, letter in letters):
field.word = word
if fill(field_list[1:], 0): return True
field.word = ''
return False
else: # fields list exhausted, crossword filled!
for field in fields.values():
for letter, pos in zip(field.word, field.letter_positions()):
result[pos[0]][pos[1]] = letter
return True
fill(sorted_fields, 0)
return [''.join(row) for row in result]
Sept. 2, 2023
Comments:
