Я пишу программу для создания редких кроссвордов / анаграмм, которые должны выглядеть следующим образом:
-------------T--
-----------OGRE-
---------T---O--
--------FORGET--
---------R------
---------T------
В данном случае это слова FORGET, OGRE, TORT,и TROT. Правила для дизайна сетки примерно такие, как вы ожидаете;слова должны пересекаться на одной и той же букве, слова не могут проходить рядом друг с другом, и все поставляемые слова должны разделять подмножество некоторого набора букв. Это анаграммы.
Приведенный ниже код реализует сетку и метод для "сканирования" сетки и вставки каждого слова в первую действительную позицию. Первое слово вставлено в приблизительный центр головоломки.
К сожалению, код фактически не вставляет ничего, кроме первого слова, и я не могу понять, что не так с моей жизньюмои проверки в функции word_fits.
import enum
import io
import itertools
import math
import random
@enum.unique
class Direction(enum.Enum):
ACROSS, DOWN = enum.auto(), enum.auto()
def __str__(self):
return self.name
def get_deltas(self):
return int(self == Direction.DOWN), int(self == Direction.ACROSS)
@staticmethod
def random():
return random.choice(list(Direction))
class Grid:
def __init__(self, height = 16, width = 16):
self.width = width
self.height = height
self.grid = {r: {c: [] for c in range(width)} for r in range(height)}
self.num_words = 0
def get_letter(self, r, c):
if not self.grid[r][c]:
return []
letters = {word[offset] for (word, offset, _) in self.grid[r][c]}
assert(len(letters) == 1)
return letters.pop()
def get_words(self, r, c):
if not self.grid[r][c]:
return []
return [word for word, _, _ in self.grid[r][c]]
def approximate_center(self):
return math.floor(self.height/ 2), math.floor(self.width/ 2)
def word_fits(self, word, r, c, direction):
# Make sure we aren't inserting the word outside the grid
if ((direction == Direction.DOWN and r + len(word) >= self.height) or (direction == Direction.ACROSS and c + len(word) >= self.width)):
return False
# Otherwise we get a KeyError (for being out of bounds) when we check
# the adjacent cells later in this function
if r == 0 or c == 0 or r == self.height-1 or c == self.width-1:
return False
delta_r, delta_c = direction.get_deltas()
# Check that the word doesn't overlap any letters incorrectly
intersects = False
for offset, letter in enumerate(word):
rr = r + offset*delta_r
cc = c + offset*delta_c
other_letter = self.get_letter(rr, cc)
if other_letter:
if letter != other_letter: return False
else: intersects = True
# Check adjacent cells
for delta in [-1, 1]:
rr = r + offset*delta_r + delta*delta_c
cc = c + offset*delta_c + delta*delta_r
if self.grid[rr][cc]:
if any(direction == d for _, _, d in self.grid[rr][cc]):
return False
# if set(self.get_words(r+offset*delta_r, c+offset*delta_c)) & set(self.get_words(rr, cc)):
# return False
if offset == 0:
# delta == -1
# point directly to the left (above) a word placed across (down)
#
# delta == 1
# point directly to the right (below) a word placed across (down)
if delta == -1:
rr = r + delta*delta_r
cc = c + delta*delta_c
elif delta == 1:
rr = r + delta*len(word)*delta_r
cc = c + delta*len(word)*delta_c
if self.grid[rr][cc]:
if any(direction == d for _, _, d in self.grid[rr][cc]):
return False
return True and intersects
def insert_word(self, word, r, c, direction):
assert(isinstance(direction, Direction))
delta_r, delta_c = direction.get_deltas()
for offset, _ in enumerate(word):
self.grid[r + offset*delta_r][c + offset*delta_c].append((word.upper(), offset, direction))
self.num_words += 1
def scan_and_insert_word(self, word):
if self.num_words == 0:
self.insert_word(word, *self.approximate_center(), Direction.random())
return
for d, r, c in itertools.product(list(Direction), range(self.height), range(self.width)):
if self.word_fits(word, r, c, d):
self.insert_word(word, r, c, d)
break
raise ValueError(f""""{word}" could not be inserted.""")
def __str__(self):
output = io.StringIO()
for r in range(self.height):
for c in range(self.width):
if self.grid[r][c]:
# Checks elsewhere ensure that there are no inconsistencies
# in the letters specified by each (word, offset, direction)
# triplet, so we can just grab the first one
word, offset, _ = self.grid[r][c][0]
letter = word[offset]
else:
letter = "-"
output.write(letter)
output.write("\n")
contents = output.getvalue()
output.close()
return contents
random.seed(1)
word_list = ["FORGET", "TROT", "OGRE", "TORT"]
g = Grid()
for word in word_list:
g.scan_and_insert_word(word.upper())
print(g)
Есть много проверок, которые все еще должны быть реализованы в этом коде, например, проверка того, что все слова имеют одно и то же слово из букв N,для некоторых N, но я пытаюсь выяснить эту ошибку, прежде чем двигаться дальше.