趣题 Leetcode 843. Guess the Word

从这个题解获得了一些启发 https://leetcode.com/problems/guess-the-word/discuss/133862/Random-Guess-and-Minimax-Guess-with-Comparison

有趣的概率题

给一个wordlist，从里面选字母，每次guess会得到答案“有多少相同字母”。直到猜中。
没法保证有确切解。

Argument 1
假设当前选定字符串ss猜，得到guess(ss)->4。
此时我们可以缩小集合！再下次猜的时候，就从集合里把和ss相差4的挑出来。

Argument 2
（第一次猜）面对当前集合，假设集合大小为n，那么每个element的概率是1/n。
假设数据非常随机，我们希望稳定的把集合缩小，即：把意外概率压低。
因此针对里面的每个字符串str_i，我们计算：假设此次guess(str_i)返回的是0,1,2,3,4,5时，再下一轮guess之前，能剩下多大。

举例：集合 里面有18个string。
取出两个字符串A,B，计算假如guess(A)和guess(B)时，下一轮保留的集合大小为:
A[3,3,3,3,3,3]，以及B[9,0,1,3,4,1]
解释：若guess(B)返回4，则下一轮guess时，有B[4]==4个string参赛。
若guess(A)返回0，则下一轮guess时，有B[0]==3个string参赛。

那么我们当然就选guess(A)，因为A最稳定。假如选了B然后guess意外返回个0，那么下一轮是9个element参与选择，这么赌就方差太大了。
我们用稳定的方法选，平均猜logN次，N=100，最多10次的上限比较稳，因此不需要大方差去“搏”答案。

int cnt[MAXN][7];
memset(cnt, 0, sizeof(cnt));
for (auto idx : possible)
    for (auto target : possible)
        cnt[target][same[idx][target]]++;
int select_idx=possible.front(), minsame=possible.size();
for (auto idx : possible) {
    int tmp=0;
    for (int i=0; i<=6; i++)
        tmp = max(tmp, cnt[idx][i]);
    if (minsame > tmp)
        select_idx=idx, minsame=tmp;   
}

新的优化点

我觉得这个题还可以深入，应根据每次guess的结果实时调整概率。
followup : 假如现在还剩下k次机会guess，写出满足k次能最大概率猜出答案的算法？

eg1: 以上述算法举例，第一轮k=10，我们经粗略计算，发现目前来看使用“最平稳的猜测”（上述代码）可以使大部分结果落在k<10次内可以猜出。

eg2: 那么如果假如现在k=1，面对某个element的统计值A[2,1,2,6,18,1]以及B[5,5,5,5,5,5]
若选guess(A)：33%会返回1，33%会返回2，17%会返回6，17%会返回18
选A而不是B，虽然B稳定，但毫无胜出可能。
因此我们自底向上计算概率，当k已知时，我们可能会加大“方差”，而使答案更多的落在“<k次机会就可猜出”里面。

从另一个角度说，上面的说法也许有问题，guess(A)并不是33%概率会返回1，私以为计算这个33%时，应该前几次guess()时候也会有影响。
现在在看我们开头提出的方法，也是对概率的一种蔑视吧。