Poor pigs

目录
1. 原题解析
1.1. 题目
1.2. 题解
1.2.1. 数学方法
1.2.2. 动态规划方法
1.2.3. 信息论方法
2. 拓展
2.1. 修改后的题目
2.2. 回到算法题本身
2.2.1. 改版一：有2桶的毒药
2.2.2. 改版二：有未知桶毒药
3. 最后
4. 参考

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

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

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

“毒药”也是敏感词？

原题解析

题目

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

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

喂猪的规则如下：

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

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

题解

数学方法

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

  1. 当有 1 只小猪时，最多可以喝 times = minutesToTest / minutesToDie = 4 次水。
  2. 最多可以喝 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
  3. 那么 2 只小猪可以验证的范围最多到多少呢？我们把每只小猪携带的信息量看成是 base 进制数，2 只小猪的信息量就是 pow(base, 2) = pow(5, 2) = 25，所以当 5 ≤ buckets ≤ 25时，anwser = 2。
  4. 那么可以得到公式关系：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;
}

动态规划方法

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

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

那么，按照《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只小猪。当然，这只是理论上的最小值，如果无法给出可实施的方案，那这个结论是不成立的。

改版二：有未知桶毒药

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

最后

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

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

参考

发布者

Zhang

hope you enjoy my articles.

《Poor pigs》上有1条评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注