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])]