Wordle или как выиграть за 6 ходов

Недавно наткнулся на довольно известную игру – Wordle. Суть игры за шесть попыток угадать случайное слово из пяти букв, при этом после каждой попытки цветом буквы окрашиваются в различны цвета в зависимости от того насколько ты близок. Серая буква означает, что данного символа в слове нет, оранжевая – буква есть, но стоит в другом месте и зеленая – буква правильно расположена.

Меня сразу заинтересовало, является ли игра детерминированной, можно ли разработать стратегию, которая всегда позволит угадать задуманное слово не более чем за шесть попыток. С этой мыслью я начал играть, чтобы проверить механику.

Не попробуешь – не узнаешь

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

После пары игр, я составил свой список слов фаворитов: TANGO, WEIRD, BLOCK и JUMPS, которые покрывали 19 различных букв английского алфавита и 5 гласных из 6. Выбор именно этих слов не обоснован логикой, скорее случайным стечением обстоятельств и ассоциаций, порожденных моим воображением. Тем не менее, комбинация показалась мне настолько удачной, что я решил, что с ней смогу определить любое слово. Обсудив эту теорию с друзьями, удалось улучшить набор, заменив TANGO на TANGY, тем самым покрыв уже 20 уникальных букв и все гласные.

Потратив ещё немного времени, играя с этими 4-мя словами, и с помощью комбинаторики определяя загаданное слово, я решил приступить к полноценному доказательству, ведь даже проведя сотни игр нельзя будет с уверенностью сказать, что эта стратегия гарантирует победу.

А как же код?

Я решил выбрать самое скучное доказательство – проверить все возможные варианты. К сожалению найти список слов оригинальной игры у меня не вышло, поэтому я воспользовался смекалкой. Через пару поисковых запросов я нашел полезный сайт, помогающий по списку "хороших" и "плохих" букв выдавать возможные варианты решения для Wordle. Углубившись в их API, и сделал кастомный запрос, ищущий все возможные слова из 5 букв с лимитом в 20 000 слов, для игнорирования пагинации. Для интересующихся вот сам вызов. Всего получилось 2315 слов.

Далее дело за малым, я прошелся по каждому из слов и посчитал какой результат зеленых и оранжевых букв я получу после ввода своей "магической" комбинации:

const SUCCESS_STATUS = 's';
const WARNING_STATUS = 'w';
const INITIAL_WORDS = ['tangy', 'weird', 'block', 'jumps'];

// получаем из слова объект букв с зеленым или желтым статусом
const parseWord = world => {
  return [...world].reduce((mapping, letter, index) => {
    const initialWord = INITIAL_WORDS.find(initialWord => initialWord.includes(letter));
    // если буквы нет во введенных нами словах
    if (!initialWord) {
      return mapping;
    }

    // находится ли буква на своем месте
    const status = initialWord.indexOf(letter) === index ? SUCCESS_STATUS : WARNING_STATUS;
    
    // объединяем с предыдущими значениями
    return { ...mapping, [letter]: status };
  }, {});
};

// получаем ключ, уникальный для каждой комбинации букв со статусами
const getHashFromMapping = mapping => {
  return Object.entries(mapping)
    // сортируем буквы для гарантирования равенства
    // { a: 's', b: 'w' } и { b: 'w', a: 's' }
    .sort(([letter1], [letter2]) => letter1.charCodeAt(0) - letter2.charCodeAt(0))
    .map(([letter, status]) => `${letter}-${status}`)
    .join('|');
};

Оставалось понять, существуют ли слова, и если да, то сколько их, которые будут иметь одинаковый хэш, а значит не смогут быть однозначно определены после 4-х попыток (спойлер, да). Сразу уточним, что если слов с одинаковым хэшем всего два, то однозначно можно угадать верное за 5-ую и 6-ую попытку соответственно, а значит нас интересуют только комбинации из трех и более слов.

// опять достаточно простой вариант кода, чтобы это посчитать
const main = (words) => {
    const hashCounts = words.reduce((result, word) => {
        const mapping = parseWord(word);
        const hash = getHashFromMapping(mapping);
        // сохраняем список слов для каждого хэша
        const values = result[hash] || [];

        // используем Object.assign вместо ...result для повышения производительности
        // т.к. ...result будет пересоздавать объект каждый раз
        return Object.assign(result, { [hash]: [...values, word] })
    }, {});
  
  // вычисление любой интересующей статистики из hashCounts
};

После запуска скрипта на нашем датасете выяснилось, что для 2315 пятибуквенных слов:
Уникальных хэшей, по которым однозначно можно назвать слово – 1999
Хэшей ровно с двумя словами – 119
Хэшей ровно с тремя словами – 19
Хэшей ровно с четырмя словами – 4
Хэшей с пятью словами или больше – 1

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

// в каждой строке слова с одинаковым хэшем и через | проверочное слово
hazel,halve,valve | halve
bezel,bevel,belle | bevel
fixer,river,eerie | river
graze,grave,agree | grave
shaft,staff,stash | staff
avail,flail,villa | flail
earth,hater,eater | hater
false,salve,easel | salve
filer,liver,rifle | liver
filet,lithe,title | lithe
frail,rival,viral | rival
lathe,valet,latte | lathe
loath,allot,total | loath
stave,asset,state | stave
puree,purer,rupee | purer
ester,reset,steer | ester

Аналогичная ситуация для хэшей с 4-мя или более словами, по одному слову из списка можно либо случайно угадать, либо однозначно определить с 6-ой попытки загаданное слово, хотя логика и чуть сложнее.

fever,verve,freer,refer        | freer
hover,offer,rover,error        | rover
horde,odder,order,rodeo        | order
forte,other,voter,otter        | voter
fresh,serve,sever,sheer,verse  | verse

Как можно заметить в списках выше отсутствуют 3 хэша, которые дают интересные комбинации слов – последнии четыре буквы в каждой комбинации одинаковые и отличаются только первый символ. Для них я отдельно подобрал пятое проверяющее слово, которое помогает проверить какой из первых символов все же содержится в искомом слове

// Пример, вводя слово fever
// если оранжевая f, то искомое слово focal
// если оранжерая v, то искомое слово vocal
// если ни f, ни v не оранжевые, то искомое слово local
focal,vocal,local | fever
viper,piper,riper | privy
haunt,vaunt,taunt | vouch

И для чего это все?

Таким образом, достаточно грубым методом, но мне удалось удостовериться, что все же для игры Wordle есть стратегия, всегда приводящая к победе (на используемом датасете как минимум).

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

Спасибо за внимание.