@@ -0,0 +1,2020 @@
+import collections%0Aimport random%0A%0Aimport unittest%0Afrom typing import List%0A%0AWORD_LENGTH = 6%0A%0A%0Adef get_num_matches(a, b):%0A    return sum(1 for i in range(WORD_LENGTH) if a%5Bi%5D == b%5Bi%5D)%0A%0A%0A# O(n%5E2) time. O(n%5E2) space. Minimax.%0Aclass Solution:%0A    def findSecretWord(self, wordlist, master):%0A        %22%22%22%0A        :type wordlist: List%5BStr%5D%0A        :type master: Master%0A        :rtype: None%0A        %22%22%22%0A        graph = collections.defaultdict(lambda: %5B%5B%5D for _ in range(WORD_LENGTH + 1)%5D)%0A%0A        for i, a in enumerate(wordlist):%0A            for j in range(i + 1, len(wordlist)):%0A                b = wordlist%5Bj%5D%0A                num_matches = get_num_matches(a, b)%0A                graph%5Ba%5D%5Bnum_matches%5D.append(b)%0A                graph%5Bb%5D%5Bnum_matches%5D.append(a)%0A%0A        candidates = set(wordlist)%0A%0A        while True:%0A            word = min(candidates, key=lambda candidate: len(graph%5Bcandidate%5D%5B0%5D))%0A            num_matches = master.guess(word)%0A%0A            if num_matches == WORD_LENGTH:%0A                return%0A            candidates.intersection_update(graph%5Bword%5D%5Bnum_matches%5D)%0A%0A%0Adef random_word():%0A    return ''.join(chr(random.randint(ord('a'), ord('z'))) for _ in range(WORD_LENGTH))%0A%0A%0Aclass Master:%0A    def __init__(self):%0A        self.ok = False%0A        self.attempts = 0%0A        self.wordlist = %5Brandom_word() for _ in range(100)%5D%0A        self.secret_word = random.choice(self.wordlist)%0A%0A    def guess(self, word):%0A        %22%22%22%0A        :type word: str%0A        :rtype int%0A        %22%22%22%0A        self.attempts += 1%0A        num_matches = get_num_matches(self.secret_word, word)%0A        if num_matches == WORD_LENGTH:%0A            self.ok = True%0A        return num_matches%0A%0A%0Aclass Test(unittest.TestCase):%0A    def test(self):%0A        for _ in range(10):%0A            master = Master()%0A            solution = Solution()%0A            solution.findSecretWord(master.wordlist, master)%0A            self.assertEqual(True, master.ok)%0A            self.assertLessEqual(master.attempts, 10)%0A%0A%0Aif __name__ == '__main__':%0A    unittest.main()%0A

843. Guess the Word