843. Guess the Word
Given 100 words of length 6, one of which is the target. You pick one at a time to query how many matches in letters between the one you pick and the target. Matches is calculated as:
"aabbcc" has 3 matches at index 0, 2, 4. You need to pick the target within 10 queries.
A simple solution would be after each query we filter the list of words. For example, the query says the picked one and the target has x matches. We check the matches of the picked one with all the words. Only keep the ones having x matches with the picked word. Next time, we just randomly pick one from the filtered list.
This solution won't pass. A better solution would be not randomly pick. We want the size of the filtered list to be small after a query. Given a word, there are only 7 possible outcomes of the query (0~6 matches). Each of the outcome would result in a different size of the filtered list. We use the maximum among the 7 as the indicator of whether we should pick it. We just compute the indicator of all the words in the list before we pick one with the smallest indicator.
The reason we use the maximum as the indicator is because we want to garantee the worst case since we only have 10 chances.
# """ # This is Master's API interface. # You should not implement it, or speculate about its implementation # """ # class Master: # def guess(self, word: str) -> int: import copy def get_matches(word1, word2): ret = 0 for i in range(len(word1)): if word1[i] == word2[i]: ret += 1 return ret def get_value(index, possible, f): count =  * 7 for j in possible: if j == index: continue count[f[index][j]] += 1 ret = 0 temp = 0 max_value = 0 for i in range(7): if count[i] == 0: continue ret += count[i] temp += 1 max_value = max(max_value, count[i]) return max_value return ret * 1.0 / temp def pick(possible, f): if len(possible) == 1: return possible ret = -1 min_value = 1000 for index in possible: value = get_value(index, possible, f) if value < min_value: ret = index min_value = value return ret class Solution: def findSecretWord(self, wordlist: List[str], master: 'Master') -> None: wordlist = wordlist checks = [True] * len(wordlist) possible = [i for i in range(len(wordlist))] f = [[get_matches(wordlist[i], wordlist[j]) for j in range(len(wordlist))] for i in range(len(wordlist))] while len(possible) != 0: # print('*') index = pick(possible, f) word = wordlist[index] num_matches = master.guess(word) if num_matches == 6: return possible = [i for i in possible if (get_matches(word, wordlist[i]) == num_matches and word != wordlist[i])]