<p>You are given an array of unique strings <code>words</code> where <code>words[i]</code> is six letters long. One word of <code>words</code> was chosen as a secret word.</p>

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

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

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

<p>For each test case, you should call <code>Master.guess</code> with the secret word without exceeding the maximum number of allowed guesses. You will get:</p>

<ul>
	<li><strong><code>&quot;Either you took too many guesses, or you did not find the secret word.&quot;</code></strong> if you called <code>Master.guess</code> more than <code>allowedGuesses</code> times or if you did not call <code>Master.guess</code> with the secret word, or</li>
	<li><strong><code>&quot;You guessed the secret word correctly.&quot;</code></strong> if you called <code>Master.guess</code> with the secret word with the number of calls to <code>Master.guess</code> less than or equal to <code>allowedGuesses</code>.</li>
</ul>

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> secret = &quot;hamada&quot;, words = [&quot;hamada&quot;,&quot;khaled&quot;], allowedGuesses = 10
<strong>Output:</strong> You guessed the secret word correctly.
<strong>Explanation:</strong> Since there are two words, you can guess both.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= words.length &lt;= 100</code></li>
	<li><code>words[i].length == 6</code></li>
	<li><code>words[i]</code> consist of lowercase English letters.</li>
	<li>All the strings of <code>wordlist</code> are <strong>unique</strong>.</li>
	<li><code>secret</code> exists in <code>words</code>.</li>
	<li><code>10 &lt;= allowedGuesses &lt;= 30</code></li>
</ul>

# """
# This is Master's API interface.
# You should not implement it, or speculate about its implementation
# """
# class Master:
#     def guess(self, word: str) -> int:

class Solution:
    def findSecretWord(self, words: List[str], master: 'Master') -> None:
        words.sort()
        maxScore = 0
        guesses = 0
        valids = []
        while len(words) > 0:
            word = self.findGuess(words)
            #print(f"guessing:{word}")
            guessRes = master.guess(word)
            #print(f"got score:{guessRes}")
            if guessRes == 6:
                #print(f"found in {guesses} guesses")
                return
            elif guessRes > maxScore:
                # sort each word by how many letters it has in common with 'word'
                #print(f"found higher score with:{word}")
                words = [ w for w in words if word != w and self.commonLetters(word, w) >= guessRes]
                maxScore = guessRes
                valids = [word]
                counter = 0
            elif guessRes == 0:
                #if nothing is correct, filter out anything similar to this string
                #print(f"found 0 score with:{word}")
                words = [ w for w in words if word != w and self.commonLetters(word, w) == 0]
                maxScore = guessRes
                counter = 0
            else:
                if maxScore != 0 and guessRes == maxScore:
                    #print(f"found same score with:{word}")
                    valids.append(word)
                    # see what matches in the valids
                    match = self.checkMatch(valids[0], valids[1], guessRes)
                    if match:
                        # if there is an exact match, filter out
                        #print(f"found exact match")
                        words = [ w for w in words if word != w and self.findMatch(match, w)]
                        valids = valids[1:]
                words= [w for w in words if word != w]
            #print(f"list:{words}")
            #print(f"len:{len(words)}")
            guesses+=1
    def commonLetters(self, word1, word2):
        # always 6
        count = 0
        for i in range(len(word1)):
            if word1[i] == word2[i]:
                count+=1
        return count
    def checkMatch(self, word1, word2, sim):
        if self.commonLetters(word1, word2) == sim:
            # we know the common letters are valid in this case]
            match = ""
            for i in range(len(word1)):
                if word1[i] == word2[i]:
                    match+=word1[i]
                else:
                    match+='*'
            return match
        return None

    def findMatch(self, match, test):
        for i in range(len(match)):
            char = match[i]
            if char != '*':
                if test[i] != char:
                    return False
        return True

    def findGuess(self, words):
        freq = {}
        #print(f"finding freq for {words}")
        for word in words:
            wordFreq = [1,1,1,1,1,1]
            for w in freq:
                for i in range(len(word)):
                    if word[i] == w[i]:
                        wordFreq[i]+=1
                        freq[w][i]+=1
            freq[word] = wordFreq
        return max(freq, key = lambda x: sum(freq[x]))
                
16800