Помощник – «решатель филвордов» на python (алгоритм поиска слов плюс распознавание текста tesseract)

Kate · 22 Сен 2021

На работе, в обеденный перерыв коллега показал игрушку на Яндекс играх – Филворды. Как то не заладилась игра у меня – вроде простые слова, но дело шло медленно. А у товарища уровень был выше 400. Первая мысль при таком фэйле – конечно, показать глупой машине, что есть кто-то умнее ее! То есть другая машина…
Дабы не бросаться на амбразуру, решил проверить, какие варианты существуют для решения филвордов. Когда попадается интересная задача, изначально стараюсь найти решение no-code, бывает, находишь элегантное решение, остается только «снять шляпу». На удивление, попались несколько вариантов составления, но, ни одного для решений филвордов. Время действовать.

Алгоритм поиска слов

Очень интересной и простой показалась задача создания алгоритма перебора всех цепочек. В основе классический алгоритм поиска пути. Первоначальное решение:

Переводим нашу таблицу букв в более понятный список.

Из каждой ячейки таблицы строить цепочки - [[0, 0], [0, 1]], [[0, 0], [1, 0]], [[0, 0], [0, 1], [0, 2]], [[0, 0], [1, 0], [2, 0]] и.т.д стартуя со всех ячеек.
Для сокращения буквенных наборов для поиска в словаре (а так же из-за того что в дальнейшем, все-равно будем разбивать длинные цепочки на наборы букв “ро, роз, роза, розас”) выбираем самые длинные цепочки и проверяем на вхождение в них коротких.
Переводим обратно цифры в буквы (как во втором пункте, но наоборот). Разбиваем цепочки на составные части “ро, роз, роза, розас”.
Для отсечения лишних наборов проверяем и отсекаем слова, в которых повторяются более 2 гласных или более 3 согласных, так же ставим ограничение на длину слова (тут здравая логика).
Проверяем полученные наборы в словаре.

Подойдя к моменту тестирования, столкнулся с тем (что и ожидалось), что при увеличении исследуемой таблицы резко возрастает время обработки (на моем «старичке» очень). Чтобы не углублять в описание O-большого, по-простому: таблица 4*4 считается порядка 20 секунд, 5*5 десятка минут, чем дальше в лес, тем еще страшнее. Решение – разделяй и властвуй. Посчитал оптимально «шагать» по исходной таблице филвордов ячейкой 4*4. Есть минус такого подхода – вероятность выпадения слов содержащих 5 букв и более, у которых 4 буквы расположены в ряд. Плюсы – стабильная скорость обработки, возможность обрабатывать не только квадратные таблицы «6*6», а и «5*25» и.т.п.
Далее постарался расписать подробно по коду (весь код сложил в один файл, чтобы было удобнее пробовать в google colab).

Настройка распознавания картинок

Чтобы каждый раз не вводить наборы букв, написал скрипт распознавания скриншота с игры и перевода полученного результата - букв, в «удобоваримый» список python. С помощь его мы получаем список, который можно поместить в скрипт (указанный выше в гугл колаб) в start_data = np.array(полученный список), для последующей препарации.
Скрипт с описанием.
Алгоритм распознавания неплохо работает со скриншотами и других игр, не только Яндекс, но нужно, чтобы буквы были темного цвета (в идеале черного) на однотонном поле.
Скрин нужно сделать с равными отступами снизу и сверху, так как далее картинка «разрезается» на равные части. Пользуюсь яндекс.диском, скрин из папки диска перекидываю сразу в рабочую папку гугла. Картинка должна выглядеть приблизительно так:

P.S.: мои первые шаги в народ, просьба сильно не бить. Учусь - ставлю задачу->читаю книгу.