Created
July 21, 2012 21:06
-
-
Save pervognsen/3157191 to your computer and use it in GitHub Desktop.
my solution to jonsen's egg puzzle variant
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment