Guess the secret word from match-count feedback

A secret word is one of a list of distinct words, all the same length. You guess words from the list; for each guess you learn its match score, the number of positions where the guess and the secret have the same letter. Find the secret in as few guesses as possible.

Interface

Unless you agree on a different interface with the interviewer, assume:

• score(a: str, b: str) -> int counts positions i with a[i] == b[i].
• next_guess(words: list[str], guesses: list[str], scores: list[int]) -> str. Keep only the candidates consistent with every earlier guess and its score. For each candidate as a possible guess, group the remaining candidates by the score it would return, and choose the guess whose largest group is smallest. Break ties by the lexicographically smallest word.
• find_secret(words, oracle) -> str repeats next_guess against an oracle(guess) -> int until the score equals the word length.

Example

words = ["acckzz", "ccbazz", "eiowzz", "abcczz"]
next_guess(words, [], [])            ->  "acckzz"   # scores 6, 3, 2, 4: every group has size 1
next_guess(words, ["acckzz"], [3])   ->  "ccbazz"   # the only word scoring 3 against acckzz

next_guess(["aaaa", "aaab", "aaba", "abaa", "baaa"], [], [])  ->  "aaab"
# guessing "aaaa" leaves a group of 4 (all score 3); each other guess leaves at most 3

Constraints

• 1 <= len(words) <= 500; each word has 1 to 20 lowercase letters; all words have the same length.
• Every earlier guess is in the list, and at least one word is consistent with all scores.

Clarifying questions

• Must every guess come from the list?
• Is there a limit on the number of guesses, and is the secret chosen adversarially or at random?
• How should ties between equally good guesses be broken?
• How large can the list get?

What a strong answer covers

• Filtering: after each answer, keep only the words whose score against the guess equals the answer. Never guess a word already ruled out.
• Minimax choice: for each candidate, count the score groups; O(n^2 x L) per guess, fine for 500 words. Precompute the pairwise score matrix once.
• Why random guessing can fail on adversarial lists, and why minimax bounds the worst case.
• Tests with a single candidate, words that all share a prefix, and a secret found on the first guess.

Follow-ups

• Pick the guess that maximizes the expected information (entropy of the score groups) instead of minimizing the worst group. When do the two differ?
• Allow guesses from outside the candidate set, as long as they are in the list.
• The oracle sometimes returns a wrong score once. How would you stay robust?