Guess the Word

Guess the Word is an interaction problem: you cannot read the answer, you can only ask questions and learn from the replies. It is a clean lesson in elimination — every answer you get should let you throw away words that can no longer be the secret.

The slow way first

The naive approach is to guess words at random. With a big list you might burn every allowed call and never land on the secret, because a random guess tells you nothing about which words to drop next.

The question to ask: when I get a match count back, what does it tell me about the secret? It tells me the secret must share exactly that many positions with the word I just guessed. So I can compare that guess against every other candidate and discard the ones whose count is different — they could not possibly be the secret.

The idea: each answer prunes the pool

Keep a list of candidates (initially all the words). Each round: guess one candidate, read its score, then keep only the candidates whose match count against that guess equals score. The pool shrinks fast, and within a few rounds only the secret survives.

The key insight: the secret answers consistently. Whatever count it produces against our guess, it must also produce that same count when we compare it to the guess. So every word with a different count is provably not the secret.

Walk through it

Step through the animation. Round 1 guesses "abcde" and gets 1, eliminating the words that score differently — three survive. Round 2 guesses "xyzwe", gets 4, and eliminates one more. Round 3 has a single candidate left, guesses it, and the count equals the word length, so we are done.

Pseudocode

candidates = all words
while candidates is not empty:
    guess = any candidate (here, the first)
    score = master.guess(guess)          # positions shared with secret
    keep only words w where match(w, guess) == score
    if score == word length:
        return guess                     # the secret

The Python solution

def find_secret(words, master):
    def match(a, b):
        return sum(x == y for x, y in zip(a, b))
 
    candidates = words
    while candidates:
        guess = candidates[0]
        score = master.guess(guess)
        candidates = [w for w in candidates
                      if match(w, guess) == score]
        if score == len(guess):
            return guess

• match(a, b) counts how many positions two equal-length words share.
• candidates starts as the full list and only shrinks.
• guess = candidates[0] — we simply guess the first survivor each round (smarter pickers exist; see below).
• score = master.guess(guess) is the one piece of feedback we get.
• The list comprehension is the filter: keep a word only if its count against the guess matches score.
• When score == len(guess) every position matched, so the guess is the secret.

Complexity

Each guess costs an O(n · L) filter over the candidate list, and the pool shrinks every round, so a handful of guesses g suffices. We trade O(n) space for the candidate list in exchange for never wasting a guess.

When this pattern shows up

Practice