Алгоритм Word Hunt DFS не находит оптимального решения
Я пытаюсь написать алгоритм для игры Word Hunt на Iphone Game Pigeon.
Как работает поиск слов: Каждому игроку предоставляется сетка с буквами 4х4. Каждый игрок должен составлять слова из трех или более букв, соединяя буквы, расположенные рядом друг с другом по горизонтали, вертикали или диагонали. Как только буква используется в цепочке, одну и ту же плитку нельзя использовать снова. Большее количество баллов присуждается за более длинные слова.
Я написал следующий код для алгоритма, но, похоже, он не находит максимально длинные слова:
import os
import time
def read_grid():
grid = []
for i in range(4):
i += 1
row = input(f"Enter row {i} (4 letters): ").strip().lower()
if len(row) != 4 or not row.isalpha():
raise ValueError("Each row must contain exactly 4 letters.")
grid.append(list(row))
return grid
def read_word_list(file_path):
file_path = os.path.expanduser("~/Self Projects/Word Hunt/word_list.txt")
with open(file_path, 'r') as file:
words = set(word.strip().lower() for word in file if len(word.strip()) >= 3)
return words
def find_words(grid, word_list):
def dfs(x, y, path, current_word):
if not (0 <= x < 4 and 0 <= y < 4):
return
if (x, y) in path:
return
current_word += grid[x][y]
if len(current_word) >= 3 and current_word in word_list:
found_words.add(current_word)
path.add((x, y))
for dx, dy in [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]:
dfs(x + dx, y + dy, path.copy(), current_word)
path.remove((x, y))
found_words = set()
for i in range(4):
for j in range(4):
dfs(i, j, set(), "")
return found_words
def word_hunt_solver(grid, word_list):
possible_words = find_words(grid, word_list)
sorted_words = sorted(possible_words, key=lambda word: (-len(word), word))
return sorted_words[:100]
grid = read_grid()
start_time = time.time()
word_list = read_word_list('word_list.txt')
longest_words = word_hunt_solver(grid, word_list)
longest_words.reverse()
for word in longest_words:
print(word)
print("\n")
print("\n")
print(f"Program Execution Time: {time.time() - start_time}")
Словарный файл, который я использую: https://drive.google.com/file/d/1oGDf1wjWp5RF_X9C7HoedhIWMh5uJs8s/view
Например, если я ввожу в сетку:
adul
aret
tion
sing
самые длинные найденные слова
adulterising
adulteration
adulterating
тогда как «фальсификации» — допустимое слово, и оно длиннее. Другой пример: если я ввожу сетку:
unfo
vigr
ingn
esst
самые длинные найденные слова
forgiving
fogginess
unforgiving
когда «непрощение» — допустимое длинное слово. Похоже, что алгоритм пропускает не только самое длинное слово, но и множество промежуточных слов. Полный вывод для приведенной выше сетки:
vis
vin
vig
vie
uni
sin
sen
sei
org
orf
nis
nie
ins
ing
igg
gor
gnu
gin
gig
gif
fro
for
fog
fin
fig
ess
ens
eng
vise
vins
vine
vigs
vies
snig
sins
sing
sine
sien
sens
orgs
nine
nies
ness
ings
ingo
info
iggs
grog
gins
ging
gigs
frog
fins
fini
fine
figs
figo
engs
visne
vines
vigor
snigs
snies
sings
siens
sengi
oggin
nines
ivies
gings
finis
fines
vining
unfine
sining
oggins
gneiss
giving
singing
seining
givings
forging
ungiving
forgings
forgiving
fogginess
unforgiving
что вовсе не кажется оптимальным из-за количества трех- и четырехбуквенных слов, которые, казалось бы, не должны входить в 100 самых длинных слов.
Вы используете ложную логику, позволяя себе начинать слева в последней строке. Вы не следуете правилам, а следуете тому, чему вас научили в школе: читайте форму слева направо :-)
Теперь я чувствую себя глупо, лол. Спасибо вам, ребята :)
Ответы 1
С точки зрения результата ваш алгоритм работает правильно. Он возвращает ожидаемые результаты. Однако с точки зрения производительности он довольно медленный. Попробуем оптимизировать его.
Если вы прекратите копирование объекта пути, производительность улучшится почти вдвое. Копировать сейчас нет смысла, координата будет удалена после выполнения цикла.
Просто замените эту строку кода:
dfs(x + dx, y + dy, path.copy(), current_word)
С этим.
dfs(x + dx, y + dy, path, current_word)
Результат функции не изменится, производительность значительно увеличится.
Однако я предложу вам свое решение, которое возвращает те же результаты, но алгоритм поиска работает мгновенно.
Первое, что изменилось — это обработка файлов. Мы собираем не только возможные слова, но и все возможные фрагменты, которые мы можем получить для определенного слова. Это понадобится при поиске, чтобы мы могли быстро отсеять бесперспективные слова.
def read_word_list(filepath):
# add additional logic here if necessary
possible_chunks = set()
possible_words = set()
with open(filepath) as file:
for line in file.readlines():
word = line.strip().lower()
if len(word) >= 3:
possible_words.add(word)
for index in range(len(word), -1, -1):
chunk = word[:index]
if chunk in possible_chunks:
break
possible_chunks.add(chunk)
return possible_chunks, possible_words
Эта функция требует больше всего времени для выполнения сценария, поскольку файл очень большой и содержит много слов. На моем компьютере это занимает около 0,3 секунды.
Теперь перейдем к основному изменению.
from functools import cache
MOVES = (
(-1, -1),
(-1, 0),
(-1, 1),
(0, -1),
(0, 1),
(1, -1),
(1, 0),
(1, 1),
)
def find_words(grid, possible_chunks, possible_words):
@cache
def find_neighbors(x, y):
neighbors = set()
for dx, dy in MOVES:
nx, ny = dx + x, dy + y
if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]):
neighbors.add((nx, ny))
return neighbors
def iter_search(x, y, word):
for nx, ny in find_neighbors(x, y):
if (nx, ny) in visited:
continue
next_letter = grid[nx][ny]
next_word = word + next_letter
if next_word not in possible_chunks:
continue
if next_word in possible_words:
yield next_word
visited.add((nx, ny))
yield from iter_search(nx, ny, next_word)
visited.remove((nx, ny))
result = set()
visited = set()
initial = (
(i, j, l) for i, line in enumerate(grid) for j, l in enumerate(line)
)
for i, j, letter in initial:
visited = {(i, j)}
result.update(iter_search(i, j, letter))
return result
Здесь я добавил кеширование соседних координат, с ним оно работает немного быстрее. Однако главное изменение — if next_word not in possible_chunks: continue, оно позволяет нам пропустить дальнейшую работу над бесперспективным словом, которое со временем не принесет желаемого результата. Скорость выполнения на моем компьютере 0,003–0,005 секунды.
Если у вас есть вопросы, напишите мне. Попробую дополнить ответ.
спасибо за помощь, я бы даже не подумал сделать это таким образом!
ни «фальсификации», ни «непрощение» не могут быть сформированы с помощью соответствующих решеток.