Find the Secret - Solution Explained

I haven't used LeetCode or other learning platforms for a very long time. I used to enjoy them, even years after starting to work as a professional developer. They're fun little challenges to keep us entertained and sharp.

After probably 5 years I've been doing a few, and recently found a problem that I enjoyed very much. It's pretty simple, but made me think a bit.

As there are no solutions posted on LeetCode with an explanation, at least for TypeScript, I've decided to write this post to explain my thoughts, process and solution.

The problem ❓

Guess the Word @ LeetCode

Description:

You are given an array of unique 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 a word that exists in words.

There is a parameter allowedGuesses for each test case where allowedGuesses is the maximum number of times you can call Master.guess(word). Note that you don't have access to that value.

For each test case, you should call Master.guess with the secret word without exceeding the maximum number of allowed guesses.

In simpler terms:

You have to guess a secret word that is inside an array of words, without exceeding the number of allowed guesses. The caveat is that the allowed guesses could be less than the amount of possible words. i.e. there are 35 words but you only have 10 guesses.

NOTE: If you haven't done it, and what a little challenge, consider trying to complete it before reading the rest of the post!

Guess the Word

Seems impossible... 🤔

At first glance, you might think it's impossible to find. Of course, by brute force, it's not possible in cases where the amount of words is greater than the allowed guesses.

However, as the question description hints, the words are not random, and it can be done using the correct strategy.

The strategy 🤓

The obvious or not-so-obvious solution would be to try to reduce the amount of words we have to check every iteration.

Luckily the Master.guess() returns the amount of matches that the word has (letter and position). So, we can use this information to skip words that could not, by any chance, be the solution.

For example, the secret is xabxvv, if we test aabbcc, it gives 2 matches (-ab----). We don't know what the matches are though, but we know that the correct word must at least have the 2 matches that this word has. This means that we can then remove any other words that do not contain at least 2 characters in the same position as the word we just tested. i.e. For example the word xaxbbzz only contains one match (-a----), so we can remove it. But xabbxx contains ab in the same position, so we can keep this word.

We do this for all the remaining words, by the next iteration we have reduced the number of words to check by a lot. Then we just repeat this process until we find the secret word.

Let's visualize it 👀

Words:

[
  "ycbfps","peayuf","yiejjw","rcbbps","trlccr","jxwhkz",
  "ldzccp","nqsjoa","qrjasy","pcldos","acrtag","buyeia",
]

Secret Word: pcldos

• 1 - We loop until we find the word

• 2 - We remove the the first or last word from the words array (ycbfps), and make a guess. The word has 2 matches (-c---s), but we don't know which ones.

  • 2.1 - We decide whether to get the last or first element based on the last guess. If the last guess had no matches, we switch to the other end of the array. This is done in case all words that are before or after the secret have no matches. Imagine that you have 10 guesses, and the first 11 words do not have any match. It wouldn't find the word in the given guesses. By switching back and forth, we have a greater chance of finding the secret.

• 3 - We then filter out any words that do not contain at least 2 characters in common with the guessed word.

This code will make it easier to explain:

let matching = 0;

for (let i = 0; i < otherWord.length; i++) {
  if (otherWord.charAt(i) == word.charAt(i)) {
    matching++;
  }
}

return matching >= matches;

• word is the word we just guessed.
• matches is the result of the guess, the amount of matching characters in word.

The code will be executed for each word that remains in the words array (excluding the word we just guessed). If it returns true the word will be kept, otherwise it's removed from the words array.

Then it loops over the indexes from 0 to word.length, then checks if the character at index i is the same in both the word and the otherWord, and adds up every matching character.

If the otherWord does not contain at least the same amount of matches, it means that it's impossible that the word is the secret. Because the secret word must have more matches than the guessed word.

By doing this we can discard a lot of words very fast.

In this example we'd go from all these words (12):

[
  "ycbfps","peayuf","yiejjw","rcbbps","trlccr","jxwhkz",
  "ldzccp","nqsjoa","qrjasy","pcldos","acrtag","buyeia",
]

To just (2):

[ 'rcbbps', 'pcldos' ]

This is done in one iteration, by the next iteration, we'll just have the secret word. Done in 3 guesses, instead of 10.

• 4 - We repeat step 1 until we find the secret.

Each iteration will remove many words. Reducing the amount of guesses needed to find the secret.

 The implementation 💻

function findSecretWord(words: string[], master: Master) {
  let lastHasMatch = false;

  while (true) {
    let word = lastHasMatch ? words.shift() : words.pop();
    let matches = master.guess(word);

    if (matches === 0) {
      lastHasMatch = !lastHasMatch;
      continue;
    }

    if (matches === 6) return word;

    words = words.filter((w) => {
      let matching = 0;

      for (let i = 0; i < w.length; i++) {
        if (w.charAt(i) == word.charAt(i)) {
          matching++;
        }
      }

      return matching >= matches;
    });
  }
};

Summary

Once you know the strategy it's pretty straightforward, but if you don't it seems impossible. But that's the key, acknowledging that it's impossible to guess all the words makes us think of a way of not having to do it. In this case, discard words that we can determine are not possibly the secret.

The solution I came up with is not optimal. It assumes certain things that would not work in other scenarios. Like assuming words are of the same length, and knowing that we will find the secret and that the secret is 6 characters long (that's why there's a while(true) loop).

I would tell you the space and time complexity of the code, but in all honesty, I don't care, and I don't know how to calculate it (I've never had to do it xD).

So yeah, that's it. A cool little problem that makes you think!