Choose optimal guesses for green-only Wordle

Problem Statement

In a variant of the Wordle game, you are provided with a dictionary of words. When you make a guess, you receive a 'green' feedback only for letters that are in the correct position. If a letter is not in the correct position, you receive no information about it (i.e., you do not know if it is absent or misplaced).

Your goal is to write a function find_best_guess(words) that returns the word from the provided list that minimizes the expected number of remaining possible words for the next turn.

Rules

• A guess is 'green' at index i if guess[i] == secret[i].
• After a guess g, the set of possible candidates is filtered: only words that share the same green-feedback pattern as the secret word relative to g remain valid.
• Assume every word in the provided dictionary is equally likely to be the secret word.

Function Signature

def find_best_guess(words: List[str]) -> str:

Example

If words = ['aba', 'aca', 'ada']:

• If you guess 'aba':
  • If secret is 'aba', feedback is (T, T, T). Remaining: {'aba'}.
  • If secret is 'aca', feedback is (T, F, T). Remaining: {'aca'}.
  • If secret is 'ada', feedback is (T, F, T). Remaining: {'ada'}.
  • The expected number of remaining words is (1 + 1 + 1) / 3 = 1.

Constraints

• len(words) is between 1 and 2,000.
• All words have the same length L (1 <= L <= 10).
• You should return the word that results in the smallest average size of the resulting candidate set.

Edge Cases

• If multiple words result in the same minimum expected value, return the one that appears first lexicographically.