843. Guess the Word - Detailed Explanation

Problem Statement

You are given a list of unique words (all of the same length) and an interface (often called Master) that hides one secret word. You can make guesses by calling the master API with a word from the list. The API returns an integer score indicating how many characters in your guessed word match exactly (both character and position) with the secret word. Your goal is to guess the secret word within at most 10 guesses.

Example:

Suppose the secret word is "acckzz" and the word list is:

["acckzz", "ccbazz", "eiowzz", "abcczz"]

• A call to master.guess("eiowzz") might return 3 if 3 characters match exactly with the secret.
• If you eventually call master.guess("acckzz") and it returns 6 (i.e. the length of the word), then you have found the secret word.

Constraints:

• All words in the list have the same fixed length.
• The list contains unique words.
• You have at most 10 guesses to identify the secret word.

Hints Before Solving

• Hint 1: Use the feedback (number of matching positions) to filter out words that could not possibly be the secret.
• Hint 2: Consider that a naïve random guessing strategy might fail in the worst-case; think about how you can choose each guess to narrow the candidate pool as effectively as possible.
• Hint 3: A minimax approach is a common strategy in problems like this. For each candidate word, consider how many other words would remain if that candidate were guessed and a certain match score were returned.
• Hint 4: Precomputing similarities between pairs of words (i.e. how many matching characters they share) can help you quickly filter the candidate list.

Approaches to Solve the Problem

Approach 1: Random Guessing (Naïve)

• Idea:
  Randomly pick a word from the candidate list, make a guess, and then filter the candidate list to only include words that would yield the same matching count with the guessed word. Repeat this process.

• Downside:
  Although this may work in many cases, it does not guarantee that you will reduce the candidate list fast enough to find the secret within 10 guesses in the worst-case scenario.

Approach 2: Minimax (Optimal Strategy)

Explanation:

1. Precompute Similarity:
   For every pair of words in the candidate list, you can compute how many positions match exactly. This similarity measure is used to decide which word to guess next.

2. Select the Next Guess Using Minimax:
   For each candidate word, simulate what would happen if you guessed it:

   • For every possible match score (from 0 to the word length), count how many words in the candidate list would remain if the guess resulted in that score.
   • The worst-case scenario for that guess is the maximum size among these counts.
   • Choose the candidate word that minimizes this worst-case count. This ensures that, regardless of the response, the number of remaining candidates is as small as possible.

3. Filter the Candidate List:
   Once you make a guess and receive a match score from the master API, filter the candidate list to include only those words that have the same similarity (i.e. same number of matching characters) with the guessed word as the score.

4. Repeat Until the Secret is Found or Guesses Run Out:
   Continue the process with the updated candidate list. If at any point the API returns a score equal to the word length, you have found the secret.

Why Minimax?

The minimax strategy is aimed at reducing the worst-case number of remaining candidates after each guess. By carefully selecting the guess that “splits” the candidate list most evenly (or minimizes the largest group), you improve the chance of narrowing down the possibilities within 10 guesses.

Code Implementations

Python Implementation