algorithm - 反常的刽子手问题

Question

Perverse Hangman 是一款与常规 Hangman 游戏非常相似的游戏，但有一个重要区别:获胜单词由学院根据猜中的字母动态确定。

例如，假设您有棋盘 _ A I L 和 12 个剩余的猜测。因为有 13 个不同的单词以 AIL 结尾(bail、fail、hail、jail、kail、mail、nail、pail、rail、sail、tail、vail、wail)，所以无论你猜哪 12 个字母，房子都一定会赢, 房子会声称所选的单词是你没有猜到的。但是，如果棋盘是 _ I L M，那么您就把房子逼到了墙角，因为 FILM 是唯一以 ILM 结尾的单词。

挑战是:给定字典、单词长度和允许猜测的次数，提出一种算法:

a) 证明玩家总是赢，无论发生什么情况，都为进入房屋角落的玩家输出决策树

b) 通过输出一个无论如何都允许房子逃脱的房子的决策树来证明房子总是赢。

作为玩具示例，考虑字典:

bat
bar
car

如果允许您猜错 3 次，则玩家赢取以下树:

Guess B
NO -> Guess C, Guess A, Guess R, WIN
YES-> Guess T
      NO -> Guess A, Guess R, WIN
      YES-> Guess A, WIN

Answer 1

这与“如何通过反复称量找到奇数硬币？”几乎是一模一样的。问题。基本的见解是，您正在尝试最大化从猜测中获得的信息量。

构建决策树的贪心算法如下:- 对于每个猜测，选择答案为“真”和答案为“假”的猜测尽可能接近 50-50，因为理论上这提供了最多的信息。

令 N 为集合的大小，A 为字母表的大小，L 为单词中的字母数。

所以把你所有的话放在一个集合里。对于每个字母位置，以及字母表中的每个字母，计算该位置有多少个单词(这可以通过额外的哈希表进行优化)。选择大小最接近集合一半的计数。这是 O(L*A)。

将集合一分为二，取在这个位置有这个字母的子集，并使这两个分支成为树。对每个子集重复，直到你拥有整棵树。在最坏的情况下，这将需要 O(N) 步，但如果你有一个很好的字典，这将导致 O(logN) 步。