eggdrop.py

import timeit


def memoize(function):
    """Caching results of a function"""
    # This is bad of course, it just to be able to compare the solutions
    memoize.cache = {}

    def memoizer(*args, **kwargs):
        """Memoize helper"""
        memoizer.count += 1
        key = (args, frozenset(kwargs))
        res = memoize.cache.get(key)
        if res is None:
            memoizer.miss += 1
            res = function(*args, **kwargs)
            memoize.cache[key] = res
        return res
    memoizer.count = 0
    memoizer.miss = 0
    return memoizer

# Both solutions (drop1/2) exceed recursion depth quite easily


@memoize
def drop1(eggs, floors):
    """Solving the eggdrop problem"""
    # If we have one egg left, we need "floors" tries
    if eggs == 1:
        return floors
    # If we there are no floors or only one floor, we need "floors" tries
    elif floors < 2:
        return floors
    min_ = floors + 1
    for x in range(floors - 1):
        # If we fail we have to check floors lower than x
        fail = drop1(eggs - 1, x)
        # If we succeed we have to check floors heighter than x
        success = drop1(eggs, floors - x - 1)
        res = max(fail, success)
        if res < min_:
            min_ = res
    return min_ + 1


@memoize
def drop2(eggs, floors):
    """Solving the eggdrop problem"""
    # If we have one egg left, we need "floors" tries
    if eggs == 1:
        return floors
    # If we there are no floors or only one floor, we need "floors" tries
    elif floors < 2:
        return floors
    return 1 + min([
        max(
            # If we fail we have to check floors lower than x
            drop2(eggs - 1, x),
            # If we succeed we have to check floors heighter than x
            drop2(eggs, floors - x - 1)
        ) for x in range(floors - 1)
    ])


@memoize
def drop3(eggs, floors):
    """Solving the eggdrop problem"""
    # If we have one egg left, we need "floors" tries
    if eggs == 1:
        return floors
    # If we there are no floors or only one floor, we need "floors" tries
    elif floors < 2:
        return floors
    return 1 + min([
        max(
            # If we fail we have to check floors lower than x
            drop3(eggs - 1, x),
            # If we succeed we have to check floors heighter than x
            drop3(eggs, floors - x - 1)
        # Try to hit the base case first, to reduce stack-depth
        ) for x in range(floors - 2, -1, -1)
    ])


def test1():
    memoize.cache = {}
    drop1(5, 200)


def test2():
    memoize.cache = {}
    drop2(5, 200)


def test3():
    memoize.cache = {}
    drop3(5, 200)


print(timeit.timeit("test1()", setup="from __main__ import test1", number=3))
print(timeit.timeit("test2()", setup="from __main__ import test2", number=3))
print(timeit.timeit("test3()", setup="from __main__ import test3", number=3))