Disclaimer: пост пятничный, всерьёз не принимать.
Хронологически всё началось с Wordle. Про эту внезапно популярную игру говорили из каждого утюга, делались ролики на youtube, писались боты (а потом из каждого утюга и youtube рассказывали про этих ботов). Даже на Хабре появилось несколько статей на тему. Я тоже сыграл несколько раз.
В какой-то скучный выходной я не выдержал и захотел уже найти оптимальное слово, с которого надо начинать игру. Оптимальное — значит максимально уменьшающее пространство поиска, после которого в среднем останется как можно меньше слов, подходящих под ответ. Про саму программу я писать особо не буду, там все довольно просто, перебирается в лоб, код одноразовый, пишется минут за 10-15, считает секунд 15-20. Нашёл roate, потом оказалось, что можно было просто нагуглить.
Потом решил найти два стартовых слова, это уже считалось подольше, нашло пару carse + doilt, после которой в среднем останется всего четыре слова. И тут Остапа понесло.
Эти слова — оптимальные в среднем. А какие слова будут лучшими даже в самом худшем случае? Чтоб не тянуть интригу — это serai и пара tired + loans. Даже в самом худшем случае, какое бы слово не было бы загадано, после tired loans гарантировано останется не более 16 слов. Это результат для самых отъявленных пессимистов, которые всегда ожидают самого худшего.
Эти программы как перебирают — для каждого возможного слова из множества отгадок (или для каждой пары) перебирают все возможные загаданные слова и считают сколько подходящих слов должно остаться после ответа игры. И считают среднее или берут максимум. Но ведь кроме среднего реалиста и крайнего пессимиста могут быть и всякие промежуточные варианты. Можно ли как-то этот расчет обобщить?