Taro Logo

Guess the Word

Hard
Meta logo
Meta
Topics:
ArraysStrings

You are given an array of unique strings words where words[i] is six letters long. One word of words was chosen as a secret word. You have a Master object with a guess(word) method, which returns the number of exact matches between your guess and the secret word (-1 if the word is not in the input list). You are allowed a maximum number of guesses allowedGuesses. Write an algorithm to guess the secret word within the allowed number of guesses. You will get "Either you took too many guesses, or you did not find the secret word." if you called Master.guess more than allowedGuesses times or if you did not call Master.guess with the secret word, or "You guessed the secret word correctly." if you called Master.guess with the secret word with the number of calls to Master.guess less than or equal to allowedGuesses.

For example:

secret = "acckzz", words = ["acckzz","ccbazz","eiowzz","abcczz"], allowedGuesses = 10

In this case, you should call master.guess("acckzz"), which returns 6, and the algorithm terminates successfully.

Another Example:

secret = "hamada", words = ["hamada","khaled"], allowedGuesses = 10

You could call master.guess("hamada"), which returns 6, or master.guess("khaled"), which returns 0, and then subsequently call master.guess("hamada"), which returns 6, and the algorithm terminates successfully.

Constraints:

  • 1 <= words.length <= 100
  • words[i].length == 6
  • words[i] consist of lowercase English letters.
  • All the strings of wordlist are unique.
  • secret exists in words.
  • 10 <= allowedGuesses <= 30

Solution


Brute Force Approach

Let's begin with a brute-force approach. The most straightforward way to solve this problem is to iterate through the list of words and guess each word until the Master.guess() method returns 6 (meaning all characters match). Although simple, this method isn't efficient and doesn't guarantee finding the secret within the allowed number of guesses, especially if the secret word is near the end of the list.

Code Example (Python)

def findSecretWord_brute_force(words, master):
    for word in words:
        if master.guess(word) == 6:
            return

Big O Analysis:

  • Time Complexity: O(N), where N is the number of words in the list.
  • Space Complexity: O(1), as we use constant extra space.

Optimal Solution: Minimax with Random Guessing

A more efficient approach involves using a minimax strategy combined with random guessing. The main idea is to:

  1. Calculate Similarity: For each pair of words, calculate the number of matching characters.
  2. Partition Words: Based on a guess, partition the remaining words into groups based on their similarity to the guess.
  3. Reduce Search Space: Choose a guess that minimizes the maximum size of these groups.
  4. Repeat: Continue this process until the secret word is found or the maximum number of guesses is reached.

This strategy helps to narrow down the search space more effectively than the brute-force approach.

Code Example (Python)

import random

class Solution:
    def findSecretWord(self, wordlist, master):
        def matches(w1, w2):
            match = 0
            for i in range(len(w1)):
                if w1[i] == w2[i]:
                    match += 1
            return match

        for _ in range(10):  # Up to 10 guesses
            guess = random.choice(wordlist)
            match_count = master.guess(guess)

            if match_count == 6:
                return

            wordlist = [word for word in wordlist if matches(guess, word) == match_count]

Explanation:

  • The matches function calculates the number of exact matches between two words.
  • The main loop iterates up to 10 times (as allowed by the problem constraints).
  • In each iteration, a random word is chosen from the remaining wordlist.
  • If the guess is correct (6 matches), the function returns.
  • Otherwise, the wordlist is filtered to include only words that have the same number of matches with the guess as the secret word would.

Big O Analysis:

  • Time Complexity: The time complexity is difficult to precisely determine due to the random nature and the word filtering. However, on average, this approach significantly reduces the search space with each guess.
  • Space Complexity: O(N) in the worst case, where N is the number of words in wordlist, due to the creation of new lists during filtering.

Edge Cases

  • Empty Word List: If the initial word list is empty, the algorithm should handle this gracefully (though the problem statement says this won't happen).
  • No Matching Words: If, after a guess, there are no words left in the filtered list, it implies an issue (either the guess was wrong or the word list is inconsistent).
  • Secret Word Not in the List: The problem statement guarantees that the secret word is in the list, so this is not a relevant edge case.

Further Optimizations

  • Instead of random guessing, one could implement a more sophisticated minimax strategy to choose the next guess. This involves selecting the word that minimizes the maximum number of words that could remain after a guess.
  • Caching the results of matches could also provide a slight performance improvement.