Poor pigs | Bran Zhang

本文从一条 LeetCode 算法题，研究了一下题目拓展后的情景，并结合言论审查赋予了拓展题一点点实际意义。

小插曲一：在写本文期间看到的笑话一则，真实性未验证：众网友为吐槽“浙江选考”，却发现微博屏蔽了部分“浙江选考”相关的搜索结果，问题既不是出在“浙江”上，也不是出在“选考”上，而是“江选”两个字。

小插曲二：在 LeetCode 的中文站上看题解时，发现好像有些词被屏蔽了，通过与题目描述对比，发现“毒药”是敏感词。

原题解析

题目

请听题：458. Poor Pigs，题目中文描述如下：

有 buckets 桶液体，其中正好有一桶含有毒药，其余装的都是水。它们从外观看起来都一样。为了弄清楚哪只水桶含有毒药，你可以喂一些猪喝，通过观察猪是否会死进行判断。不幸的是，你只有 minutesToTest 分钟时间来确定哪桶液体是有毒的。

喂猪的规则如下：

选择若干活猪进行喂养
可以允许小猪同时饮用任意数量的桶中的水，并且该过程不需要时间。
小猪喝完水后，必须有* minutesToDie* 分钟的冷却时间。在这段时间里，你只能观察，而不允许继续喂猪。
过了 minutesToDie 分钟后，所有喝到毒药的猪都会死去，其他所有猪都会活下来。
重复这一过程，直到时间用完。

给你桶的数目 buckets，minutesToTest 和 minutesToDie ，返回在规定时间内判断哪个桶有毒所需的最小猪数。

题解

数学方法

毕竟，这条题目给的标签就是 Math，想通之后的解法也很简单，就是一个数学公式。以总时间 minutesToTest = 60，死亡时间 minutesToDie = 15为例：

当有 1 只小猪时，最多可以喝 times = minutesToTest / minutesToDie = 4 次水。
最多可以喝 4 次水，能够携带 base = times + 1 = 5 个的信息量，也就是（便于理解从 0 开始）：
- (1) 喝 0 号死去，0 号桶水有毒
- (2) 喝 1 号死去，1 号桶水有毒
- (3) 喝 2 号死去，2 号桶水有毒
- (4) 喝 3 号死去，3 号桶水有毒
- (5) 喝了上述所有水依然活蹦乱跳，4 号桶水有毒
- 结论是 1 只小猪最多能够验证 5 桶水中哪只水桶有毒，当 buckets ≤ 5 时，answer = 1
那么 2 只小猪可以验证的范围最多到多少呢？我们把每只小猪携带的信息量看成是 base 进制数，2 只小猪的信息量就是 pow(base, 2) = pow(5, 2) = 25，所以当 5 ≤ buckets ≤ 25时，anwser = 2。
那么可以得到公式关系：pow(base, ans) ≥ buckets，取对数后即为：ans ≥ log(buckets) / log(base)，因为 ans 为整数，所以 ans = ceil(log(buckets) / log(base))。

因此，代码实现如下：

public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
    int times = minutesToTest / minutesToDie;
    int base = times + 1;
    double temp = Math.log(buckets) / Math.log(base);
    int ans = (int)Math.ceil(temp)
    return ans;
}

动态规划方法

既然提到了动态规划，来来来，动态规划算法三要素：

所有不同的子问题组成的表
解决问题的依赖关系可以看成是一个图
填充子问题的顺序（即对②的图进行拓扑排序，填充的过程称为状态转移）

那么，按照《Turn dynamic programming into mathematical formula》这篇文章中的思路，对应到上面三要素，

**子问题：**小猪的个数 n，以及有限时间内最多测试次数 t，t = minutesToTest / minutesToDie，可以判断 dp(n,t) 桶水，不同的 n 和 t 组成了子问题。

**问题的依赖关系：**当有 n 只小猪，最多测试次数为 t 时，

同时被 n 只猪喝，那么假设这桶水有毒，所有猪全死了，如果这类桶数量超过1，显然就无法判断具体是哪一桶了，因此这类桶最多一个（猪全死了就是它有毒）。
同时被 n-1 只猪喝，假设这桶水有毒，死了 n-1 只猪，那么只剩下一只猪和 t-1 轮喝水机会，那么这类水桶最多只能有 C(n,n-1) * dp(1,t-1) 个。
同时被n-k只猪喝，假设这桶水有毒，死了n-k只猪，那么只剩下k只猪和t-1轮喝水机会，那么这类水桶最多只能有 C(n,k) * dp(k,t-1) 个。
这一轮没有猪喝，那么假设这桶水有毒，只剩下n只猪和t-1轮喝水机会，那么这类桶最多只能有 C(n,0) * dp(n,t-1) 个。

因此，可以得到依赖关系：dp(n,t) = C(n,n) * dp(0,r-1) + C(n,n-1) * dp(1,r-1) + … + C(n,0) * dp(n,r-1)

**填充顺序：**按照先测试次数的增加，再小猪的个数增加来填充。

当然，原文最终对依赖关系中的计算逻辑进行了简化，简化到最后实际上也是一个数学公式，进而可以直接计算出结果。

信息论方法

“根据香农的信息论，信息熵 = 连加 – (每一项的概率*log(每一项的概率))。在此活动中每一项都是等概的。故计算结果：瓶子信息熵=log(瓶子数)，猪信息熵=log(状态数)，为了获得足够的信息需要的猪即为两个信息熵相除。”
— https://leetcode-cn.com/problems/poor-pigs/solution/jing-dian-xin-xi-lun-ti-mu-by-pi-xie-wang-bei-luo/

对应的代码实现如下：

int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
    int states = minutesToTest / minutesToDie + 1;
    return ceil(log(buckets) / log(states));
}

拓展

修改后的题目

假如那些水桶中有不止1桶有毒，比如：2桶有毒，或者未知桶有毒，那么，需要多少只小猪来试毒？

于是，上述对题目的改写，我联想到了一个实际场景，请听题：有一个论坛，其对敏感言论的审查平均时间为10分钟，一旦查出来某账户发表了敏感言论，将会被销号（你号没了）。但是平台又不公布敏感词。为此，假设现从某语料库中得到N个词语，问：在10小时内，判断出词库中每个词是否为敏感词，需要准备多少个账号？

在这里，我假设：

平台的敏感词审查是单纯的字符串比对，也就是遍历敏感词列表，判断发布的言论是否包含敏感词。
可以将词进行组合发布，并且论坛不限制内容的长度，就好比同一只小猪可以同时测试多个桶是否有毒。
组合发布的词使用标点隔开，使得平台无法将前后的词连接起来，也就是说算法题里不会出现文章开头“插曲一”的情形。

这样的一个问题，账号相当于小猪，发表一段内容相当于喝下若干桶的水，敏感词相当于毒药，言论的审查平均时间相当于毒药的发作时间，被销号相当于中毒身亡。这个问题等同于小猪试毒药的“未知桶有毒”的情形。

如果真的需要做成这样一件事情，其实还有很多细节可以深挖，比如：

初始的词汇准备。不同于词典中的词语，敏感词不仅仅是诸如 “政府，共产党，造反” 一些常见的词语，也会是人名，简称，拼音，英语单词，数字，混写等，比如 “薄熙来，江选，CNM，8964，2b”等。如果初始词汇准备的不够全面，那也就谈不上测出敏感词了。
有些网站会在言论发布时就提示文本中是否包含敏感词，反应到题目中就是言论的审查时间非常短，所以在这样的情况下算法在实际设计时需要考虑别的方面。

当然，有人会说，有很多的更加方便的得到敏感词列表的方式，在此，本文仅讨论算法本身，以上对题目的联想仅仅是犯病了。

回到算法题本身

为了方便算法问题的讨论，还是回到“小猪和毒药”的版本，下面就探讨一下毒药多于1桶时的情形。

问题描述：1000桶水，猪喝毒水后会在15分钟内死去，想用一个小时找到毒水，至少需要几只猪？

改版一：有2桶的毒药

《猪猪超进化：你的潜能，超乎你的想象！》这篇文章从各种方案实施的角度，列举了多种实施方式，得出的最少小猪使用量均为10只。但却无法证明是否可能只用9只小猪。

从信息论的角度，1000桶水里有2桶毒水，那么需要检验的点位有 (999+1)*999/2=499500 个（这公式怎么来的？），总共测试4轮，所以一只猪可以有5种状态，求解5^n>499500，n为正整数，lg(49500)/lg(5) ≈ 8.15，所以至少需要9只小猪。当然，这只是理论上的最小值，如果无法给出可实施的方案，那这个结论是不成立的。

改版二：有未知桶毒药

这个问题的复杂程度远超出我的想象，可以尝试用二分法之类的给出一个较为合理的解决方案，但目前做不到最优解。等有的进展再补充进来。（我真的会补坑，只要有进展）

最后

以上仅为从一条算法题出发，结合敏感言论审查所想到的一点点拓展而已。并无多少实际执行的意义，如果你耐心看完上文，会发现拓展后的题目是基于很多理想化的前提的，现实远没有那么简单。

言论的审查不仅在于交流上的不方便，频出的各种缩写，绰号，增加了交流的阻力，更使得每个人能够接受到的观点存在缺失。或许，这就是当猪的命吧。

参考

算法题中文描述：https://leetcode-cn.com/problems/poor-pigs/
算法题解法：https://leetcode-cn.com/problems/poor-pigs/solution/
Turn dynamic programming into mathematical formula：https://leetcode.com/problems/poor-pigs/discuss/94307/Turn-dynamic-programming-into-mathematical-formula
动态规划到通项公式：https://leetcode-cn.com/problems/poor-pigs/solution/dong-tai-gui-hua-dao-tong-xiang-gong-shi-by-defeat/
经典信息论题目：https://leetcode-cn.com/problems/poor-pigs/solution/jing-dian-xin-xi-lun-ti-mu-by-pi-xie-wang-bei-luo/
1000桶水中两桶有毒，猪喝毒水后会在15分钟内死去，想用一个小时找到毒水，至少需要几只猪？：https://www.zhihu.com/question/60461214