Some thoughts on the "egg drop" problem: https://www.interviewcake.com/question/python/two-egg-problem

egg-drop.md

Problem description:

https://www.interviewcake.com/question/python/two-egg-problem

A building has 100 floors. One of the floors is the highest floor an egg can be dropped from without breaking.

If an egg is dropped from above that floor, it will break. If it is dropped from that floor or below, it will be completely undamaged and you can drop the egg again.

Given two eggs, find the highest floor an egg can be dropped from without breaking, with as few drops as possible.

Discussion

Binary search solution: 50 drops worst-case

My first inclination would be to use binary search. However, this is hampered by the fact that we can only sacrifice one egg. So the worst-case here would be if the solution were 49: we would start with a drop from 50 (which would break), at which point we would be forced to start from the first floor and increment one floor at a time until we reached floor 49, so 50 drops total.

Floor-skipping (hop-size == 2): 50 drops worst-case

My next thought is that we can use a bit of mathematical induction to skip some floors. For example, we could start on floor 2, and if that breaks, we know the answer is floor 1 without having to drop a second egg.

If we chain these together, we can hop two floors at a time. Here, the worst-case would be floor 100, which would require 50 drops to deduce.

Binary search with floor-skipping (hop-size == 2): 25 drops worst-case

I think we can combine those approaches and the worst-case (floor 49) is now 25 drops (1 drop of the first egg at @50, then 24 drops with the second egg to deduce that 49 is the answer).

Binary search with floor-skipping (hop-size == 4): 27 drops worst-case

We could increase the number of floors which we skip with each hop to 4, and then bisect that with the remaining egg. A solution of floor 99 is now the worst case, which would require 25 drops with the first egg and two more with the second egg (27 total), so that's no better.

Dynamically increasing hop-size: 31 drops worst-case

What if we used an increasing hop size with the first egg? Here there is going to be a trade-off between how aggressively we grow the hop-size for the first egg vs. how many hops the second egg will have to make.

Hmm, I think we will have to write a few programs to find that tradeoff.

OK, so the best result I saw there was 31 drops, which isn't as good as the 25 drop solution described above. Graph of results

Here's the first few lines of the results (as CSV), sorted with best solutions on top:

1.20310722171,31
1.20431032893,31
1.20551463926,31
1.2067201539,31
1.22617316074,31
1.2273993339,31
1.22862673324,31
1.13534496912,32
1.13648031409,32

So, solutions with a hop-size multiplier near 1.2 yeilded the best results (31 drops worst-case)

egg-drop.py

#!/usr/bin/env python

def eggdrop(answer, multiplier=2.0):
    print "testing %s with multiplier %s" % (answer, multiplier)
    top_floor = 100
    good_guesses = [1]
    bad_guesses = []
    last_hop_size = 1.0
    num_guesses = 0
    while len(bad_guesses) == 0:
        last_hop_size *= multiplier
        hop_size = int(last_hop_size)   
        guess = good_guesses[-1] + hop_size
        if guess >= top_floor:
            guess = top_floor
        num_guesses += 1
        egg_broke = guess > answer
        if egg_broke:
            bad_guesses.append(guess)
            print "egg 1 guess: %s: broke!" % guess
            break
        else:
            good_guesses.append(guess)
            print "egg 1 guess: %s: ok!" % guess
            if guess == top_floor:
                assert answer == guess
                print "num guesses: %s" % num_guesses
                return num_guesses
            continue
    while len(bad_guesses) == 1:
        guess = good_guesses[-1] + 1
        num_guesses += 1
        egg_broke = guess > answer
        if egg_broke:
            bad_guesses.append(guess)
            assert answer == (guess - 1)
            print "egg 2 guess: %s: broke!" % guess
            print "num guesses: %s" % num_guesses
            return num_guesses
        else:
            good_guesses.append(guess)
            print "egg 2 guess: %s: ok!" % guess
            continue
    assert False

worsts = []

multiplier = 1.0
while multiplier < 101.0:
    results = []
    for i in range(1, 101):
        results.append(eggdrop(i, multiplier))
        print
    worst = sorted(results)[-1]
    worsts.append((worst, multiplier))
    if multiplier >= 2.0:
        multiplier = int(multiplier + 1)
    elif multiplier >= 1.5:
        multiplier *= 1.01
    else:
        multiplier *= 1.001

worsts.sort()
for worst, multiplier in worsts:
    print "%s,%s" % (multiplier,worst)

results.txt

1.20310722171,31
1.20431032893,31
1.20551463926,31
1.2067201539,31
1.22617316074,31
1.2273993339,31
1.22862673324,31
1.13534496912,32
1.13648031409,32
1.14789639546,32
1.15826888385,32
1.15942715274,32
1.16058657989,32
1.16174716647,32
1.17107373786,32
1.1722448116,32
1.17341705641,32
1.17459047347,32
1.17576506394,32
1.17694082901,32
1.18757576535,32
1.18876334111,32
1.18995210446,32
1.19114205656,32
1.19233319862,32
1.19352553181,32
1.20792687405,32
1.20913480092,32
1.21034393572,32
1.21155427966,32
1.22494821253,32
1.22985535997,32
1.23108521533,32
1.23231630054,32
1.23354861684,32
1.25343411359,32
1.2546875477,32
1.25594223525,32
1.25719817748,32
1.25845537566,32
1.282582448,32
1.28386503045,32
1.28514889548,32
1.28643404438,32
1.28772047842,32
1.32030278464,32
1.32162308742,32
1.32294471051,32
1.32426765522,32
1.11621671775,33
1.11733293447,33
1.1184502674,33
1.11956871767,33
1.12293078365,33
1.12405371443,33
1.12517776815,33
1.12630294592,33
1.12742924886,33
1.12855667811,33
1.12968523479,33
1.1376167944,33
1.13875441119,33
1.13989316561,33
1.14103305877,33
1.14560404177,33
1.14674964581,33
1.14904429185,33
1.15019333614,33
1.15134352948,33
1.15249487301,33
1.16290891364,33
1.16407182255,33
1.16523589437,33
1.16640113027,33
1.17811776984,33
1.17929588761,33
1.18047518349,33
1.19471905735,33
1.1959137764,33
1.19710969018,33
1.20190531639,33
1.21276583394,33
1.21397859977,33
1.21519257837,33
1.21640777095,33
1.22372448804,33
1.23478216546,33
1.23601694763,33
1.23725296457,33
1.23849021754,33
1.25218193165,33
1.25971383104,33
1.26097354487,33
1.26223451841,33
1.26349675293,33
1.28002112573,33
1.28130114686,33
1.2890081989,33
1.2902972071,33
1.2915875043,33
1.29287909181,33
1.31898380084,33
1.32559192288,33
1.3269175148,33
1.32824443232,33
1.32957267675,33
1.37004365586,33
1.37141369951,33
1.37278511321,33
1.11065233842,34
1.11176299076,34
1.11287475375,34
1.11398762851,34
1.12068828639,34
1.12180897467,34
1.13081492002,34
1.13194573494,34
1.13307768068,34
1.13421075836,34
1.14217409183,34
1.14331626592,34
1.14445958219,34
1.15364736788,34
1.15480101525,34
1.15595581627,34
1.15711177208,34
1.1675675314,34
1.16873509893,34
1.16990383403,34
1.18165565868,34
1.18283731434,34
1.18402015165,34
1.1852041718,34
1.18638937597,34
1.19830679987,34
1.19950510667,34
1.20070461178,34
1.21762417872,34
1.2188418029,34
1.2200606447,34
1.22128070535,34
1.22250198605,34
1.23972870776,34
1.24096843646,34
1.2422094049,34
1.24968131933,34
1.25093100065,34
1.26476024968,34
1.26602500993,34
1.26729103494,34
1.27874238335,34
1.2941719709,34
1.29546614287,34
1.29676160901,34
1.29805837062,34
1.33090224942,34
1.33223315167,34
1.33356538483,34
1.33489895021,34
1.36867498088,34
1.37415789833,34
1.37553205622,34
1.37690758828,34
1.37828449587,34
1.37966278036,34
1.42735362599,34
1.42878097961,34
1.43020976059,34
1.43163997035,34
1.43307161032,34
1.43450468193,34
1.43593918662,34
1.09084925836,35
1.09194010761,35
1.09631442405,35
1.09741073848,35
1.09850814922,35
1.09960665737,35
1.10290877726,35
1.10401168603,35
1.10511569772,35
1.10622081342,35
1.10732703423,35
1.10843436127,35
1.10954279563,35
1.11510161613,35
1.24345161431,35
1.24469506592,35
1.24593976099,35
1.24718570075,35
1.24843288645,35
1.26855832598,35
1.2698268843,35
1.27109671119,35
1.2723678079,35
1.27746491843,35
1.29935642899,35
1.30065578542,35
1.30195644121,35
1.31634978492,35
1.3176661347,35
1.33623384916,35
1.33757008301,35
1.33890765309,35
1.36457715432,35
1.36594173147,35
1.3673076732,35
1.38104244314,35
1.38242348559,35
1.38380590907,35
1.42592769829,35
1.4373751258,35
1.43881250093,35
1.44025131343,35
1.44169156474,35
1.51550310461,35
1.0810805238,36
1.0854113367,36
1.08649674804,36
1.08758324478,36
1.08867082803,36
1.09303204772,36
1.09412507977,36
1.09521920485,36
1.10070626402,36
1.10180697029,36
1.27364017571,36
1.27491381588,36
1.2761887297,36
1.30325839765,36
1.30456165605,36
1.3058662177,36
1.30717208392,36
1.34024656075,36
1.34158680731,36
1.34292839411,36
1.34427132251,36
1.36321394038,36
1.38518971498,36
1.3865749047,36
1.3879614796,36
1.38934944108,36
1.42450319509,36
1.44313325631,36
1.44457638956,36
1.44602096595,36
1.44746698692,36
1.62482445468,36
1.07676699092,37
1.07784375791,37
1.08216160432,37
1.08324376592,37
1.08432700969,37
1.08975949886,37
1.30847925601,37
1.30978773526,37
1.311097523,37
1.31372102914,37
1.31503475017,37
1.34561559383,37
1.34696120942,37
1.34830817063,37
1.36185208829,37
1.39073879052,37
1.39212952931,37
1.39352165884,37
1.3949151805,37
1.41740199691,37
1.41881939891,37
1.4202382183,37
1.42165845652,37
1.42308011498,37
1.44891445391,37
1.45036336836,37
1.45181373173,37
1.45326554546,37
1.49899912425,37
1.50049812338,37
1.07247066913,38
1.0735431398,38
1.07461668294,38
1.07569129962,38
1.07892160167,38
1.08000052327,38
1.31240862052,38
1.3496564788,38
1.35100613528,38
1.35235714142,38
1.35370949856,38
1.35641827127,38
1.35777468954,38
1.35913246423,38
1.36049159669,38
1.39631009568,38
1.39770640578,38
1.39910411218,38
1.41457143946,38
1.4159860109,38
1.45471881101,38
1.45617352982,38
1.45762970335,38
1.45908733305,38
1.49600561701,38
1.49750162263,38
1.53065813566,38
1.06605830708,39
1.06712436538,39
1.06925968124,39
1.07032894092,39
1.07139926986,39
1.35506320806,39
1.4005032163,39
1.40190371951,39
1.40330562323,39
1.40470892885,39
1.46054642038,39
1.4620069668,39
1.46346897377,39
1.64107269923,39
1.79481704255,39
1.06286651786,40
1.06392938438,40
1.06499331376,40
1.06819148975,40
1.40611363778,40
1.40751975142,40
1.40892727117,40
1.46493244274,40
1.46639737519,40
1.46786377256,40
1.46933163633,40
1.49152656126,40
1.49301808782,40
1.49451110591,40
1.54596471701,40
1.60873708384,40
1.77704657678,40
1.05968428489,41
1.06074396918,41
1.06180471315,41
1.41033619844,41
1.41174653464,41
1.41315828118,41
1.47080096797,41
1.47227176894,41
1.47374404071,41
1.48854797676,41
1.49003652473,41
1.65748342622,41
1.81276521297,41
1.05440172172,42
1.05545612344,42
1.05651157956,42
1.05756809114,42
1.05862565923,42
1.47521778475,42
1.47669300253,42
1.47816969554,42
1.47964786523,42
1.48706091584,42
1.5928089939,42
1.05124483243,43
1.05229607727,43
1.05334837334,43
1.4811275131,43
1.48260864061,43
1.48409124925,43
1.4855753405,43
1.56142436418,43
1.67405826048,43
1.75945205622,43
1.8308928651,43
2.00242056243,43
1.0491454923,44
1.0501946378,44
1.04809739491,45
1.74203173883,45
1.84920179376,45
1.04391546538,46
1.04495938084,46
1.04600434022,46
1.04705034457,46
1.57703860782,46
1.69079884309,46
1.04183076202,47
1.04287259279,47
1.04078997205,48
1.86769381169,48
1.03871151032,49
1.03975022183,49
1.70770683152,49
1.72478389983,49
1.98259461626,49
1.03767383648,50
1.03456703066,51
1.03560159769,51
1.03663719928,51
1.88637074981,51
1.9629649666,51
7,51
50,51
1.03353349716,52
49,52
51,52
1.03250099616,53
1.90523445731,53
1.9435296699,53
48,53
52,53
1.03146952664,54
47,54
53,54
1.02940967787,55
1.03043908755,55
1.92428680188,55
46,55
54,55
1.02838129657,56
45,56
55,56
1.02735394263,57
44,57
56,57
43,58
57,58
1.02632761502,59
42,59
58,59
1.02427803467,60
1.0253023127,60
6,60
41,60
59,60
1.02325477989,61
40,61
60,61
1.02223254734,62
39,62
61,62
38,63
62,63
1.02121133601,64
3,64
37,64
63,64
1.02019114486,65
36,65
64,65
8,66
35,66
65,66
1.01917197289,67
4,67
34,67
66,67
33,68
67,68
1.01815381907,69
32,69
68,69
1.01713668239,70
31,70
69,70
30,71
70,71
5,72
29,72
71,72
1.01612056182,73
28,73
72,73
1.01510545637,74
27,74
73,74
26,75
74,75
1.014091365,76
25,76
75,76
24,77
76,77
1.01307828672,78
23,78
77,78
22,79
78,79
1.0120662205,80
21,80
79,80
20,81
80,81
19,82
81,82
1.01105516533,83
9,83
18,83
82,83
17,84
83,84
16,85
84,85
1.01004512021,86
15,86
85,86
14,87
86,87
13,88
87,88
12,89
88,89
1.00903608413,90
11,90
89,90
10,91
90,91
91,92
92,93
1.00802805607,94
93,94
94,95
95,96
96,97
97,98
98,99
1.0,100
1.001,100
1.002001,100
1.003003001,100
1.004006004,100
1.00501001001,100
1.00601502002,100
1.00702103504,100
99,100
100,100