Решение головоломок Wordle с помощью Basic Python

Wed, 26 Jan 2022 15:18:49 +0300

Перевод статьи “Solving Wordle Puzzles with Basic Python” автора Mickey Petersen

Вы наверняка слышали о Wordle? Это словесная головоломка не так проста, как кажется на первый взгляд. Вас просят угадать английское «слово дня», которое состоит из пяти букв. Если вы ошибетесь, вам дадут несколько подсказок: буква в слове будет зеленой, если вы правильно угадали нужную букву в нужном месте; желтой, если эта буква присутствует в слове, но не на этом месте; и серой, если буквы вообще нет в слове.

На самом деле, решать эту головоломку довольно сложно! Вот как вы можете написать Wordle Solver на Python, с использованием множеств, представления списков (list comprehension) и капелькой удачи!

Суть головоломки

Каждый день Wordle генерирует новое слово, которое нужно угадать. Поскольку у нас есть только шесть попыток — сайт использует файлы cookie для отслеживания вашего прогресса — попытки нужно использовать аккуратно!

На первый взгляд, есть несколько подсказок, которые упрощают решение:

Слово состоит ровно из пяти букв.

Слово из английского языка и использовать можно только алфавит — никаких знаков препинания, цифр или других символов.

Любая попытка дает подсказки:

Зеленая буква, если буква и её место в слове правильные.
Желтая буква, если буква присутствует в слове, но было выбрано не то место.
Серая буква, если буквы вообще нет в слове.

Существует конечное число слов, и их количество дополнительно ограничено словарем, используемым Wordle.

Поскольку я не хочу пытаться извлечь тот же словарь, что использует 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

У нас есть всего шесть попыток; длина слова равна пяти, и мы можем использовать все доступные буквы английского алфавита.

Я преобразовываю допустимые символы в Python 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
}

Здесь я использую представление списков (list comprehension) для создания множества допустимых слов. Я использую отличный класс Path для чтения непосредственно из файла. Если вы еще не знакомы с Path, я рекомендую вам узнать о нем, поскольку это очень удобный инструмент.

Так, я фильтрую слова из словаря, которые имеют правильную длину и в которых набор символов в слове является подмножеством ALLOWABLE_CHARACTERS. Другими словами, выбираются только слова, которые составлены из набора допустимых символов.

Алфавитно-частотный анализ на английского языка

Особенность английского языка заключается в неравномерном распределении букв, используемых в словах. Например, буква E используется гораздо чаще, чем X. Поэтому, если мы сможем генерировать слова с наиболее распространенными буквами, у нас больше шансов угадать некоторые или даже все буквы в слове. Таким образом, выигрышная стратегия состоит в том, чтобы придумать систему, которая вычислит наиболее популярные буквы английского языка.

К счастью, у нас есть словарь английских слов!

from collections import Counter
from itertools import chain

LETTER_COUNTER = Counter(chain.from_iterable(WORDS))

Класс Counter — полезное изобретение! Это модифицированный словарь, который считает количество повторений каждого элемента. Когда вы передаете ему список элементов, они становятся ключами, а затем он сохраняет количество появлений каждого ключа в его значение. Это как раз то, что нам нужно, чтобы посчитать популярность каждой буквы среди всех английских слов из 5 букв.

Для этого я использую малоизвестную функцию 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...
        })

Так, мы получили только абсолютное количество букв в словаре. Теперь нужно разделить его на общее количество букв, чтобы перейти к относительным величинам. К счастью, в классе Counter есть удобный метод total, который может посчитать общее количество букв всех слов словаря.

Затем составляем таблицу частот:

LETTER_FREQUENCY = {
    character: value / LETTER_COUNTER.total()
    for character, value in LETTER_COUNTER.items()
}

Метод Counter.total() был добавлен в Python 3.10, поэтому, если вы используете более старую версию Python, вы можете заменить его на sum(LETTER_COUNTER.values()), который делает то же самое.

Здесь я использую представление словарей (dictionary comprehension) для обработки каждого ключа и значения 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)]

Эта функция объединяет в себе все правила, которые мы обсудили выше, и ищет с помощью представления списков (list comprehension). Каждое слово проверяется на соответствие с word_vector с помощью match_word_vector.

Сортировка результатов

Наконец, нам нужно создать небольшой UI, который может многократно запрашивать нужный нам ответ.

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)

Функция solve() включает в себя некоторые элементы, которые мы уже обсудили. Затем попадаем в цикл от 1 до ALLOWED_ATTEMPTS + 1, и после каждой попытки мы отображаем номер текущей попытки и количество оставшихся возможных слов. Затем мы вызываем функцию display_word_table, которая выводит красивую таблицу из 15 совпадений с наибольшим рейтингом популярности слова. Затем функции нужно узнать слово, которое пользователь в итоге ввел и ответ Wordle.

После этого мы проходимся по ответу 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

Резюме

Представления (Comprehensions) — мощный инструмент Python
Они могут совмещать итерацию с фильтрацией, но если вы злоупотребите этой функцией, добавляя слишком много циклов for или слишком много условных операторов, код может стать нечитаемым. Избегайте сильной вложенности этих операторов, если это возможно.

Множества — полезный тип объекта в Python
Множества их их верное использование делают код более стабильным, более математически правильным и более кратким. Главное — знать, когда и как их использовать. В нашем решении множества сыграли существенную роль — не пренебрегайте ими!

Регулярные выражения могут помочь описать все требования к поиску
Хотя это не было использовано в коде, совпадение (или несовпадение) шаблона и слова — это то, что регулярные выражения делают круче всего. Подумайте, как можно переписать мэтчинг и векторизацию слов с помощью регулярных выражений.

Модули itertools и collections содержат очень полезные инструменты
Вы можете многого добиться с базовым знанием Python, если знаете, как именно можно использовать встроенные модули. Модуль itertools особенно полезен, если вы вам нужно провернуть итеративные вычисления.

Блог об аналитике, визуализации данных, data science и BI, заметки с тегом: solver