11-interactive.Rmd

# Interactive Problems


## Guess the Word / LeetCode 843 / Hard

### Description
We are given a word list of unique words, each word is 6 letters long, and one word in this list is chosen as
secret.

You may call master.guess(word) to guess a word.  The guessed word should have type string and must be from the
original list with 6 lowercase letters.

This function returns an integer type, representing the number of exact matches (value and position) of your guess to
the secret word.  Also, if your guess is not in the given wordlist, it will return -1 instead.

For each test case, you have 10 guesses to guess the word. At the end of any number of calls, if you have made 10 or
less calls to master.guess and at least one of these guesses was the secret, you pass the testcase.

Besides the example test case below, there will be 5 additional test cases, each with 100 words in the word list.
The letters of each word in those testcases were chosen independently at random from 'a' to 'z', such that every word
in the given word lists is unique.

### Example
Input: secret = "acckzz", wordlist = ["acckzz","ccbazz","eiowzz","abcczz"]

master.guess("aaaaaa") returns -1, because "aaaaaa" is not in wordlist.
master.guess("acckzz") returns 6, because "acckzz" is secret and has all 6 matches.
master.guess("ccbazz") returns 3, because "ccbazz" has 3 matches.
master.guess("eiowzz") returns 2, because "eiowzz" has 2 matches.
master.guess("abcczz") returns 4, because "abcczz" has 4 matches.

We made 5 calls to master.guess and one of them was the secret, so we pass the test case.

### Solution
#### Walkthrough
At start of the game, we simply have the choice of using each word in the wordlist to call master API, but as we are
getting more and more feedbacks from the API, we should eliminate some choice by only keeping the words that have the
same number of character matches as the match number returned from the master API. Then we use those words as the
possible choices in the next round.

Simply adapting the above strategy should give us a pretty good performance in terms of minimizing the number of
calls to the master API. However, we could use minimax strategy to further improve the accuracy of our guesses at
each round by avoiding choices that has little or no effect of reducing the number of choices we have to make in the
next round.

The idea is simply to make a choice that minimizes the maximum possible number of choices (worst outcome) we have to
make at each time that we call master.guess(word).

#### Analysis
Time Complexity is O() since this is the number of  computation performed.

#### Algorithm
minimax \@ref(minimax)

#### Java Code
```java
final int N = 6;

public void findSecretWord(String[] words, Master master) {
    List<Integer> wordIdxList = new ArrayList<>();

    //init dictionary
    for (int idx = 0 ; idx < words.length; idx++) {
        wordIdxList.add(idx);
    }

    while (wordIdxList.size() > 0) {
        int minLoss = Integer.MAX_VALUE;
        int minIdx = -1;
        for (int idx : wordIdxList) {
            int loss = maxLoss(idx, words, wordIdxList);

            /* minimizes the possible number of choices (worst outcome) to make at each time that we call master.guess */
            if (loss < minLoss) {
                minLoss = loss;
                minIdx = idx;
            }
        }

        int match = master.guess(words[minIdx]);
        //made the correct guess, return
        if (match == N) {
            return;
        }
        List<Integer> nextIdxList = new ArrayList<>();
        for (int idx: wordIdxList) {
            if (similarity(words[minIdx], words[idx]) == match) {
                nextIdxList.add(idx);
            }
        }
        wordIdxList = nextIdxList;
    }
}


/*
* Retrieve the MAX # of word from CURRENT dict that has the same similarity with
* guessed word, where guessWord != candidateWord.
*/
private int maxLoss(int guessIdx, String[] words, List<Integer> wordIdxList) {
    int[] bucket = new int[N];
    int maxScore = 0;

    for (int idx : wordIdxList) {
        String guess = words[guessIdx];
        String candidate = words[idx];

        if (!guess.equals(candidate)) {
            int score = similarity(guess, candidate);
            bucket[score]++;
        }
    }

    for(int score : bucket) {
        maxScore = Math.max(maxScore, score);
    }

    return maxScore;
}

private int similarity(String s1, String s2) {
    int match = 0;
    for (int i = 0; i < N; i++) {
        match += s1.charAt(i) == s2.charAt(i) ? 1 : 0;
    }
    return match;
}
\end{lstlisting}
```