Think of this like Wordle, but with a fixed word list. You guess a word from the list, the system tells you how many characters are in the exact right position, and you use that feedback to narrow down which word is the secret. The twist: you have a limited number of guesses, so you need a strategy, not just trial and error.

Here is the core observation that drives every approach. After guessing word W and receiving a match count of k from the Master, we know the secret has exactly k positional matches with W. So any word in our list that does NOT have exactly k positional matches with W cannot be the secret. We can safely eliminate it. This "guess and filter" loop is the foundation. The only question is: which word should we guess next to eliminate the most candidates?

Key Constraints:

Intuition

The simplest strategy is to pick any word from the candidate list, guess it, and use the Master's feedback to eliminate impossible candidates. We don't need a clever selection strategy to get started. Even picking the first word in the list works.

Here is why filtering works. Suppose we guess word W and the Master returns k. That means the secret has exactly k characters matching W in the same positions. Now look at every other word in our list. If a word has, say, 2 positional matches with W but the Master said 3, that word can't be the secret. We toss it. The secret, on the other hand, always survives this filter because it genuinely has k matches with W.

After filtering, we repeat with the smaller candidate list. Each round, we guess one word and remove it plus all incompatible words. Eventually, only the secret remains.

Algorithm

Example Walkthrough

Code

The bottleneck here is our selection strategy. Picking the first word can waste guesses when it has the same match count with all other candidates, leaving nothing eliminated. What if we chose words that are more likely to split the candidates into smaller groups?

Intuition

Before diving into a full game-theory solution, there is a practical heuristic that works well. The insight comes from probability. For two random 6-letter words, each position has a 1/26 chance of matching. The probability of zero total matches is (25/26)^6, which is about 79.4%. That means roughly 4 out of 5 word pairs share no characters in any position.

Why does this matter? When we guess a word and get 0 matches back, we filter to keep only words with 0 matches against our guess. Since most word pairs have 0 matches, that group tends to be huge. The 0-match group is almost always the largest group, and a large surviving group means poor elimination.

So here is the heuristic: for each candidate, count how many other candidates have 0 matches with it. Pick the one with the fewest zero-match partners. This word is the most "connected" to the rest of the list. When we guess it, the 0-match outcome leaves fewer survivors, and non-zero match outcomes leave even fewer.

Algorithm

Example Walkthrough

Code

The zero-match heuristic only looks at one of seven possible match outcomes. A word might have few zero-match partners but a huge 3-match group. What if we considered all possible outcomes and picked the word that minimizes the worst case?

Intuition

This is where game theory enters the picture. We are playing a game against an adversary (the hidden secret). We pick a guess; the adversary "picks" the outcome (the match count). We want to minimize our worst case, no matter what the adversary does.

Here is the idea. For each candidate word W, imagine guessing it. The other candidates split into groups based on their match count with W: the 0-match group, the 1-match group, and so on up to the 5-match group (6-match means W itself, which would be the answer). The secret falls into one of these groups, and after guessing W, we are left with that group as our new candidate list.

The worst case for guessing W is the size of the largest group. If W splits candidates into groups of sizes [15, 3, 2, 1], the worst case is 15 remaining candidates. But if another word X splits them into [5, 5, 4, 6], the worst case is only 6.

The minimax strategy picks the word whose largest group is the smallest. We minimize the maximum damage. This guarantees the best worst-case convergence, and in practice it typically finds the secret in 4-5 guesses even for 100 words.

Algorithm

Example Walkthrough

Code