Minimax (Java) - ShuweiLeung/Thinking GitHub Wiki
1.（843:Hard）（非常经典题）Guess the Word
- 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. 在每次选取第一个guess的字符串时，需要让其与secretmatch的值最大化，所以我们需要统计每个单词和其他单词的相似度，并选取其中与所有单词相似度最高的单词来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) //我们统计每个单词与其他单词match为0的个数，挑选match数最多的一个单词(与其他单词match值为0最少的单词)作为第一个猜的单词，从而可以有效减少wordList的大小(最大可能在10次guess中找到secret)
for (String w2 : wordlist)
if (match(w1, w2) == 0)
count.put(w1, count.getOrDefault(w1 , 0) + 1);
Pair<String, Integer> minimax = new Pair<>("", 1000); //寻找match=0最少的单词
for (String w : wordlist)
if (count.getOrDefault(w, 0) < minimax.getValue())
minimax = new Pair<>(w, count.getOrDefault(w, 0));
x = master.guess(minimax.getKey()); //获得选中单词与secret的match值
List<String> wordlist2 = new ArrayList<String>();
for (String w : wordlist)
if (match(minimax.getKey(), w) == x) //将所有与选中单词match值为x的单词都加入到新的wordList中，并重复以上过程
wordlist2.add(w);
wordlist = wordlist2.toArray(new String[0]);
}
}
public int match(String a, String b) { //判断a和b字符串match的数量
int matches = 0;
for (int i = 0; i < a.length(); ++i) if (a.charAt(i) == b.charAt(i)) matches ++;
return matches;
}