# 843. Guess the Word

## Problem

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:

"abbccd" and

"aabbcc" has 3 matches at index 0, 2, 4. You need to pick the target within 10 queries.

## Solution

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.

## Code

# """
# 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 = [0] * 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[0]
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])]