К старту курса по Fullstack-разработке на Python рассказываем, как решать Wordle. Worlde — новая головоломка, которая захватила внимание множества людей по всему миру. За подробностями приглашаем под кат.

Слышали об игре Wordle? Её простота обманчива. Надо отгадывать английские слова из пяти букв. Если слово не отгадано, даются подсказки: цвет ячейки с буквой становится зелёным, если угадано его место в слове; жёлтым, если она есть в слове, но в другом месте; и серым, если её в слове нет. Кажется, это просто просто, а всё-таки сложно! Напишем решатель задач для Wordle. Понадобятся абстракции множества, генераторы списков на Python и немного удачи! Чтобы было проще, далее цвет фона будем считать цветом буквы.

Задача

Каждый день в Wordle генерируется новое слово. У нас только шесть попыток, а на сайте для отслеживания прогресса используются куки — так что выбираем тщательно! Но, похоже, здесь есть подсказки:

Пишем решатель задач Wordle на Python.

1. Слово состоит из пяти английских букв.

2. Нет никаких знаков препинания, цифр и других символов.

3. После каждой попытки даются подсказки:

1. Фон за буквой становится зелёным, если символ и его место в слове угаданы.

2. Фон становится жёлтым, если символ есть в слове, но в другом месте.

3. Фон за буквой серый, если символа в слове нет.

4. Число допустимых слов ограничено словарём 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 особенно хорош для ленивого или итеративного вычисления значений.

Продолжить изучение Python вы сможете на наших курсах:

• Профессия Fullstack-разработчик на Python

• Профессия Data Scientist

Узнайте подробности здесь.