Implementing memoization in recursive code break functionality

Question

I can't seem to figure out what broke my code.

I wrote a code that takes a pyramid:

[[1],
 [2,3],
 [4,5,6],
 [7,8,9,10]]

Starting from the head (pyramid[0][0]) calculates the maximum sum possible to achieve by moving to either the item below, or to the item below and to the right recursively

In this example the output should be 20.

This is the code without memoization, which works fine:

def max_trail(pyramid,row=0,col=0):
    if row == (len(pyramid)-1):
        return pyramid[row][col]
    else:
        return pyramid[row][col] + max(max_trail(pyramid ,row+1 ,col),
                                       max_trail(pyramid ,row+1, col+1))

But when I try to apply memoization, something along the way breaks. What am I missing?

This is the broken code:

def max_trail_mem(pyramid,row=0,col=0,mem=None):
    if mem==None:
        mem={}
    key = ((row),(col))
    if row == (len(pyramid)-1):
        if key not in mem:
            value = pyramid[row][col]
            mem[key]=value
            return mem[key]
        return mem[key]
    else:
        key = (row+1),(col)
        if key not in mem:
            mem[(row+1),(col)] = max_trail_mem(pyramid ,row+1 ,col,mem)
        key = (row+1),(col+1)
        if key not in mem:
            mem[(row+1),(col+1)]=max_trail_mem(pyramid ,row+1, col+1,mem)
    return max(mem[(row+1),(col)],mem[(row+1),(col+1)])

This has taken hours off my poor studential life. Any help will be greatly appreciated!

Answer 1

You forgot pyramid[row][col] + before max(... at your last return. Adding it gives 20 for your example (see last line of code):

def max_trail_mem(pyramid,row=0,col=0,mem=None):
    if mem==None:
        mem={}
    key = ((row),(col))
    if row == (len(pyramid)-1):
        if key not in mem:
            value = pyramid[row][col]
            mem[key]=value
            return mem[key]
        return mem[key]
    else:
        key = (row+1),(col)
        if key not in mem:
            mem[(row+1),(col)] = max_trail_mem(pyramid ,row+1 ,col,mem)
        key = (row+1),(col+1)
        if key not in mem:
            mem[(row+1),(col+1)] = max_trail_mem(pyramid ,row+1, col+1,mem)
    return pyramid[row][col] + max(mem[(row+1),(col)],mem[(row+1),(col+1)])

Answer 2

from timeit import timeit
import math

from repoze.lru import CacheMaker
cache_maker=CacheMaker()


def max_trail(pyramid,row=0,col=0):
    if row == (len(pyramid)-1):
        return pyramid[row][col]
    else:

        mt1 = max_trail(pyramid ,row+1 ,col)
        mt2 = max_trail(pyramid ,row+1, col+1)
        return pyramid[row][col] + max(mt1, mt2)

@cache_maker.lrucache(maxsize='1000', name='pyramid')
def max_trail_with_memoization(pyramid,row=0,col=0):
    if row == (len(pyramid)-1):
        return pyramid[row][col]
    else:

        mt1 = max_trail(pyramid ,row+1 ,col)
        mt2 = max_trail(pyramid ,row+1, col+1)
        return pyramid[row][col] + max(mt1, mt2)

# Build pyramid
pyramid = ()
c = 0
for i in range(20):
    row = ()
    for j in range(i):
        c += 1
        row += (c,)
    if row:
        pyramid += (tuple(row),)

# Repetitions to time
number = 20

# Time it
print('without memoization:  ', timeit('f(t)', 'from __main__ import max_trail as f, pyramid as t', number=number))
print('with memoization      ', timeit('f(t)', 'from __main__ import max_trail_with_memoization as f, pyramid as t', number=number))




print max_trail(pyramid)

Returns:

without memoization:   3.9645819664001465
with memoization:      0.18628692626953125