Poor pigs

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

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

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

“毒药”也是敏感词?

原题解析

题目

请听题:458. Poor Pigs,题目中文描述如下:

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

喂猪的规则如下:

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

给你桶的数目 bucketsminutesToTestminutesToDie ,返回在规定时间内判断哪个桶有毒所需的最小猪数。

题解

数学方法

毕竟,这条题目给的标签就是 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只小猪。当然,这只是理论上的最小值,如果无法给出可实施的方案,那这个结论是不成立的。

改版二:有未知桶毒药

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

最后

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

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

参考

发表评论

您的电子邮箱地址不会被公开。