Memoizing Egg Drop

Question

I am struggling to understand the following lines of code based on the Egg Drop problem. In particular, I am having trouble understanding the memo_cyclic function. Can you explain to me what does the *args do, and how decorator work in this setting? What does f_memo.__name__ = f.__name__ do? Why when I remove the lines above and including @memo_cyclic, the program returns an error?

def memo_cyclic(f_cycle):
    def decorator(f):
        cache = {}
        def f_memo(*args):
            args = tuple(args)
            if args not in cache:
                cache[args] = f_cycle(*args)
                cache[args] = f(*args)
            return cache[args]
        f_memo.__name__ = f.__name__
        return f_memo
    return decorator

fail = float("infinity")

@memo_cyclic(lambda *args: fail)
def f(n, lo, hi, fl=0, dr=0):
    if lo == hi:
        return 0 # only one floor is possible
    if n+dr == 0:
        return fail # out of eggs
    if fl == 0:
        n, dr = n+dr, 0 # pick up any dropped eggs
    return 1 + min(f(n, lo, hi, fl-1, dr) if fl > 0 else fail,  # go down one floor
                   f(n, lo, hi, fl+1, dr) if fl < hi else fail, # go up one floor
                   max(f(n-1, lo,   fl, fl, dr),                # drop egg (broken)
                       f(n-1, fl+1, hi, fl, dr+1))              # drop egg (unbroken)
                       if n > 0 and lo <= fl < hi else fail)

import sys
sys.setrecursionlimit(10000)

print [f(n, 0, n) for n in range(20)]
print [f(1, 0, n) for n in range(20)]
print f(2, 0, 99)

Answer 1

This is all explained in any good tutorial on decorators. For example https://realpython.com/primer-on-python-decorators/.

But here is the basic flow. Consider this construct.

@decorator
def some_function (...):
    ...

is actually short-hand for the following:

def some_function (...):
    ...

some_function = decorator(some_function)

But in your case you have a decorator with arguments. What does that do? Well:

@complex_decorator(stuff)
def some_function (...):
    ...

simply means

def some_function (...):
    ...

some_function = complex_decorator(stuff)(some_function)

So complex_decorator needs to be a function that returns a function. And the function that it returns needs to take a function and return a new function! (Yes, this is supposed to make your head spin the first few times that you encounter it. But it is all logical.)

Now your complex decorator is memo_cyclic, which is too clever by half. Let's see if we can untangle it with comments and numbers. Please try to read the comments in order of the numbers. They generally go outside in, so skip below a function before trying to read inside of it.

# 1) This is a recursive cache that will avoid repeated work and
#    also replace infinite cycles with a failure value that is
#    f_cycle(whatever, the, arguments, were)
def memo_cyclic(f_cycle):
    # 3) decorator will take our original function, and returns the
    #    replacement.  By possibly confusing coincidence, the
    #    function was originally called f before (global namespace)
    #    and is locally called f here in scope.  But it would work
    #    just fine if we locally called it g.
    def decorator(f):
        # 5) cache will have the values that we have produced
        #    before so that we can return them instead of
        #    having to calculate them a second time.  This trick
        #    is called "memoizing"
        cache = {}
        # 6) f_memo will be our replacement for f.  Note that *args
        #    here just means, "Turn whatever list of arguments we got
        #    before into an array."
        def f_memo(*args):
            #  9) A tuple is the same as an array except that it can't
            #     change.  Because it can't change, Python will let us
            #     use it as the key to a dictionary.
            args = tuple(args)
            # 10) And now we check if the tuple is in the cache.  If
            #     we have received this set of arguments before, the
            #     cache will be filled and we skip this.  Else we have
            #     work to do.
            if args not in cache:
                # 11) We set the value to return upon hitting an
                #     infinite loop.  Note that *args here means
                #     "turn a list back into a list of arguments
                #     before calling the function".
                cache[args] = f_cycle(*args)
                # 12) And now we recursively do the original
                #     calculation.  Note that when f calls itself
                #     recursively, it will call what is bound to
                #     the name f.  Which will _actually_ be the
                #     function f_memo.  Which means that if it
                #     WOULD have gone into an infinite loop, it
                #     will INSTEAD return the failure value.  (In
                #     our case, infinity.)
                cache[args] = f(*args)
            # 13) And whether we just calculated it, or had it
            #     from before, the answer should be cache[args].
            return cache[args]

        # 7) As a nicety, we make f_memo report itself as whatever
        #    name f had for itself.  This will, for example, make
        #    stack backtraces look nicer.
        f_memo.__name__ = f.__name__

        # 8) Returning f_memo here with f_cycle and the old f
        #    bound to it tells Python to make it become the new f.
        return f_memo

    # 4) Returning decorator here with f_cycle already bound is what
    #    tells python to replace f with decorator(f).
    return decorator

fail = float("infinity")

# 2) f_cycle will be a function that takes any arguments and
#    returns infinity.
@memo_cyclic(lambda *args: fail)
def f (...)
    ...