Problem statement

https://leetcode.com/problems/guess-the-word/

Solution 1

Quite difficult for me problem, mainly because of new interactive concept. Note, that there is always will be small probability, that solution will not be accepted, and I do not like it.

So, what is the main idea here? We have a list of words, and we need to find the secret word among these words. Let us try the following strategy: choose some of this words (how exactly, a bit later), apply master.guess() function to this word, imagine we have result t. Now, for every other word, we compare how many matches we have with given word, and if number if not t, we can for sure eliminate this word. We continue this process, until we have only one word left or we found word with 6 matches.

So, now the question, how to choose the word we want to test?

  1. We can just choose first word (or last, or random) and if we are lucky testing system will admit this solution, I tried it and it is working sometimes.
  2. Choose the word, such that if we delete it, we can eliminate the biggest number of words. Note first of all, that there is $(25/26)^6 \approx 0.8$ probability that two words will not have any matches at all, because it is given that letters chosen uniformly independent. So, let us for each word find number of words such that number of matches is equal to $0$ and chose mininmum of them. Why minimum and not maximum? Imagine we found word, which has 0 matches with any other word, then if it happen that master.guess() is equal to 0 (and it happen with probability 0.8), then we will not eliminate anything at all.

Complexity

Time complexity is O(n^2*log n) in average, because on each iteration we spend O(n^2) time and potentially we have O(log n) iterations.

Code

class Solution:
    def findSecretWord(self, wordlist, master: 'Master'):
        def match(w1, w2): return sum(i==j for i,j in zip(w1, w2))
        
        while wordlist:
            count = Counter(w1 for w1, w2 in permutations(wordlist, 2) if match(w1, w2) == 0)
            guess = min(wordlist, key=lambda w: count[w])
            t = master.guess(guess)
            if t == 6: return
            wordlist = [w for w in wordlist if match(w, guess) == t]

Solution 2

We also can use another heuristic to choose the best word: for each of 6 places and 26 letters we first count how many words have them. Then we choose the word, which highest score: the word, which in some sense most similar to all others.

Complexity

Time complexity will be O(n log n).

Code

class Solution:
    def findSecretWord(self, wordlist, master: 'Master'):
        def match(w1, w2): return sum(i==j for i,j in zip(w1, w2))
        
        while wordlist:
            count = [Counter(w[i] for w in wordlist) for i in range(6)]
            guess = max(wordlist, key=lambda w: sum(count[i][c] for i, c in enumerate(w)))
            t = master.guess(guess)
            if t == 6: return
            wordlist = [w for w in wordlist if match(w, guess) == t]