LeetCode 843 - Guess the Word

https://leetcode.com/problems/guess-the-word/

This problem is an interactive problem new to the LeetCode platform.

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 1:
Input: secret = "acckzz", wordlist = ["acckzz","ccbazz","eiowzz","abcczz"]

Explanation:

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.

X.  random choose and exclude not match words
https://blog.csdn.net/u011439455/article/details/80482508
https://www.jianshu.com/p/b77ae5d669b1

基于贪心策略，我们应该要利用好系统的反馈机制，避免我们浪费查询机会。我们的目标应该是提高每次的 matches 值，即每次都要淘汰词表里不等于matches的单词，缩小我们枚举范围。
每次查询之后，如果matches不等于6，我们虽然还不知道"secret"。但我们知道哪些一定不是"secret"，进而缩小范围，逼近答案。

    int match(const string a, const string b){
        int ans = 0;
        
        for(int i = 0;i<a.length(); i++){
            if(a[i] == b[i]) ++ans;
        }
        
        return ans;
    }
    
    void shrinkWordList(vector<string>& wordlits, const string guessWord, const int matches){
        vector<string> tmp;
        
        
        for(string word : wordlits){
            int m = match(word, guessWord);
            if(m == matches){
                tmp.push_back(word);
            }
        }
        
        wordlits = tmp;
    }
    
    void findSecretWord(vector<string>& wordlist, Master& master) {
        
        string target = wordlist[random() % wordlist.size()];
        int Count = 10;
        while(Count--){
            int matches = master.guess(target);
            
            shrinkWordList(wordlist, target, matches);
            
            target = wordlist[random() % wordlist.size()];
        }
        
    }

X. Random Guess and Minimax Guess with Comparison
https://leetcode.com/problems/guess-the-word/discuss/133862/Random-Guess-and-Minimax-Guess-with-Comparison

The description emphasize that the wordlist is generated randomly and it's does have a reason.

There is no solution that can guarantee to find a secret word in 10 tries. If I make up a test case with wordlist like ["aaaaaa", "bbbbbb" ...., "zzzzzz"], it need 26 tries to find the secret.

So 10 tries is just a limit to test reasonable solution. And this problem is more than finding right output for given input, it's more about a strategy.

Intuition:
Take a word from wordlist and guess it.
Get the matches of this word
Update our wordlist and keep only the same matches to our guess.

For example we guess "aaaaaa" and get matches x = 3, we keep the words with exactly 3 a.

Also we need to know the matches between two words, so a sub function as following will be helpful.

    public int match(String a, String b) {
        int matches = 0;
        for (int i = 0; i < a.length(); ++i) if (a.charAt(i) == b.charAt(i)) matches ++;
        return matches;
    }

This process is straight forward.
However, the key point is, which word should we guess from all of the wordlist?

First of all, I guessed the first word from wordlist.
Unfortunately, I didn't get a lucky pass.
This problem has only 5 test cases but they are good.

But I didn't give up this idea. All words are generated randomly.
So why not we also guess a random word and let it be whatever will be.
So here it is this idea and it can get accepted.

    public void findSecretWord(String[] wordlist, Master master) {
        for (int i = 0, x = 0; i < 10 && x < 6; ++i) {
            String guess = wordlist[new Random().nextInt(wordlist.length)];
            x = master.guess(guess);
            List<String> wordlist2 = new ArrayList<>();
            for (String w : wordlist)
                if (match(guess, w) == x)
                    wordlist2.add(w);
            wordlist = wordlist2.toArray(new String[wordlist2.size()]);
        }
    }

https://leetcode.com/problems/guess-the-word/discuss/164744/Java-with-Explanations

I said I could get accepted but not for sure. In fact it has 80% rate to get accepted.

Now we want to find a solution that improve this rate. We should guess a word that can minimum our worst case.

Generally, we will get 0 matches and wordlist size reduce slowly.

So we compare each two words and for each word, we note how many 0 matches it gets.

Then we guess the word with minimum 0 matches.

So even in most cases we get 0 match from master, it's still the best word that we can guess.

Because the wordlist will reduce at minimum as possible.

Time Complexity and Result Analyse

To be more convincing, I test each approach with 1000 test cases.
For the random approach, time complexity O(N), average 6.5 guess, worst case 14 guess.
For the minimax approach, time complexity O(N^2), average 5.5 guess, worst case 10 guess.

    public void findSecretWord(String[] wordlist, Master master) {
        for (int i = 0, x = 0; i < 10 && x < 6; ++i) {
            HashMap<String, Integer> count = new HashMap<>();
            for (String w1 : wordlist)
                for (String w2 : wordlist)
                    if (match(w1, w2) == 0)
                        count.put(w1, count.getOrDefault(w1 , 0) + 1);
            Pair<String, Integer> minimax = new Pair<>("", 1000);
            for (String w : wordlist)
                if (count.getOrDefault(w, 0) < minimax.getValue())
                    minimax = new Pair<>(w, count.getOrDefault(w, 0));
            x = master.guess(minimax.getKey());
            List<String> wordlist2 = new ArrayList<String>();
            for (String w : wordlist)
                if (match(minimax.getKey(), w) == x)
                    wordlist2.add(w);
            wordlist = wordlist2.toArray(new String[0]);
        }
    }

X.
https://www.cnblogs.com/lightwindy/p/9795777.html

这是一个Leetcode平台新型的交互式问题
给定一个不重复的词表，里面都是只有6个小写字母的单词。然后，系统会随机选定一个单词作为 "secret"

你可以调用系统提供的API master.guess(word) 来查询word 是否就是 "secret"。
这个API返回的参数是个整型，表示查询的匹配程度。

对于每个测试用例，你有10次查询机会。如果你能在10次以内的查询中找出 "secret" 则判定你通过用例。

任何绕过判定的做法都会被视为非法。

解法：Random Guess and Minimax Guess with Comparison

X. http://hehejun.blogspot.com/2018/11/leetcodeguess-word.html
这道题是猜数字的游戏，通常这类题目我们仍然是运用minimax的思路，对于所有可能成为答案的candidates：

• 对于每一个数，我们要算其在所有match可能(0-5)下，能eliminate的最少数量，我们称其为这个pick的score。考虑最坏的情况，这就是min
• 那么对于所有可能pick的数，我们取score最大的。在所有可选的范围内选择最优的，这就是max

我们需要preprocess建立一个match的表，维护了每两个string match的情况。然后对于每一个可能的pick，和match数m，我们计算其可以排除掉的数，即如果string和pick的match数不为m，那么肯定不是当前条件的答案的候选，所以排除。时间复杂度O(N^2 * log N)，每一次pick的过程是O(N^2)，每次应该pick之后至少应该能排除一半，所以是log N，

Approach #1: Minimax with Heuristic [Accepted]

We can guess that having less words in the word list is generally better. If the data is random, we can reason this is often the case.

Now let's use the strategy of making the guess that minimizes the maximum possible size of the resulting word list. If we started with $N$ words in our word list, we can iterate through all possibilities for what the secret could be.

Algorithm

Store H[i][j] as the number of matches of wordlist[i] and wordlist[j]. For each guess that hasn't been guessed before, do a minimax as described above, taking the guess that gives us the smallest group that might occur.

• Time Complexity: $O(N^2 \log N)$, where $N$ is the number of words, and assuming their length is $O(1)$. Each call to solve is $O(N^2)$, and the number of calls is bounded by $O(\log N)$.
• Space Complexity: $O(N^2)$.

  int[][] H;

  public void findSecretWord(String[] wordlist, Master master) {

    int N = wordlist.length;

    H = new int[N][N];

    for (int i = 0; i < N; ++i)

      for (int j = i; j < N; ++j) {

        int match = 0;

        for (int k = 0; k < 6; ++k)

          if (wordlist[i].charAt(k) == wordlist[j].charAt(k))

            match++;

        H[i][j] = H[j][i] = match;

      }

    List<Integer> possible = new ArrayList();

    List<Integer> path = new ArrayList();

    for (int i = 0; i < N; ++i)

      possible.add(i);

    while (!possible.isEmpty()) {

      int guess = solve(possible, path);

      int matches = master.guess(wordlist[guess]);

      if (matches == wordlist[0].length())

        return;

      List<Integer> possible2 = new ArrayList();

      for (Integer j : possible)

        if (H[guess][j] == matches)

          possible2.add(j);

      possible = possible2;

      path.add(guess);

    }

  }

  public int solve(List<Integer> possible, List<Integer> path) {

    if (possible.size() <= 2)

      return possible.get(0);

    List<Integer> ansgrp = possible;

    int ansguess = -1;

    for (int guess = 0; guess < H.length; ++guess) {

      if (!path.contains(guess)) {

        ArrayList<Integer>[] groups = new ArrayList[7];

        for (int i = 0; i < 7; ++i)

          groups[i] = new ArrayList<Integer>();

        for (Integer j : possible)

          if (j != guess) {

            groups[H[guess][j]].add(j);

          }

        ArrayList<Integer> maxgroup = groups[0];

        for (int i = 0; i < 7; ++i)

          if (groups[i].size() > maxgroup.size())

            maxgroup = groups[i];

        if (maxgroup.size() < ansgrp.size()) {

          ansgrp = maxgroup;

          ansguess = guess;

        }

      }

    }

    return ansguess;

  }

https://leetcode.com/problems/guess-the-word/discuss/134251/Optimal-MinMax-Solution-(%2B-extra-challenging-test-cases)

X.
https://www.cnblogs.com/haoweizh/p/10202516.html
思考下为什么这个算法会失败，直观上来说，我们希望每次剪枝都能删除尽可能多的字符串，而随机挑选字符串的策略并不能满足要求，所以我以第一个字符为目标，在第一个字符出现频率最高的所有字符串中随机挑选一个字符串，然后再进行迭代，这样就可以保证每次都能删掉尽可能多的字符串。不过这道题我还有个疑问，我们是否能够保证在十次之内必定能找到目标字符串，能否用数学方式证明这个结论是否正确。

11     int getMatch(string &a,string &b){
12         int count = 0;
13         for(int i = 0;i != a.size();++i){
14             if(a[i] == b[i])
15                 count++;
16         }
17         return count;
18     }
19     char getMost(vector<string>& words){
20         vector<int> v(26,0);
21         int maximal = 0;
22         char result;
23         for(string s:words)
24             v[s[0]-'a']++;
25         for(int i = 0;i != 26;++i){
26             if(v[i] > maximal){
27                 maximal = v[i];
28                 result = 'a'+i;
29             }
30         }
31         return result;
32     }
33     void findSecretWord(vector<string>& wordlist, Master& master) {
34         char c = getMost(wordlist);
35         vector<string> vec(wordlist.begin(),wordlist.end());
36         string str;
37         for(string s:wordlist){
38             if(s[0] == c){
39                 str = s;
40                 break;
41             }
42         }
43         while(true){
44             vector<string> t;
45             int match = master.guess(str);
46             if(match == 6) return;
47             for(int i = 0;i != vec.size();++i){
48                 if(getMatch(str,vec[i]) == match && str != vec[i])
49                     t.push_back(vec[i]);
50             }
51             c = getMost(t);
52             for(string s:t){
53                 if(s[0] == c){
54                     str = s;
55                     break;
56                 }
57             }
58             vec = t;
59         }
60     }

https://docs.google.com/document/d/1qxA2wps0IhVRWULulQ55W4SGPMu2AE5MkBB37h8Dr58/edit#heading=h.gsbh7qxi4gdo

Guess word改版

给一个矩阵，在里面找一个gift，不知道gift坐标，然后每次pick一个点，告诉你是更近了还是更远了还是距离不变, 距离是曼哈顿距离，要求用最少的猜测次数找到gift

思路：KD tree算法

	0	1	2	3	4
0
1
2
3		gift
4

从（0，0）开始，先二分列坐标，看(0, 4)，如果04比00近，说明gift在j = 2的右边矩阵中，如果04比00远，在j = 2的左边矩阵中，如果相等，说明gift在j=2这条线上

一直二分到 l == r找到gift所在列

然后二分行坐标，直到找到gift

参考代码：

Provider: null

   public int guess(int i1, int j1, int i2, int j2) {

    int x = 3;

    int y = 1;

    int dist1 = Math.abs(i1 - x) + Math.abs(j1 - y);

    int dist2 = Math.abs(i2 - x) + Math.abs(j2 - y);

    return dist1 - dist2;

   }

   private void guessGift(int rows, int cols) {

    int left = 0, right = cols - 1;

    while (left < right) {

    int res = guess(0, left, 0, right);

    int mid = left + (right - left) / 2;

    if(res == 0) {

    left = mid;

    break;

    } else if(res < 0) {

    right = mid - 1;

    } else {

    left = mid + 1;

    }

    }

    int top = 0, bot = rows - 1;

    while (top < bot) {

    int mid = top + (bot - top) / 2;

    int res = guess(top, left, bot, left);

    if(res == 0) {

    break;

    } else if(res < 0) {

    bot = mid  - 1;

    } else {

    top = mid + 1;

    }

    }

    System.out.println(top + ", " + left);

   }