CODEWITHSUNDEEP
pythonmemoization
Robin Andrews
Robin Andrews

Reputation: 3794

Memoization By Hand in Python Function Using Tuples as Cache Keys

I'm trying to implement by-hand memoization in the following function, which calculates the optimal please of eating chocolates given that waiting supposedly increases the pleasure:

def joy(chocs, day):
    n = len(chocs)
    if n == 1:
        return day * chocs[0]
    left = day * chocs[0] + joy(chocs[1:], day + 1)
    right = day * chocs[n - 1] + joy(chocs[:n - 1], day + 1)
    return max(left, right)

I want to use a cache dictionary to store prvious results, but I'm stuck on the implementation. Here's my attempt so far:

def joy(chocs, day, cache={}):
    if (chocs, day) in cache:
        return cache[(chocs, day)]
    n = len(chocs)
    if n == 1:
        return day * chocs[0]
    left = day * chocs[0] + joy(chocs[1:], day + 1)
    right = day * chocs[n - 1] + joy(chocs[:n - 1], day + 1)
    return max(left, right)

I'm stuck on what to use as the key/value for storing the left/right results.

Can anyone help me to complete the memoized version of the function please?

Upvotes: 0

Views: 473

Answers (2)

Joran Beasley
Joran Beasley

Reputation: 113988

just invert your logic

def joy(chocs, day, cache={}):
    if (chocs, day) not in cache:
        n = len(chocs)
        if n == 1:
            cache[(chocs,day)] = day * chocs[0]
        else:
            left = day * chocs[0] + joy(chocs[1:], day + 1)
            right = day * chocs[n - 1] + joy(chocs[:n - 1], day + 1)
            cache[(chocs,day)] = max(left, right)
    return cache[(chocs, day)]

this way your cache is ensured

Upvotes: 1

Varun Nayak
Varun Nayak

Reputation: 310

Store the result in your cache before you return.

result = max(left, right)
cache[(chocs, day)] = result
return result

There's no need to store the result of the base case.

Upvotes: 1

Related Questions