Анализ на задача wordle

Подзадача 1. |words| = 1
Тук е достатъчно да опитаме думата.

Подзадача 2. |words| <= 6
Тази подзадача е с цел да възнагради решения, които не съдържат идеята за пълното решение. 
Тук можем да взимаме първата дума, която отговаря на това, което досега ни е връщал query, и да я пробваме докато не познаем думата. Това не ни гарантира пълни точки, но е възможно решение.

Подзадача 3. |words| <= 10^4 + 67
Тук вече трябва да се ориентираме към пълното решение. Има различни решения за частични точки на тази подзадача, но ще обясня само едно от решенията за 100т. 
Тук ще използваме нещо като грийди стратегия: за всеки guess ще избираме локалния оптимум т.е. най-полезната дума, която можем да опитаме вмомента. Няма да мислим за бъдещи guess-ове.
Да обобщим каква ни е задачата вмомента: имаме списък от думи, при всяка заявка намаляме броя на възможни думи, трябва да намерим някоя от тези думи, като ползваме оптимално заявките.
Това звучи малко като binary search. При двоичното търсене ако ни казват, че числото, което търсим, е по-малко от нашето, това разделя числата, които трябва да търсим, на 2.
Идеята в тази задача е една идея по-сложна. Вместо да ни казват дали едно число е по-малко или по-голямо, ни дават буквите, които съвпадат (това, което връща query) в двете думи.
При двоичното търсене делим на две равни части, но в този случай трябва да разделим думите на 3^5 = 243 (брой възможни шаблони) части и да се стремим да са с почти еднакъв размер.
Да фиксираме една дума, която ще използваме (O(n)). Ако гледаме всички шаблони, можем да проверим колко думи попадат във всеки от тях и следователно каква е вероятността този шаблон да се падне.
Целта на нашето грийди е да избере най-полезната дума, а полезността на всяка дума ще изглежда нещо от сорта на това:
E = сума на (p(w) * (някакъв фактор, който ни показва колко ни е полезно, ако този шаблон се покаже при тази дума)) върху всички шаблони w. 
В нашия случай този фактор е просто колко добре шаблоните делят думата. Както казахме, искаме тези 243 части да са с горе-долу равен размер. 

Как можем да пресметнем това? На пръв поглед звучи доста сложно. Нека си дадем пример.
Имаме 24 думи, разделени на 8 шаблона, вместо 243.
Да речем, че всеки шаблон има равен брой думи => по 3 думи на шаблон. Вероятността да се падне шаблон w при някой guess е p(w)=3/24=1/8
Искаме да измерим колко полезен е даден шаблон, тоест колко думи можем да елиминираме, ако го получим.
Ако шаблонът има малко думи е полезен, защото другите отпадат. Ако има много думи, не е полезен, защото не отпадат много думи.
Следователно полезността на шаблона е обратно пропорционална на вероятността му: полезност(w) ~ 1/p(w).
За всяка дума искаме средната й полезност, за да изберем накрая най-полезната и да я guess-нем. За целта трябва да намерим този фактор.
Ако сложим фактора да е равен директно на 1/p(w), тогава получаваме E = сума на (p(w) * (1/p(w))) върху всички шаблони = сума на (1) върху всички шаблони.
Това просто ни показва броя на шаблоните, но не отчита различните вероятности, ако частите, на които разделят думите, не са равни.
Трябва ни функция за полезност на шаблона, обратно пропорционална на p(w). Авторовото решение използва log2, но log10 също работи, а sqrt дава 73.9 точки. Вероятно може да се докаже защо не е оптимално.
Вече имаме полезност(w) = log2 (1/p(w)).
Ако вървим с примера, полезността на всеки шаблон ни е log2(1/p)=log2(8)=3. Тоест средната полезност на дадена дума е E = сума на (p(w) * log2(1/p(w))) върху всички шаблони w, което в случая е равно на 3.
Тази стойност е еднаква за всички думи в примера, защото всеки шаблон има равен брой думи.

И така намерихме, че полезността на някоя дума е:
E = сума на (p(w) * log2(1/p(w))) върху всички шаблони w.

За всеки guess просто сортираме думите по полезност и избираме най-добрата. Така сложността става O(n^2) в най-лош случай (който тук не би трябвало да се постига) и O(n log n) приблизително в общия случай.

Всъщност формулата идва от теория на информацията, където E отбелязва ентропия и се измерва в битове.

Решение за 73.9 точки (Кики)
Това решение може да не взима пълния брой точки, но използва по-интуитивна идея:
Фиксираме една дума и приемаме, че тя е вярната. Обикаляме всички други и правим "шаблон" (като този който връща функцията query) спрямо 
тази фиксиране дума. Изпълняваме това за всяка дума. Оптималната дума ще бъде тази, която създава максимален брой различни шаблони. След като query ни върне истинския шаблон, махаме всички думи, които не спазват условието за вярност. Цялата тази идея я повтаряме докато има думи в списъка.
Вероятно проблемът в това решение е, че ако има няколко думи с еднакъв максималнен брой различни шаблони, решението няма свестен показател коя от всички да вземе. Това може да увеличи броя на извикванията на query.

Има и други частични решения, направени от състезателите по време на състезанието, които не бяха предвидени от авторите, но са сравнително интуитивни.

Идея и решения: Кирил Зашев
Условие, решения, анализ: Димитър Шапатов
