程式隨筆
0%

【LeetCode】Poor Pigs

Posted on Edited on In Disqus:

#題目

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

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

Follow-up:

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 “poison” bucket within p minutes? There is exact one bucket with poison.

1
2
3
4
5
public class Solution {
    public int PoorPigs(int buckets, int minutesToDie, int minutesToTest) {
        
    }
}

#解題

喝下毒藥15分鐘毒發身亡，假設每15分鐘沒事就喝下一桶這樣循環，一隻豬一小時可喝下四桶水，假設中間喝到任一桶毒藥，則提前找到目標，如果沒有，則第五桶就會是毒藥。(全部五桶的狀況)

換句話說，假設2隻豬可以測試25桶水(二維)，依據豬隻毒發的時間可以知道哪桶水有毒

1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

豬隻A每次喝一行(1,2,3,4,5)，豬隻B每次喝一列(1,6,11,16,21)，一小時剛好可以測試25桶水，毒發時即可推測哪一桶水有毒了

所以公式為**(測試時間/毒發時間 + 1 ) ^ n >= 水桶數** ，求n的最小值

案例一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
[TestMethod]
public void PoorPigsTest_5桶水_1小時_毒發時間15分鐘_最少需要1隻豬來測試()
{
    //arrange
    var sut = new Solution();
    var bukets = 5;
    var minutesToDie = 15;
    var minutesToTest = 60;

    var expected = 1;
    //act
    var actual = sut.PoorPigs(bukets, minutesToDie, minutesToTest);

    //assert
    actual.Should().Be(expected);

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int PoorPigs(int buckets, int minutesToDie, int minutesToTest)
{
    var OnePigCanTestBukets = (minutesToTest / minutesToDie) + 1;

    var Pigs = 0;
    double TotalCanTestBukets = 0;
    while (TotalCanTestBukets < buckets)
    {
        Pigs++;
        TotalCanTestBukets = Math.Pow(OnePigCanTestBukets, Pigs);
    }

    return Pigs;
}

案例二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
[TestMethod]
public void PoorPigsTest_6桶水_1小時_毒發時間15分鐘_最少需要2隻豬來測試()
{
    //arrange
    var sut = new Solution();
    var bukets = 6;
    var minutesToDie = 15;
    var minutesToTest = 60;

    var expected = 2;
    //act
    var actual = sut.PoorPigs(bukets, minutesToDie, minutesToTest);

    //assert
    actual.Should().Be(expected);

}

直接通過單元測試

#解析

LeetCode測試發生錯誤

/images/20180619/1.jpg

補上案例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
[TestMethod]
public void PoorPigsTest_1桶水_1分鐘測試時間_毒發時間1分鐘_最少需要0隻豬來測試()
{
    //arrange
    var sut = new Solution();
    var bukets = 1;
    var minutesToDie = 1;
    var minutesToTest = 1;

    var expected = 0;
    //act
    var actual = sut.PoorPigs(bukets, minutesToDie, minutesToTest);

    //assert
    actual.Should().Be(expected);

}

一桶水根本不需要測試，所以修改一下Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int PoorPigs(int buckets, int minutesToDie, int minutesToTest)
{
    var Pigs = 0;
    if (buckets <= 1)
    {
        return Pigs;
    }

    var OnePigCanTestBukets = (minutesToTest / minutesToDie) + 1;
    double TotalCanTestBukets = 0;
    while (TotalCanTestBukets < buckets)
    {
        Pigs++;
        TotalCanTestBukets = Math.Pow(OnePigCanTestBukets, Pigs);
    }

    return Pigs;
}

過關

心得

一開始沒想清楚，想說算出一隻豬能測試幾桶後直接除即可，但這樣會發生一個狀況是剛好全部豬都活下來，那就會有一堆水桶還沒測試，參考了答案後想了一下才想通這是幾維的問題，只要讓這些豬喝下的水有交錯的可能，那有辦法推斷哪桶有毒。

另外Math.Pow的用法也是查了後才知道如何使用，雖然理解上不難，但也是很有收穫的一題

MSDN - Math.Pow