我如何处理Kik谜语

几周前, Kik带着一个有趣的谜语和一个潜在的奖金悄悄地出现在我当地的大学subreddit上。 那是考试季,但是我要输什么呢?

考虑1000瓶相同的葡萄酒,但其中一瓶中毒。 您有十只老鼠可供使用,如果老鼠从中毒的瓶子中喝水,它就会呕吐。 如果您想继续阅读,请尝试一下。


一种解决方案是给每个瓶子编号,将每只大鼠视为一个二进制数字,并且如果该大鼠的二进制数字在瓶子的二进制表示中为“ 1”,则让每只大鼠喝一个瓶子。 然后,考虑按二进制呕吐的大鼠,找出罪魁祸首! 用10只老鼠,我们可以用这种方式识别多达21个= 1024瓶。

这个谜语的Kik变体更具挑战性:如果有两个中毒的瓶子,并且能够抛出更多假阳性F呢? 您能最大化瓶子N的数量同时最小化所需老鼠R的数量吗? 具体来说,最大化N /( R * max( F ,1))。

我付诸实践,开始尝试示例,同时寻求对问题的见解。 我想出了一些记号-如果且仅当所有从A瓶喝水的老鼠都从B瓶喝水时, A瓶是溶液中B瓶的子集。

如果一个瓶子有几个子瓶子,那么当超集瓶子被中毒时,就不可能知道哪个子瓶子被中毒了,因为它们不会影响中毒大鼠的分布。 将过多的大鼠分配到一个瓶子中被证明是非最佳的,因为它允许过多的子集瓶子。 对于分配了很少大鼠的瓶子,也有类似的效果。

一个有趣的发现是,提交表格不需要解释解码过程,只需说明哪些大鼠可以喝哪些瓶子。 这意味着有一个判断程序可以确定溶液的生存力和分数,这完全取决于哪只大鼠会喝哪瓶。 我考虑过该算法如何工作。 也许学习法官的工作方式会教会我如何击败它。

法官的工作方式显而易见。 考虑每对可能的中毒瓶,并计算中毒/未受影响大鼠分布的N²种可能结果。 对于每个唯一的大鼠分布,请确保最多有(2 + F )个唯一的瓶子可以关联到每种可能的结果。

例如,假设老鼠的结果为11000111,并且F = 1。 如果瓶子对A&B和A&C都可能造成11000111,则瓶子A,B和C链接在一起。

可以使用字典来执行该法官。 我使用了Java的HashMaps。 有人告诉我,有一个聪明的解决方案,它使用排序列表且内存开销较低。

考虑到排行榜,似乎没有“正确”的解决方案。 注意到我先前的观察结果,我想出了一种方法,它生成N个长度为R的随机二进制字符串,以确保法官在每个附加的二进制字符串之后保持不变,从而排除了任何违规情况。 另外,每个随机字符串将填充特定数量的M。 我通过设置M = 8并增加M来获得成功,因为我的算法无法为太多的迭代找到其他合法的字符串。 我选择F = 1,因为F = 2会使我的分数减半。 我大部分时间都花在摆弄M的值上

此解决方案中使用的一种有趣的算法是如何在O(M)时间中生成具有M个置位的R长度随机二进制字符串。 考虑将索引的M长度数组从0-R改组,并在零初始化的二进制字符串中切换这些索引。 这可以通过O(M)内存来完成。 我使用了Fisher-Yates Shuffle的变体,使用字典来表示选定的索引。

经过一些额外的摆弄后,我的程序能够针对参数N = 3000, R = 30, F = 1生成整洁的100分解决方案。我对此解决方案感到满意,并且设法获得了第一名。

请参阅https://riddle.kik.com/了解挑战主页。