Guess the Word

Hard

Verily

1 view

Topics:

ArraysGreedy AlgorithmsRecursion

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 are also given the helper object Master. You may call Master.guess(word) where word is a six-letter-long string, and it must be from words. Master.guess(word) returns:

-1 if word is not from words, or
an integer representing the number of exact matches (value and position) of your guess to the secret word.

There is a parameter allowedGuesses for each test case where allowedGuesses is the maximum number of times you can call Master.guess(word).

For each test case, you should call Master.guess with the secret word without exceeding the maximum number of allowed 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.

The test cases are generated such that you can guess the secret word with a reasonable strategy (other than using the bruteforce method).

Example 1:

Input: secret = "acckzz", words = ["acckzz","ccbazz","eiowzz","abcczz"], allowedGuesses = 10
Output: You guessed the secret word correctly.
Explanation:
master.guess("aaaaaa") returns -1, because "aaaaaa" is not in wordlist.
master.guess("acckzz") returns 6, because "acckzz" is secret and has all 6 matches.
master.guess("ccbazz") returns 3, because "ccbazz" has 3 matches.
master.guess("eiowzz") returns 2, because "eiowzz" has 2 matches.
master.guess("abcczz") returns 4, because "abcczz" has 4 matches.
We made 5 calls to master.guess, and one of them was the secret, so we pass the test case.

Example 2:

Input: secret = "hamada", words = ["hamada","khaled"], allowedGuesses = 10
Output: You guessed the secret word correctly.
Explanation: Since there are two words, you can guess both.

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

Guess the Word

Hard

Verily

1 view

Topics:

ArraysGreedy AlgorithmsRecursion

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 are also given the helper object Master. You may call Master.guess(word) where word is a six-letter-long string, and it must be from words. Master.guess(word) returns:

-1 if word is not from words, or
an integer representing the number of exact matches (value and position) of your guess to the secret word.

There is a parameter allowedGuesses for each test case where allowedGuesses is the maximum number of times you can call Master.guess(word).

For each test case, you should call Master.guess with the secret word without exceeding the maximum number of allowed 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.

The test cases are generated such that you can guess the secret word with a reasonable strategy (other than using the bruteforce method).

Example 1:

Input: secret = "acckzz", words = ["acckzz","ccbazz","eiowzz","abcczz"], allowedGuesses = 10
Output: You guessed the secret word correctly.
Explanation:
master.guess("aaaaaa") returns -1, because "aaaaaa" is not in wordlist.
master.guess("acckzz") returns 6, because "acckzz" is secret and has all 6 matches.
master.guess("ccbazz") returns 3, because "ccbazz" has 3 matches.
master.guess("eiowzz") returns 2, because "eiowzz" has 2 matches.
master.guess("abcczz") returns 4, because "abcczz" has 4 matches.
We made 5 calls to master.guess, and one of them was the secret, so we pass the test case.

Example 2:

Input: secret = "hamada", words = ["hamada","khaled"], allowedGuesses = 10
Output: You guessed the secret word correctly.
Explanation: Since there are two words, you can guess both.

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

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the length of each word in the wordlist, and what is the total number of words in the wordlist?
Can the secret word be the same as one of the words in the wordlist? If so, can I assume the wordlist contains the secret word?
What should I return if I cannot guess the secret word within the allowed 10 guesses (or any reasonable upper bound on the number of guesses)? Is there a specific error code or an exception I should raise?
Are the words in the wordlist case-sensitive, and should my guesses be case-sensitive as well?
If there are multiple words in the wordlist that give the same number of matches with my guess, is there a preferred way to choose which word to guess next, or can I pick arbitrarily?

Brute Force Solution

Approach

The brute force approach to "Guess the Word" involves trying every possible word from the list as the secret word. We make a guess, receive feedback, and then use that feedback to narrow down the remaining possible secret words. We repeat this process until we correctly guess the secret word.

Here's how the algorithm would work step-by-step:

Start by considering every word in the list as a potential secret word.
Choose any word from the list and make it your guess.
Compare your guess with the actual secret word (which you don't know directly, but can get comparison feedback from).
Based on the comparison feedback (the number of letters in the correct position), eliminate all the words from the list that don't have the same number of matching letters in the same positions compared to your guess.
If only one word remains in the list, you've found the secret word!
If more than one word remains, choose another word from the remaining possibilities and repeat the process of guessing and eliminating words until only the secret word is left.

Code Implementation

def guess_the_word_brute_force(word_list, secret):    possible_words = word_list[:]
    while len(possible_words) > 0:
        guess_word = possible_words[0]
        matches = get_matches(guess_word, secret)
        
        # Eliminate words that don't have the same number of matches
        possible_words = [word for word in possible_words if get_matches(word, guess_word) == matches]
        
        if guess_word == secret:
            return guess_word

def get_matches(word1, word2):
    # Determines the number of matching characters between two words
    matches = 0
    for index in range(len(word1)):
        if word1[index] == word2[index]:
            matches += 1
    return matches

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n*m*w) – Let n be the number of words in the wordlist, m be the number of guesses we make, and w be the length of each word. In the worst case, we might have to guess close to every word in the wordlist (m is approximately n). For each guess, we iterate through the entire wordlist again (n) to eliminate words that don't match the number of correct letters. Comparing the guessed word with other words takes w operations. Thus, the total time complexity is approximately n*n*w, where n is the number of words, and w is the length of each word; simplifying to O(n*m*w).

Space Complexity

O(N) – The algorithm's space complexity is primarily determined by the need to maintain a list of potential secret words. In the worst-case scenario, initially, this list contains all N words from the input. As the algorithm progresses, it filters this list, but the maximum auxiliary space required is proportional to the initial list size. Thus, the space complexity is O(N), where N is the number of words in the input list.

Optimal Solution

Approach

The goal is to guess a secret word by making strategic guesses. The most efficient strategy involves picking guesses that maximize the information gained about the secret word, quickly narrowing down the possibilities. We'll choose guesses that are different from all previous guesses.

Here's how the algorithm would work step-by-step:

Start by picking a random word from the list of possible words as your first guess.
Submit your guess and see how many letters it has in common with the secret word, and which positions the matching letters are in.
Now, remove all words from the list of possible words that don't have the exact same number of matching letters in the exact same positions as your guess.
From the remaining list of possible words, pick the word that would potentially eliminate the most words if it were your next guess. To do this, for each possible word, count how many other words in the list share a certain number of matching letters in the same positions. Then choose the word that has the lowest sum of those counts. This is minmax strategy.
Repeat steps 2-4 until you guess the secret word or you run out of guesses.

Code Implementation

import random

def guess_the_word(word_list, master):

    def get_matches(word1, word2):
        matches = 0
        for i in range(len(word1)):
            if word1[i] == word2[i]:
                matches += 1
        return matches

    possible_words = word_list[:]
    for _ in range(10):
        #Pick a random word for the first guess.
        if len(possible_words) > 1:
            guess = random.choice(possible_words)
        else:
            guess = possible_words[0]
        match_count = master.guess(guess)
        
        if match_count == len(guess):
            return

        #Filter the list to keep words that match our guess
        possible_words = [
            word
            for word in possible_words
            if get_matches(guess, word) == match_count
        ]

        # Use minmax strategy to reduce worst case outcome.
        if len(possible_words) > 1:
            best_guess = ""
            min_max_score = float('inf')

            for potential_guess in possible_words:
                group_counts = {}
                # Count groups based on pattern matches.
                for other_word in possible_words:
                    matches = get_matches(potential_guess, other_word)
                    if matches not in group_counts:
                        group_counts[matches] = 0
                    group_counts[matches] += 1

                max_group_size = max(group_counts.values())

                # Pick the guess that minimizes the largest group.
                if max_group_size < min_max_score:
                    min_max_score = max_group_size
                    best_guess = potential_guess

            guess = best_guess
            match_count = master.guess(guess)

            if match_count == len(guess):
                return

            #Filter the list to keep words that match our guess.
            possible_words = [
                word
                for word in possible_words
                if get_matches(guess, word) == match_count
            ]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n*m*k) – Let n be the initial number of words, m be the length of the words, and k be the number of guesses. The core loop runs k times (number of guesses). Inside the loop, filtering the word list takes O(n*m) in the worst case, where we compare each word against the guess and calculate matches. Then finding the next best guess involves iterating through all remaining words (up to n), comparing each with every other word to count matches, which is another O(n*n*m) operation. Therefore, one iteration of the main loop is bounded by O(n*m + n*n*m), which simplifies to O(n*n*m). Multiplying by the number of guesses, k, the overall complexity becomes O(k * n*n*m). In the prompt's strategy the selection of the next best guess considers the potential to eliminate words. This has an upper bound of O(n*m), where n is the number of words remaining and m is the word length. This results in time complexity O(n*m*k). Combining both operations gives us O(n*m*k).

Space Complexity

O(N) – The algorithm maintains a list of possible words, which, in the worst case, could initially contain all N words from the input list. This list is filtered in each iteration, but its maximum size is still proportional to N. Furthermore, the counts of matching letters between words, used for the minmax strategy, might be stored in a data structure whose size could be proportional to N in the worst case (considering all possible pairs of words). Therefore, the auxiliary space is O(N).

Edge Cases

Case	How to Handle
wordlist is null or empty	Return an empty string or null to indicate invalid input and prevent null pointer exceptions.
wordlist contains words of different lengths	Filter out words that have different lengths from the initial secret word length.
secret is null or empty	Return an error or handle gracefully by returning a default/empty value to prevent runtime exceptions.
No word in wordlist matches the secret	Handle the case where the algorithm fails to converge by returning a special value (e.g., an empty string) or raising an exception after a maximum number of guesses.
wordlist contains duplicate words	The algorithm should still work correctly as the duplicate words will be treated as separate guesses.
All words in wordlist are identical	The algorithm might get stuck if all words are identical; add a check to handle this special scenario by returning or by randomly picking another word.
Very large wordlist (performance)	Ensure that the number of guesses is bounded to avoid infinite loops and/or excessive processing time.
secret word is not in the wordlist	Handle the case where the secret word is not in the list by returning a specific error or exiting after a maximum number of attempts.