Недавно наткнулся на довольно известную игру – 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 есть стратегия, всегда приводящая к победе (на используемом датасете как минимум).
Особой пользы это знание вряд ли принесет, но я получил моральное удовлетворение, немного размял мозги, обдумывая стратегии и вспоминая слова, а теперь и поделился этим с вами. Надеюсь данная головоломка вас хоть немного заинтересовала, или может вы сможете найти контрпример, когда данная стратегия не сработает и поделиться им.
Спасибо за внимание.
Комментарии (28)
DjPhoeniX
23.05.2022 00:33Вроде бы (по логике правил) не должно быть слов, в которых одна и та же буква повторяется больше одного раза. Если отфильтровать датасет по таким словам - станет ли меньше «коллизий хэша»?
hardlight Автор
23.05.2022 00:38+1Повторение букв не запрещено правилами, и такие слова встречаются как в самой игре, так и в найденом списке.
Weron2
23.05.2022 14:48Прикольно, потому что я и сам недавно только начал играть в эту игру и тоже из-за тинькова, но играю на русском. У меня стратегия такая:
Спрут, камин, выход, желчь. А потому уже думать что может быть если слишком мало букв открылось) и наверное правильнее начинать именно с камина- т.к. по статистике есть подозрение что буквы а,и,к,м,н используются чаще в разных словах, но это тоже нужно проверять
red_void
23.05.2022 15:21Любопытно. Я в русскоязычной версии обычно начинал максимум с двух слов: «напор» и «метис». Этого обычно хватало для того, чтобы дальше угадывать более предметно.
Было бы прикольно развить идею и найти оптимальную или близкую к ней стратегию для заданного датасета. Например, Кнут в свое время предлагал хорошую стратегию для классических «Быков и коров», ее можно модифицировать.
SGordon123
23.05.2022 15:38А разве можно вводить слова без открытых букв? Или это только русское дополнение?
Rumidu
23.05.2022 16:18
Возникло желание перечитать "Золотого жука" Э.По. Хорошее применение знания частотности использования букв в английском языкеязыке.
Rumidu
23.05.2022 16:50-1Пофантазирую. Играю в эту игру месяца три, почти каждый день и фиксирую результат. Начало игры - заполняю клетки с первым словом, каждый раз слова новые (за редким исключением - такой комплимент самому себе). И тут из памяти полезло: "метод свободных ассоциаций", "лингвистический ассоциативный эксперимент", "тест Юнга 100 слов". То есть, не пытаются ли люди запустившие эту игру получить некий "портрет" игрока? Публикация эта полезна ещё и тем, что применяя "слова-шаблоны" для решения головоломки, мы исключаем возможность "прочесть" нас.
a1ex25
23.05.2022 17:16Мой скрипт для игры от Тинькова работает по следующей логике.
На основании словаря существительных, выбраны все из пяти символов.
Посчитаны количество повторений каждой буквы и составлен рейтинг.
На основе топа букв выбрал топ слов (то есть те в которых максимальное кол-во повторений топ-букв): первое - "кроат", затем в целом равнозначные "норка", "крона" и "оркан". Игру начинаем с ввода одного из этих слов.
После первой попытки, в скрипт отправляю введенное слово, а так же символы угаданные и символы с угаданным индексом.
Скрипт выводит два списка:
1) список слов, которые подходят под угаданные ранее буквы;
2) список слов в которых не встречаются символы, проверенные ранее.
Второе слово ввожу из списка, символы из которых не встречались ранее (ну уже и заглядывая, в рейтинг символов составленный ранее). Вновь указываю угаданные символы и индексы. Скрипт повторно отрабатывает только уже на основе возможных слов, оставшихся после предыдущей попытки, и вновь формирует 2 списка.Тут уже обычно можно выбрать слово из списка слов, подходящих по угаданные ранее символы и их позиции, так как обычно их остается менее десятка. То есть обычно хватает трех попыток.
thealfest
23.05.2022 22:52Словарь вполне можно было вытащить из оригинального js-кода. На самом деле их два - 2315 слов, которые могут быть загаданы + еще 10657 слов, которые можно ввести.
Hebe
Сейчас в тинек запустили аналог игры. На русском алфавите есть стратегия, всегда приводящая к победе?
hardlight Автор
Благодаря этой акции от Тинькофф и заинтересовался игрой. Но для русской версии не искал пока стратегию, может чуть позже.
Ryder95
Как раз недавно написал скрипт на Python для помощи в игре. Я выкачал частотный словарь, словарь существительных и частоту использования букв, каждый раз начинаю со слова "осина", так как в нем самые популярные буквы, и дальше уже методом исключения, за 4 дня скрипт пока ни разу не подвёл
Beluxur
Я обычно начинаю игру со слов "прима - весло - кухня" (15 разных букв, 6 самых популярных гласных), а дальше по обстоятельствам )))
censor2005
По ощущениям, на русском играть гораздо сложнее - в русском больше гласных букв, да и количество букв больше. И кажется, что допустимых в речи комбинаций букв в русском больше.
Neusser
в русском, в отличие от английского, используются только существительные. А в английском и глаголы, и прилагательные, и наречия, и местоимения, и даже причастие совсем недавно было.
Weron2
А повторы букв есть? В русском варианте игры есть слова с повторяющимися гласными и даже согласными, поэтому играть приходится с проверкой на повторение, иначе вообще кажется фиг угадаешь
Neusser
Есть повторы.
Еще отличие - в русском варианте (по крайней мере на сайте belousov что-то там) самые обычные слова, никаких редкоупотребимых. А в английском может быть все, что угодно. Знакомый англичанин иногда пишет мне что-нибудь типа "ну очень странное слово" или "я и забыл, что такое слово есть".
PavlovM
Я наткнулся на русский вариант игры несколько месяцев назад. Через несколько десятков честно решенных слов накидал скрипт, который выбирает 20 самых популярных букв в списке русских пятибуквенных слов и ищет в том же словаре 4 слова, состоящие полностью из них.
Результат: почин, смрад, культ, взбег.
Стратегия: вводить эти слова, пока не откроется 4 буквы, потом находить точное положение этих букв. Пятая почти всегда легко угадывается в конце, когда остальные 4 стоят на местах.
Несколько раз бывало, что после этих 4 слов нет ни одной открытой буквы, но такую экзотику как минимум в половине случаев получалось угадать по неиспользованным буквам.
WicRus
Помощник для стратегии.
У меня два начальных слова «океан» и «спирт», иногда получается угадать третей попыткой.
tminnigaliev
приём
сачок
тяжба
гуляш
выдох
покрываются буквы:
а, б, в, г, д, е, ё, ж, и, к, л, м, о, п, р, с, т, у, х, ч, ш, ы, я
не покрываются:
з, й, н, ф, ц, щ, ъ, ь, э, ю,
покрываются дважды:
а, о, я
Это моя "стратегия".
Но её можно улучшить. Надо иметь не список слов, а что-то типа дерева, в котором выбор следующего зависит от того, какие буквы известны.
Neusser
если
гуляшзаменить наглушь, то покрытие увеличится наьXneg
Пару месяцев назад заморочился этой задачей, написал алгоритм на питоне.
https://gist.github.com/xneg/4dc9f82cb1822c1d7aaef27143558658
Для https://wordle.belousov.one/ работает за 2-5 попыток, чаще всего 3. Для тинька работает хуже, потому что Тинькофф не случайное слово из условной тысячи выбирает, а загадывает относительно редкие.
Xneg
В двух словах работа алгоритма. Для каждого слова А в исходной выборке надо получить паттерн для каждого другого слова B, как если бы мы вводили первым слово A, а загадано было бы слово B.
Логично, что паттерны для некоторых слов будут совпадать (особенно, если это все серые). Все паттерны распределеяем по бакетам по количеству. Таким образом, для каждого слова в исходной выборке получаем словарь вида узор: количество повторений. Далее из всех слов выбираем начальным то, у которого узор с максимальным количеством повторений является минимальным среди всех остальных слов, ну, то есть, такой min(max(...)).
Соответственно, именно это начальное слово даже при худшем раскладе максимально уменьшит нам выборку доступных слов. Ну и этот алгоритм повторяется на втором и последующем шагах с учетом уже открытых букв и сильно сократившегося количества доступных слов.
hard_sign
Я написал скрипт на перле, который решает задачу. Подход автора фундаментален, я же поступил проще: начинаю со слова с самыми распространёнными буквами (по статистике моего словаря это коран/оркан/крона), а потом фильтрую список в соответствии с ответами. Почти всегда слово угадывается с 4 попытки, единственное слово, на которое понадобилось 5 попыток – «кабан»: