Two Egg problem confusion_问答_开发者_运维开发者技术经验分享

Two Egg problem:

You are given 2 eggs.
You have access to a 100开发者_如何学Python-storey building.
Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.
You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.
Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process

I am sure the two egg problem ( mentioned above ) has been discussed sufficiently. However could someone help me understand why the following solution is not optimal.

Let's say I use a segment and scan algorithm with the segment size s. So,

d ( 100 / s   + (s-1) ) = 0    [ this should give the minima,  I need '(s-1)' scans per segment and there are '100/s' segments]
-
ds

=> -100 / s^2 + 1 = 0
=> s^2 = 100
=> s = 10

So according to this I need at most 19 drops. But the optimal solution can do this with 14 drops.

So where lies the problem?

You seem to be assuming equal-sized segments. For an optimal solution, if the first segment is of size N, then the second has to be of size N-1, and so on (because when you start testing the second segment, you've already dropped the egg once for the first segment).

So you need to solve n+(n-1)+(n-2)+...+1<=100, from where (n)(n+1)/2<=100 (this function transform is done with arithmetic series aka sum of an arithmetic sequence), now if you solve for n (wolframalpha: Reduce[Floor[n + n^2] >= 200, n] ) you get 14. Now you know that the first floor where you need to make the drop is 14th floor, next will be (14+14-1)th floor and whole sequence:

14; 27; 39; 50; 60; 69; 77; 84; 90; 95; 99; 100

If you break the first egg, you go back to the last one and linearly check all options until you break the second egg, when you do, you got your answer. There is no magic.

http://mathworld.wolfram.com/ArithmeticSeries.html

Correct and optimal solution is 13, 25, 36, 46, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100 in which average number of trials of finding floor on which egg breaks is minimum, assuming floor on which egg breaks is selected randomly.

Based on this information we can write a recursive function to minimize average trials, that gives a solution of

13, 25, 36, 46, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100

It has following max trials for each floor-step

13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14

This is obviously much better than naive solution arrived by assuming gaps starting at 14 and reducing. In this case 55% of time you just need 13 trials. It is very near to optimal solution derived from n (n+1) / 2 >= 100 which gives n = 13.651 and our optimal solution is (13*5+14*9)/14 i.e. 13.643

Here is a quick implementation:

import sys

def get_max_trials(floors):
    pf = 0
    trials = []
    for i, f in enumerate(floors):
        trials.append(i+f-pf)
        pf = f
    return trials

def get_trials_per_floor(floors):
    # return list of trials if egg is assumed at each floor
    pf = 0
    trials = []
    for i, f in enumerate(floors):
        for mid_f in range(pf+1,f+1):
            trial = (i+1) + f - mid_f + 1
            if mid_f == pf+1:
                trial -= 1
            trials.append(trial)
        pf = f
    return trials

def get_average(floors):
    trials = get_trials_per_floor(floors)
    score = sum(trials)
    return score*1.0/floors[-1], max(trials)

floors_map = {}
def get_floors(N, level=0):
    if N == 1:
        return [1]
    if N in floors_map:
        return floors_map[N]
    best_floors = None
    best_score = None
    for i in range(1,N):
        base_floors = [f+i for f in get_floors(N-i, level+1)]
        for floors in [base_floors, [i] + base_floors]:
            score = get_average(floors)
            if best_score is None or score < best_score:
                best_score = score
                best_floors = floors

    if N not in floors_map:
        floors_map[N] = best_floors
    return best_floors

floors = get_floors(100)
print "Solution:",floors
print "max trials",get_max_trials(floors)
print "avg.",get_average(floors)

naive_floors = [14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100]
print "naive_solution",naive_floors 
print "max trials",get_max_trials(naive_floors)
print "avg.",get_average(naive_floors)

Output:

Solution: [13, 25, 36, 46, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100]
max trials [13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14]
avg. (10.31, 14)
naive_solution [14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100]
max trials [14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 12]
avg. (10.35, 14)

I also had the same thought in mind . I was also trying to find the exact method you said . I cleared this solution as explained by one of the members here . But here is a bit more explanation if you might .

N is defined as the minimum no: of searches required .

I am trying to find a no: n such that it is the min no: of searches I have to make .

So I start at xth floor I have 2 scenarios ,

1) It breaks , I have to do x-1 more checking's (because I have only 1 more egg) . All's fair there . Total is 1+ x-1 = x searches .

Now we have defined this value as n . Hence x = n ! [PS : This might be trivial but this has some subtleties IMO]

2) It doesnt break - and I have used up one of my n possibilities already ! Now the searches allowed further is n - 1 . Only then the total no: of searches will be N and that is the definition of N . The problem now has become a sub problem of 100 - n floors with 2 eggs . If am chosing some yth floor now - its worst case should be n - 1 . (n - 1)th floor satisfies this .

Hence you get the pattern go to nth , n + (n -1 )th floor , n + (n - 1) + (n - 2)th floor .... Solve this for 100th floor and you get N . The floor you start with and the no: of searches is a coincidence I think .

To get the maxima n = 14 , you can think of having n bulbs with 2 bulbs glowing at once . It will require atleast 14 bulbs to cover all the possible combinations of where egg can break .

As a challenge try to do it for 3 eggs .

In your logic basically , there is an asymmetry in how the search progress . For the first set of 10 elements , the algorithm finds out quickly . I would suggest to try and check

http://ite.pubs.informs.org/Vol4No1/Sniedovich/ for some explnation and also try to visualize how this problem is seen in real cases of Networks .

A very nice explanation of the solution I found in the below link. The Two Egg Problem

It explains how you get to n+(n-1)+(n-2)+...+1<=100
The 1 Egg Problem - Linear Complexity O(100)
and Multiple(Infinite) Eggs Problem - Logarithmic complexity O(log2(100)).

Here's a solution in Python. If you drop the egg at a certain floor f, it either breaks or it doesn't, and in each case you have a certain number of floors you still need to check (which is a subproblem). It uses a recursion and also a lookup dictionary to make it much faster to compute.

neededDict = {}

# number of drops you need to make
def needed(eggs, floors):

    if (eggs, floors) in neededDict:
        return neededDict[(eggs, floors)]

    if eggs == 1:
        return floors

    if eggs > 1:

        minimum = floors
        for f in range(floors):
            #print f
            resultIfEggBreaks = needed(eggs - 1, f)
            resultIfEggSurvives = needed(eggs, floors - (f + 1))
            result = max(resultIfEggBreaks, resultIfEggSurvives)
            if result < minimum:
                minimum = result

        # 1 drop at best level f plus however many you need to handle all floors that remain unknown
        neededDict[(eggs, floors)] = 1 + minimum
        return 1 + minimum


print needed(2, 100)

The question should not be how many drops you need to make ? but rather than that it should be find the minimal number of drops in order to know where the egg breaks, I saw this issue on careercup, below is the algorithms I thought of:

There are two ways to solve this problem :

binary search for the first egg (risked to know where we need to look up) O(binary log)
Fibonaccy sequence search 1,2,3,5,8,13,21,34,55,89 for the first egg O(log) http://en.wikipedia.org/wiki/Fibonacci_search_technique

Once first egg is broken we know in which interval we need to look:

binary example:

we try 100/2 (50) if it broke we search from 1 to 50 incrementing by 1 if not we throw it from 50+100/2 (75) if it broke we search from 50 to 75 if not we throw it from 75+100/2 (87) if it broke we search from 75 to 87 incemrenting by one floor at a time and so on and so forth.
fibonacy example: same thing : we try 1,2,3,5,8.13,... if first egg broke we get back to the last interval's minimum and increment by 1.

hey what about this approach.

Try this sequence:

1,2,4,8,16,32,64,100

And once you find the egg is broken you well get a space to work on. lets suppose @ 64 egg breaks. then the answer lies between 32 & 64.

We can use normal binary search between those 2 number. we will check @ 48 (32+64)/2 and then we will get the upper half or lower half as shortlisted space. and repeat

In this case the worst case is having the floor at 99. which will take 14 tries.

The explanation of the two eggs problem can make some people confused in the first time, so we can understand the solution as follows: Given x is the floor we start dropping the eggs: - If it breaks, the total of trials in the worst case is x + (x - 1) - If it doesn't break, how should we step up to the next floor? We can jump to floor (x + x)th, (x + x + 1)th... But it will increase the number of trials, we can try at x = 10: . If it does break, we must try 10 times total in the worst case. . If it does not break, and we step up to 10th + 10th = 20th and try, and if it breaks, we must try 1 (at floor 10th) + 1 (at floor 20th) + 9 = 11 times. Similarly, if we step up to x + 1, or x + 2 floor it will increase the number of trials. Actually, we want the number of trials being equal in both cases, for that reason we will step up to x - 1 floor instead of x, x + 1.,etc. Finally, we will have an expression in general: x + (x - 1) + (x - 2) + ... + 1. And that's it.

I would say the optimal solution for 100 floors with two eggs is 13 tries not 14.
13, 25, 36, 46, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100 is the optimal answer, but if I reach to 99 I do not really need to try out 100. It is obvious the correct answer without try to drop egg from 100th floor :D