12.2 Guess the Word

12.2.1 Problem Metadata

12.2.2 Description

You are given a lc-list of unique six-letter lowercase words. One of them is the secret word. An oracle master.guess(word) accepts only words from the lc-list and returns the number of positions where your guess matches the secret exactly. Guesses not in the lc-list return -1. You have at most 10 guesses to find the secret word.

12.2.3 Examples

wordlc-list = ["acckzz","ccbazz","eiowzz","abcczz"], secret = "acckzz"
master.guess("aaaaaa") -> -1 (not in lc-list)
master.guess("acckzz") -> 6 (found the secret)
master.guess("ccbazz") -> 3

12.2.4 Constraints

  • Word lc-list length ≤ 100
  • Each word length = 6
  • All words are lowercase letters
  • At most 10 guesses

12.2.5 Solution - Minimax Filtering

12.2.5.1 Walkthrough

Every guess partitions the remaining candidate set by the match count produced by master. To maximize information gained each round, evaluate each word as a potential guess and simulate its worst-case partition size: for every other word, compute the similarity score (number of matching positions) and count how many candidates would remain after such feedback. Choose the guess with the minimal worst-case bucket to shrink the search space efficiently. After receiving the match count, filter the candidate lc-list to only words compatible with that feedback and repeat until the secret is found or guesses run out.

12.2.5.2 Analysis

  • Time Complexity: O(k * n^2 * L) in worst case (n words, length L=6, k guesses ≤ 10)
  • Space Complexity: O(n) to store candidate indices and buckets

12.2.5.3 Implementation Steps

  1. Track remaining candidate indices.
  2. For each guess candidate compute max bucket size by grouping other words by similarity score.
  3. Select the guess with minimal max bucket (minimax).
  4. Call master.guess(word). If matches = 6, stop; otherwise filter candidates to those with the same similarity score relative to the guess.
  5. Repeat until the secret is found or attempts exhausted.

12.2.5.4 Code - Java

class Solution {
    private static final int WORD_LEN = 6;

    public void findSecretWord(String[] words, Master master) {
        List<Integer> candidates = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            candidates.add(i);
        }

        while (!candidates.isEmpty()) {
            int bestIdx = pickMinimaxGuess(words, candidates);
            int matches = master.guess(words[bestIdx]);
            if (matches == WORD_LEN) {
                return;
            }
            List<Integer> next = new ArrayList<>();
            for (int idx : candidates) {
                if (similarity(words[idx], words[bestIdx]) == matches) {
                    next.add(idx);
                }
            }
            candidates = next;
        }
    }

    private int pickMinimaxGuess(String[] words, List<Integer> candidates) {
        int bestIdx = -1;
        int minWorst = Integer.MAX_VALUE;
        for (int guessIdx : candidates) {
            int worstBucket = 0;
            int[] bucket = new int[WORD_LEN + 1];
            for (int otherIdx : candidates) {
                if (guessIdx == otherIdx) continue;
                int score = similarity(words[guessIdx], words[otherIdx]);
                worstBucket = Math.max(worstBucket, ++bucket[score]);
            }
            if (worstBucket < minWorst) {
                minWorst = worstBucket;
                bestIdx = guessIdx;
            }
        }
        return bestIdx;
    }

    private int similarity(String a, String b) {
        int match = 0;
        for (int i = 0; i < WORD_LEN; i++) {
            if (a.charAt(i) == b.charAt(i)) {
                match++;
            }
        }
        return match;
    }
}