Solution to the eggs and floors puzzle. The original asks that if you have a 100 floors and 2 eggs what' the minimum number of drops needed to figure out where the eggs break.

egg_and_floors.py

from math import sqrt, ceil
from functools import wraps
from optparse import OptionParser

CACHE = {}


def cache(f):
    @wraps(f)
    def cached(*args, **kwargs):
        key = "%s - %s - %s - %s" % (
            f.__module__,
            f.__name__,
            ",".join(map(str, args)),
            ",".join(map(lambda x: "%s.%s" % x, kwargs.iteritems()))
        )

        global CACHE
        if key not in CACHE:
            CACHE[key] = f(*args, **kwargs)
        return CACHE[key]

    return cached


@cache
def rec_solve(floors, eggs):
    assert floors > 0
    assert eggs > 0

    if eggs == 1:
        return floors
    elif eggs == 2:
        return int(ceil((-1.0 + sqrt(1 + 8 * floors)) / 2.0))
    else:
        low, high = 0, 1
        s = lambda x: sum(rev(i, eggs - 1) for i in xrange(1, x)) + x
        while s(high) < floors:
            high *= 2

        while high - low > 1:
            mid = (low + high) / 2
            if s(mid) < floors:
                low = mid
            else:
                high = mid

        return high


@cache
def rev(drops, eggs):
    low, high = 0, 1
    while rec_solve(high, eggs) <= drops:
        high *= 2

    while high - low > 1:
        mid = (low + high) / 2
        if rec_solve(mid, eggs) <= drops:
            low = mid
        else:
            high = mid

    return low


def setup():
    parser = OptionParser(usage='usage: %prog [options] ')
    parser.add_option(
        "-f", "--floors", action="store", type="int", dest="floors")
    parser.add_option(
        "-e", "--eggs", action="store", type="int", dest="eggs")
    
    (options, args) = parser.parse_args()
    return options


if __name__ == "__main__":
    o = setup()
    print rec_solve(o.floors, o.eggs)