3
\$\begingroup\$

Problem description:

You have two eggs, and need to find the maximum floor of a 100-floor building from which you can drop the eggs without them breaking. Do this with as few attempts as possible.

NB! You are passed the level of where it breaks, n, and an egg is considered broken when your compares and finds test floor is larger than n. You can try to drop the egg as many times as you want (compare test floor and n), but you can only be above twice. Returning n-1 is cheating, consider n to be unknown!

I created a function which takes an argument of the floor, and then calculates the answer (since creating the physics engine to actually simulate the gravity and all that was out of scope).

I'd like to be reviewed on style, accuracy, efficiency, bugs/edge cases, and take into account I did this in a couple minutes while running through interview sample questions that I found on Glassdoor.

def egg_drop(n):
    ''' Find the highest floor in a building that an egg can drop from without breaking '''
    t = [1,11]
    while t[0] < 100:
        if t[1] >= n: 
            print 'break_an_egg on floor %d' % t[1] 
            for i in range(t[0],t[1]):
                if i >= n:
                    print  'break_an_egg on floor %d' % i 
                    return i - 1
        else:
            t[0] += 10
            t[1] += 10
    return 100
\$\endgroup\$
3
  • \$\begingroup\$ The algorithm is not optimal. Having the constant increment (10 in your case) gives 20 tries in the worst case, and 10 in average. There is a way guaranteeing 15 and 4.8 tries respectively. \$\endgroup\$
    – vnp
    Nov 2, 2015 at 19:03
  • \$\begingroup\$ Right, I know it's better to start with larger intervals and gradually decrease, but I learned that after I wrote this, and i want to be graded on this as if it were a really critical review of a first draft function. Not a refined one. \$\endgroup\$ Nov 2, 2015 at 20:07
  • \$\begingroup\$ Thanks to whomever took the time to decipher and edit this. I know I was not clear enough, but was bummed when it was put on hold. Whomever added the notes is exactly correct about the intentions. The original challenge didn't mention how to provide a method for specifying what was actually the correct answer, so I added a parameter n to check if it works or not. \$\endgroup\$ Nov 3, 2015 at 17:10

1 Answer 1

7
\$\begingroup\$

Here are some comments on your question:

  • Bad problem description – I can't help but to make a method which find the input parameter, seems kind of silly. It could simply do return n-1 and you're done. It would have been better if the problem description gave a predefined method which you could call at most two times before it gave some error. But I digress...
  • Choose good names for your variables – Two store the lower and higher test floors in a list t is bad. What is t[0] or t[1]. Say low, highis way better, and even they can be improved upon
  • Assign multiple values at once – If you want to use one line to assign multiple values you can do: low, high = 1, 11
  • Don't use magic numbers – If you have magic numbers, like the number of floors, do either declare them as constants at the top or as default parameters to the method in question
  • Give proper text output – It took me quite some time to understand what your output actually was meant to describe. It would have been much clearer if you had said "First egg broke on floor x" and "Second egg broke on floor y"
  • Switch to new style print formatting and function – It is recommend to switch to the new string.format() style for print output. I.e. print ('First egg broke on {}'.format(high))

  • Error handling is good – As the problem was limited to a 100 floor building, one could/should also let the code reflect that. One way can be to assert legal floor levels, and another could be to make sure that when returning you don't return an illegal level.

Finally you can reduce the number of attempts by a little if you start out attempting with a little higher delta value/range and let it shrink as you get closer to the top1. It can be shown that the optimal delta offset is the result of \$\frac{\sqrt{1 + 8\cdot {floors}} - 1}{2}\$. With these suggestions, and a simple loop to test for all available floors we get:

import math

MAX_FLOOR = 100

def safest_egg_drop_floor(n):
    """Return the safest floor to drop an egg from."""

    assert 1 <= n <= MAX_FLOOR, 'Building has floors from 1 through {}'.format(MAX_FLOOR)

    # Calculate the optimal delta to start with, to reduce attempt numbers
    delta = int(math.ceil((math.sqrt(1 + 8*MAX_FLOOR) - 1)/ 2))

    low, high = 1, delta

    while low < MAX_FLOOR:
        if high >= n:
            print('  First egg broke on floor {}'.format(high))

            for i in range(low, high+1):
                if i >= n:
                    print('  Second egg broke on floor {}'.format(i))
                    if i == 1:
                        raise ValueError("Eggs will always break")
                    else:
                        return i - 1
        else:
            delta -= 1
            low, high = high, high + delta
            if high > MAX_FLOOR:
               high = MAX_FLOOR

    return MAX_FLOOR


def main():

    for i in range(0, MAX_FLOOR+2):
        print('\nFind egg drop when it breaks at {}'.format(i))
        try:
            max_floor = safest_egg_drop_floor(i)
            print('    Safest drop from floor {}'.format(max_floor))
        except (ValueError, AssertionError) as error:
            print(error)

Which outputs:

Find egg drop when it breaks at 0
Building has floors from 1 through 100

Find egg drop when it breaks at 1
  First egg broke on floor 14
  Second egg broke on floor 1
Eggs will always break

Find egg drop when it breaks at 2
  First egg broke on floor 14
  Second egg broke on floor 2
    Safest drop from floor 1

...

Find egg drop when it breaks at 100
  First egg broke on floor 100
  Second egg broke on floor 100
    Safest drop from floor 99

Find egg drop when it breaks at 101
Building has floors from 1 through 100

1 See http://datagenetics.com/blog/july22012/index.html for a better explanation.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.