Q458. Poor Pigs

There are 1000 buckets, one and only one of them is poisonous, while the rest are filled with water. They all look identical. If a pig drinks the poison it will die within 15 minutes. What is the minimum amount of pigs you need to figure out which bucket is poisonous within one hour?

Answer this question, and write an algorithm for the general case.

 

General case:

If there are n buckets and a pig drinking poison will die within m minutes, how many pigs (x) you need to figure out the poisonous bucket within p minutes? There is exactly one bucket with poison.

 

Note:

A pig can be allowed to drink simultaneously on as many buckets as one would like, and the feeding takes no time.
After a pig has instantly finished drinking buckets, there has to be a cool down time of m minutes. During this time, only observation is allowed and no feedings at all.
Any given bucket can be sampled an infinite number of times (by an unlimited number of pigs).

I need to point out that this question get 899 downvotes with 449 upvotes which is hanging red flag. But I still want to take some notes on this question since the idea behind the solution looks quite interesting to me.

At the very beginning, I thought this question is very similar to the “dropping egg” question and might be able to solve with DP. But then, I was thinking about an easy case when only 15 minutes are available. In that case, I thought that I would need as many pigs as the buckets, i.e. all buckets have a pig drinking the water. Well, this turns out to be wrong. Anyway, following this naive routine, I came up with a solution where I repeat this routine at each round. At each round, I let one pig drink water from K buckets so that at the end of each round, I only need to work with the K buckets which poisons the pig. With this idea, and some math to minimize the number of pigs needed at each round given the total number of round, I arrived at a solution ~ buckets ** (1 / nround). This solution turns out to be wrong and I was confused about why I only need two pigs to test 4 buckets with one round of test.

OK, my initial idea is just so wrong. It is not about how to reduce the size of the problem at each round of test. All it is about is how to encode the information using as fewer pigs as possible. Let’s think about how to encode first and then examine if it is doable.

How to encode? If we do K round of tests, for each pig, it has (K+1) possible results: die at 1st round, …, die at kth round, …, not die. Then, for M pigs, they could encode (K+1)^M possibilities in total.

Is such encoding achievable? Let’s consider the pth pig. We have a list of buckets that need pth pig to have outcome k. In this case, the kth test for pth pig should contain water from and only from these buckets. This rule applies for any k. Essentially, we can see that for each pig, its outcome will partition the buckets into K+1 parts and each parts form one test with the last part being held out always (so that pig could also be alive to the end). Following this rule, we could assign the tests for each pig separately. So, the encoding is achievable.

The solution is minimum M such that (K + 1)^M > buckets where K = minutesToTest // minutesToDie.

The Python submission.

class Solution:
    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:
        nround = minutesToTest // minutesToDie + 1
        res = math.log(buckets) / math.log(nround)
        if res > int(res):
            res = int(res) + 1
        else:
            res = int(res)
        return res