843. Guess the Word


Problem Explanation

We are given a guessing game, where we are given a list of unique six-letter words, and one of those words is the "secret". We can make a guess on what the secret word could be by calling master.guess(word). If the word we guess is not in the word list, it returns -1. Otherwise, it returns an integer indicating the number of matches of both letter and position our guess has with the secret word.

We are tasked to find the secret word within 10 guesses. If we manage to correctly guess the secret word within 10 guesses, we pass the test case.

For example, given secret = "acckzz", and wordlist = ["acckzz","ccbazz","eiowzz","abcczz"], if we guess "aaaaaa", -1 would be returned as it's not in the word list. If we guess "acckzz", 6 would be returned as it's the secret word. If we guess "ccbazz", 3 would be returned as it has three matching characters at correct positions with the secret word.

Solution Approach

The solution approach involves generating random secret guesses. If a guess does not match the secret word, we eliminate all words from the word list that wouldn't have resulted in the same guess result.

This is done within a for loop that runs 10 times. At each iteration, we make a guess from the current word list. If the guess fully matches the secret (i.e., all characters match), we break the loop. If not, we update the word list to only include words that have the same number of matches with our guessed word, and continue to the next guess.

Python Solution

1
2python
3import random
4class Solution:
5    def findSecretWord(self, wordlist: List[str], master: 'Master') -> None:
6        for i in range(10): # You have 10 guesses
7            guess = random.choice(wordlist) # randomly pick a word from the wordlist
8            x = master.guess(guess) # check how many characters match
9            wordlist = [w for w in wordlist if sum(i==j for i,j in zip(guess, w)) == x] 
10        # filter wordlist for the next iteration to only include words that would have the same match result

Java Solution

1
2java
3import java.util.*;
4class Solution {
5    public void findSecretWord(String[] wordlist, Master master) {
6        for (int i = 0; i < 10; ++i) {
7            String guess = wordlist[new Random().nextInt(wordlist.length)];
8            int x = master.guess(guess);
9            List<String> wordlist2 = new ArrayList<>();
10            for (String w : wordlist)
11                if (match(guess, w) == x)
12                    wordlist2.add(w);
13            wordlist = wordlist2.toArray(new String[0]);
14        }
15    }
16
17    public int match(String a, String b) {
18        int matches = 0;
19        for (int i = 0; i < a.length(); ++i)
20            if (a.charAt(i) == b.charAt(i))
21                matches ++;
22        return matches;
23    }
24}

C++ Solution

1
2cpp
3class Solution {
4public:
5    void findSecretWord(vector<string>& wordlist, Master& master) {
6        srand(time(nullptr));  // Required
7
8        for (int i = 0; i < 10; ++i) {
9            const string& guessedWord = wordlist[rand() % wordlist.size()];
10            const int matches = master.guess(guessedWord);
11            if (matches == 6)
12                break;
13            vector<string> updated;
14            for (const string& word : wordlist)
15                if (getMatches(guessedWord, word) == matches)
16                    updated.push_back(word);
17            wordlist = std::move(updated);
18        }
19    }
20
21private:
22    int getMatches(const string& s1, const string& s2) {
23        int matches = 0;
24        for (int i = 0; i < s1.length(); ++i)
25            if (s1[i] == s2[i])
26                ++matches;
27        return matches;
28    }  
29};

JavaScript Solution

1
2javascript
3/**
4 * // This is the Master's API interface.
5 * // You should not implement it, or speculate about its implementation
6 * class Master {
7 *   guess(word: string): number {}
8 * }
9 */
10var Solution = function() {
11    this.findSecretWord = function(wordlist, master) {
12        for (let i = 0; i < 10; i++) {
13            let guess = wordlist[Math.floor(Math.random() * wordlist.length)];
14            let x = master.guess(guess);
15            wordlist = wordlist.filter(w => getMatches(guess, w) === x);
16        }
17    };
18
19    var getMatches = function(s1, s2) {
20        let matches = 0;
21        for (let i = 0; i < s1.length; i++)
22            if (s1[i] === s2[i])
23                matches++;
24        return matches;
25    };
26};
27

C# Solution

1
2csharp
3using System;
4using System.Collections.Generic;
5 
6public class Solution {
7    public void FindSecretWord(string[] wordlist, Master master) {
8        var rand = new Random();
9        for (var i = 0; i < 10; ++i) {
10            var guess = wordlist[rand.Next(wordlist.Length)];
11            var x = master.Guess(guess);
12            var newList = new List<string>();
13            foreach (var word in wordlist) {
14                if (Match(guess, word) == x) {
15                    newList.Add(word);
16                }
17            }
18            wordlist = newList.ToArray();
19        }
20    }
21    
22    private static int Match(string guessed, string word) {
23        var matches = 0;
24        for (var j = 0; j < guessed.Length; j++) {
25            if (guessed[j] == word[j]) {
26                matches++;
27            }
28        }
29        return matches;
30    }
31}

Please note that we are using a random picking strategy here, which means the solutions have a non-deterministic behavior which depends on the specific "randomness" at each runtime.# Conclusion

The above-specified approach provides the solution to the guessing game in Python, Java, JavaScript, C#, and C++. Since we're dealing with randomness, the number of guesses it takes may change each time we run our program.

However, the approach maintains its effectiveness through its repeated testing on a reduced sub-list. The list gets smaller after every guess, making it likely to find the secret word within the allowable 10 guesses.

The random choice method ensures we're examining different words every time; the filtering process discards words that are less likely to be the secret one. We're left with words that shared the same number of matching letters (in the right locations) with our previous guess.

The critical thought behind this solution is to use the information received from every guess to narrow down the list of possible secret words.

Despite the simplicity of this approach, we must also keep in mind that it may not guarantee the identification of the secret word within the given limit of 10 guesses in every possible scenario. For this reason, it possesses a probabilistic nature. However, it would work well in most cases, making it an efficient solution for this task.

Lastly, keep in mind that manipulating the 'Master' interface and its 'guess()' function implementation should be avoided for maintaining the integrity of the problem and solutions. The solutions mentioned here work under the assumption that these aspects remain unchanged.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

How does merge sort divide the problem into subproblems?

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following problems can be solved with backtracking (select multiple)

Not Sure What to Study? Take the 2-min Quiz:

In a binary min heap, the maximum element can be found in:

Fast Track Your Learning with Our Quick Skills Quiz:

What data structure does Breadth-first search typically uses to store intermediate states?


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫