Как решить популярную в 2022 головоломку Wordle на Python
Слышали об игре Wordle? Её простота обманчива. Надо отгадывать английские слова из пяти букв. Если слово не отгадано, даются подсказки: цвет ячейки с буквой становится зелёным, если угадано его место в слове; жёлтым, если она есть в слове, но в другом месте; и серым, если её в слове нет. Кажется, это просто просто, а всё-таки сложно! Напишем решатель задач для Wordle. Понадобятся абстракции множества, генераторы списков на Python и немного удачи! Чтобы было проще, далее цвет фона будем считать цветом буквы.
Задача
Каждый день в Wordle генерируется новое слово. У нас только шесть попыток, а на сайте для отслеживания прогресса используются куки — так что выбираем тщательно! Но, похоже, здесь есть подсказки:
Пишем решатель задач Wordle на Python.
- Слово состоит из пяти английских букв.
- Нет никаких знаков препинания, цифр и других символов.
- После каждой попытки даются подсказки:
- Фон за буквой становится зелёным, если символ и его место в слове угаданы.
- Фон становится жёлтым, если символ есть в слове, но в другом месте.
- Фон за буквой серый, если символа в слове нет.
- Число допустимых слов ограничено словарём Wordle.
Воспользоваться именно им было бы слишком просто, лучше взять бесплатный словарь Linux здесь: /usr/share/dict/american-english. На каждую его строку приходится одно слово.
Загрузка и генерирование слов
Сначала берём словарь. Вы можете выбрать свой. Код описывает правила игры:
import string DICT = "/usr/share/dict/american-english" ALLOWABLE_CHARACTERS = set(string.ascii_letters) ALLOWED_ATTEMPTS = 6 WORD_LENGTH = 5
Всего шесть попыток, длина слова — пять (букв), используем все доступные символы алфавита.
Преобразуем допустимые в set() символы, чтобы применять функционал множеств в части проверок принадлежности. Подробнее об этом позже. Генерируем множество слов, которые соответствуют правилам игры:
from pathlib import Path
WORDS = {
word.lower()
for word in Path(DICT).read_text().splitlines()
if len(word) == WORD_LENGTH and set(word) < ALLOWABLE_CHARACTERS
}
Чтобы создать множество допустимых слов, здесь используем абстракцию множества, а также класс Path, чтобы считывать данные прямо из файла. Рекомендую ознакомиться с Path: у него отличный функционал.
Фильтруем словарные слова, чтобы остались только слова с нужной длиной и символами, принадлежащими подмножеству ALLOWABLE_CHARACTERS. Из словаря выбираются лишь те слова, которые можно написать, используя множество допустимых символов.
Частотный анализ английского алфавита
Особенность английского языка — неравномерное распределение букв в словах. Например, буква E используется чаще, чем X. Поэтому генерируем слова с самыми частотными буквами — так больше шансов найти в Wordle соответствие символам слова. Выигрышная стратегия состоит в том, чтобы создать систему, которая вернёт самые частотные буквы английского языка. Со словарём это будет проще!
from collections import Counter from itertools import chain LETTER_COUNTER = Counter(chain.from_iterable(WORDS))
Класс Counter — это словарь с подсчётом элементов. Когда в него передаются значения, они отслеживаются как ключи. При этом сохраняется количество вхождений, то есть значений этих ключей. Эту частотность букв и нужно задействовать в задаче.
Для этого воспользуемся функцией chain из модуля itertools. В ней есть скрытый метод from_iterable, который принимает один итерируемый объект и оценивает его как длинную цепочку таких объектов. Пример поможет разобраться:
>>> list(chain.from_iterable(["inspired", "python"])) ['i', 'n', 's', 'p', 'i', 'r', 'e', 'd', 'p', 'y', 't', 'h', 'o', 'n']
Строки — это тоже итерируемые объекты, а WORDS — это множество таких строк, поэтому разбиваем множество (или список и т. д.) на составляющие их символы. Этим и полезны строки: передаём их через set, чтобы получить уникальные символы в слове:
>>> set("hello")
{'e', 'h', 'l', 'o'}
- Множества моделируются в своих математических собратьях с тем же именем, содержат только уникальные значения — без повторов — и неупорядочены.
Поэтому порядок следования множества символов иной, нежели в строке. У множеств обширный функционал, например проверка подмножества (полностью ли одно множество содержится в другом), получение элементов, которые перекрывают два множества (пересечение), объединение двух множеств и т. д.
Итак, буквы подсчитаны:
>>> LETTER_COUNTER
Counter({'h': 828,
'o': 1888,
'n': 1484,
'e': 3106,
's': 2954,
'v': 338,
# ... etc ...
})
Но это даёт лишь абсолютное число символов. Лучше разбить его на процент общего количества. Для этого используем метод total в классе Counter, дающий общее количество вхождений букв.
Переведём это количество в таблицу частотности:
LETTER_FREQUENCY = {
character: value / LETTER_COUNTER.total()
for character, value in LETTER_COUNTER.items()
}
В Python 3.10 появился метод Counter.total(), поэтому если вы работаете со старым Python, то можете заменить его на sum(LETTER_COUNTER.values()).
Здесь применяем генератор словарей, чтобы перечислить каждый ключ и значение нового, считающего словаря LETTER_COUNTER, и делим каждое значение на общее количество:
>>> LETTER_FREQUENCY
{'h': 0.02804403048264183,
'o': 0.06394580863674852,
'n': 0.050262489415749366,
'e': 0.10519898391193903,
's': 0.10005080440304827,
# ... etc ...
}
Получилась идеальная система подсчёта частотности букв, использующая подмножество словаря. Причём взят не весь словарь, а только части с допустимыми в Wordle словами. Вряд ли это очень повлияет на оценки, но теперь у нас есть множество слов, которые мы используем.
Нужно взвесить каждое слово, чтобы предлагать самого вероятного кандидатов. Берём таблицу частотности и создаём функцию подсчёта слов, чтобы оценить частоту букв в слове:
def calculate_word_commonality(word):
score = 0.0
for char in word:
score += LETTER_FREQUENCY[char]
return score / (WORD_LENGTH - len(set(word)) + 1)
Снова используем строку как итерируемый объект, перебирая каждый символ в слове. Получаем частоту каждого слова, прибавляем её, общее количество делим на длину слова минус число уникальных символов (и плюс один, чтобы избежать деления на ноль).
Это функция подсчёта и взвешивания слов проста: более редким символам слова присваивается больший вес. В идеале нужно как можно больше уникальных и частотных символов, чтобы максимизировать вероятность попаданий в зелёный или жёлтый цвета в Wordle.
Быстрый тест подтверждает: слова с редкими и повторяющимися символами имеют меньший вес, чем с частотными и ещё более редкими:
>>> calculate_word_commonality("fuzzy")
0.04604572396274344
>>> calculate_word_commonality("arose")
0.42692633361558
Теперь нам нужен способ сортировать и показывать эти слова:
import operator
def sort_by_word_commonality(words):
sort_by = operator.itemgetter(1)
return sorted(
[(word, calculate_word_commonality(word)) for word in words],
key=sort_by,
reverse=True,
)
def display_word_table(word_commonalities):
for (word, freq) in word_commonalities:
print(f"{word:<10} | {freq:<5.2}")
С помощью sort_by_word_commonality генерируем отсортированный (в порядке убывания) список кортежей со словом и его оценкой в каждом из них. Ключ сортировки — оценка.
Чтобы получить первый элемент, проще вместо лямбда-выражения использовать operator.itemgetter.
Добавим также функцию быстрого отображения, чтобы перевести слова с оценками в простую табличную форму. Переходим к решателю задач.
Пишем решатель задач для Wordle
Для простого консольного приложения используем функции input() и print():
def input_word():
while True:
word = input("Input the word you entered> ")
if len(word) == WORD_LENGTH and word.lower() in WORDS:
break
return word.lower()
def input_response():
print("Type the color-coded reply from Wordle:")
print(" G for Green")
print(" Y for Yellow")
print(" ? for Gray")
while True:
response = input("Response from Wordle> ")
if len(response) == WORD_LENGTH and set(response) <= {"G", "Y", "?"}:
break
else:
print(f"Error - invalid answer {response}")
return response
Его функционал прост. Запрашиваем у пользователя слово WORD_LENGTH, данное в Wordle, и пишем ответ от Wordle. Вариантов ответа три (зелёный, жёлтый и серый), поэтому кодируем его простой строкой из трёх символов: G, Y и ?.
Я также добавил обработку ошибок на случай, если пользователь ошибся при вводе. Цикл продолжается, пока н задана правильная последовательность. Я снова преобразую входные данные в множество, а затем проверяю, является ли это множество пользовательских данных подмножеством допустимых ответов.
Фильтрация зелёных, жёлтых и серых букв с помощью вектора слов
Согласно правилам, буква становится зелёной, если она и её место в слове угаданы, жёлтой, если она есть в слове, но в другом месте, и серой, если её в слове нет. Есть и другая интерпретация правил: пока в Wordle не указано, какие буквы зелёные, жёлтые или серые, возможно всё:
word_vector = [set(string.ascii_lowercase) for _ in range(WORD_LENGTH)]
Здесь создаём список множеств, причём его размер равен длине слова, то есть 5. Каждый элемент — это множество всех строчных английских символов. Выполнив цикл для каждого множества, удаляем символы по мере исключения их слова:
- Зелёные буквы ограничены только этой буквой.
- То есть, если зелёная — вторая буква в слове, меняем множество, чтобы на месте второй буквы оказалась только эта буква.
- Жёлтые буквы означают дополнение этой буквы.
- То есть на этом месте могут быть все буквы, кроме этой. Удаление буквы из множества на этом месте гарантирует: мы не сможем выбрать слова, в которых значение этой буквы — [именно] этот символ.
- Серые буквы означают исключение этой буквы из вектора.
- То есть этот символ удаляется из всех множеств в векторе слов.
Теперь нужна функция, чтобы определить, соответствует ли слово вектору слов. Вот простая и удобная:
def match_word_vector(word, word_vector):
assert len(word) == len(word_vector)
for letter, v_letter in zip(word, word_vector):
if letter not in v_letter:
return False
return True
В этом подходе используется zip для попарного сопоставления каждого символа в слове и векторе слов (если они есть).
Если буквы нет в множестве вектора слов на этом месте, выходим без найденного соответствия. В противном случае продолжаем и, если выйдем из цикла штатно, вернётся True, указывающее на найденное соответствие.
Сопоставление слов
Реализовав правила, напишем функцию поиска, в которой список слов фильтруется с учётом ответов, получаемых от Wordle:
def match(word_vector, possible_words):
return [word for word in possible_words if match_word_vector(word, word_vector)]
В средстве сопоставления всё рассмотренное выше объединяется в едином генераторе списков, где выполняется проверка. Каждое слово проверяется на соответствие word_vector с использованием match_word_vector.
Итерирование ответа
Теперь нужен небольшой пользовательский интерфейс, чтобы многократно запрашивать искомый ответ:
def solve():
possible_words = WORDS.copy()
word_vector = [set(string.ascii_lowercase) for _ in range(WORD_LENGTH)]
for attempt in range(1, ALLOWED_ATTEMPTS + 1):
print(f"Attempt {attempt} with {len(possible_words)} possible words")
display_word_table(sort_by_word_commonality(possible_words)[:15])
word = input_word()
response = input_response()
for idx, letter in enumerate(response):
if letter == "G":
word_vector[idx] = {word[idx]}
elif letter == "Y":
try:
word_vector[idx].remove(word[idx])
except KeyError:
pass
elif letter == "?":
for vector in word_vector:
try:
vector.remove(word[idx])
except KeyError:
pass
possible_words = match(word_vector, possible_words)
Большая часть приведённых выше настроек выполняется в функции решателя. После чего переходим в цикле к ALLOWED_ATTEMPTS + 1 и показываем каждую попытку с возможным числом оставшихся слов. Затем вызываем display_word_table, чтобы распечатать красивую таблицу с 15 соответствиями, имеющими наибольшие оценки. Затем запрашиваем слово и получаемый на него ответ от Wordle.
Перечисляем ответ, запоминая место каждой буквы. Код прост: сопоставляем каждый из трёх символов ответа с соответствующим контейнером (зелёный с word_vector и т. д.) и применяем правила.
Наконец, переопределяем possible_words с помощью нового списка соответствий из match и повторяем цикл, отображая уже меньшее подмножество.
Попробуйте:
Ответы соответствуют запросам, переданным в решатель задач. Запускаем его, вызывая solve() (для краткости часть выходных данных опущена):
>>> Attempt 1 with 5905 possible words arose | 0.43 raise | 0.42 ... etc ... Input the word you entered> arose Type the color-coded reply from Wordle: G for Green Y for Yellow ? for Gray Response from Wordle> ?Y??Y Attempt 2 with 829 possible words liter | 0.34 liner | 0.34 ... etc ... Input the word you entered> liter Response from Wordle> ???YY Attempt 3 with 108 possible words nerdy | 0.29 nehru | 0.28 ... etc ... Input the word you entered> nerdy Response from Wordle> ?YY?G Attempt 4 with 25 possible words query | 0.24 chewy | 0.21 ... etc ... Input the word you entered> query Response from Wordle> GGGGG Attempt 5 with 1 possible words query | 0.24
Заключение
- Абстракции множества, генераторы списков, словарей и т. д. — это мощные инструменты Python, сочетающие обход цикла и фильтрацию. Но перестараться с ними в циклах for или операторах if — значит затруднить восприятие кода. Ограничьтесь несколькими for и if.
- Множества — одно из главных преимуществ Python.
- Умение своевременно применять принадлежность множеству делает код более стабильным, математически корректным и лаконичным. Здесь оно используется очень эффективно — не пренебрегайте множествами!
- Задействовать пространство поиска в полной мере позволяют регулярные выражения.
- Лучше всего им удаётся нахождение соответствия (или несоответствия) символов. Хотя здесь ещё есть что изучать: подумайте, как переписать средство сопоставления и преобразование слов в векторную форму, используя регулярные выражения.
- В модулях itertools и collections есть полезные вспомогательные средства.
- С простым Python вам многое по плечу, если уметь использовать встроенные модули. itertools особенно хорош для ленивого или итеративного вычисления значений.