-2
\$\begingroup\$

Problem:

Pascal’s triangle is a useful recursive definition that tells us the coefficients in the expansion of the polynomial (x + a)^n. Each element in the triangle has a coordinate, given by the row it is on and its position in the row (which you could call its column). Every number in Pascal’s triangle is defined as the sum of the item above it and the item that is directly to the upper left of it. If there is a position that does not have an entry, we treat it as if we had a 0 there. Below are the first few rows of the triangle:

Item:   0  1  2  3  4  5

Row 0:  1

Row 1:  1  1

Row 2:  1  2  1

Row 3:  1  3  3  1

Row 4:  1  4  6  4  1

Row 5:  1  5 10 10  5  1

...

Define the procedure pascal(row, column) which takes a row and a column, and finds the value at that position in the triangle. Don’t use the closed-form solution, if you know it.

Solution:

def pascal_with_memoization(row, column):
    """
    >>> pascal_with_memoization(3, 2)
    3
    >>> pascal_with_memoization(3, 3)
    1
    >>> pascal_with_memoization(5,4)
    5
    """
    cache = {}
    for row_indx in range(0, row + 1):
        cache.setdefault(row_indx, []).insert(0, 1)
    for col_indx in range(1, column + 1):
        cache.setdefault(0, []).insert(col_indx, 0) 
    def pascal(row, column):
        if column == 0:
            return cache[row][column]
        elif row  == 0:
            return  cache[row][column]
        else:
            value_1 = 0
            value_2 = 0
            lst = cache[row-1]
            if len(lst) > column: 
                value_1 = cache[row-1][column]
                value_2 = cache[row-1][column-1]
            elif len(lst) > column - 1:
                value_1 = pascal(row-1, column)
                value_2 = cache[row-1][column-1]  
                cache.setdefault(row-1, []).insert(column, value_1)
            else:
                value_1 = pascal(row-1, column)
                value_2 = pascal(row-1, column-1)
            return value_1 + value_2
    return pascal(row, column)

Can we improve the memoized code?

\$\endgroup\$
  • \$\begingroup\$ I did not see above code asking for nonlocal declaration of cache. I did not see any error like reference before assignment \$\endgroup\$ – overexchange Jul 8 '15 at 12:50
  • \$\begingroup\$ You're not actually implementing memoization because the cache is local the the function scope. Try declaring it outside the function instead. \$\endgroup\$ – jacwah Jul 8 '15 at 12:57
  • \$\begingroup\$ @jacwah We require cache to run this tree recursion efficiently. Other than this, there is no other purpose of this cache. so why global cache? I am using memoization to increase the performance of this tree recursion. Now, why memoization definition demands the cache to be global? am not sure. \$\endgroup\$ – overexchange Jul 8 '15 at 13:06
  • \$\begingroup\$ Because every time the function is called, a new version of cache is created. It has to be shared by all calls to the function to be useful. \$\endgroup\$ – jacwah Jul 8 '15 at 13:08
  • \$\begingroup\$ Instead of making it global, you could make it an attribute of the function itself - pascal_with_memoization.cache. \$\endgroup\$ – jacwah Jul 8 '15 at 13:09
10
\$\begingroup\$

The canonical way to memoize Python code is with a decorator, for example:

from functools import wraps

def memoize(func):
    @wraps(func)
    def wrapper(*args):
        if args not in wrapper.cache:
            wrapper.cache[args] = func(*args)
        return wrapper.cache[args]
    wrapper.cache = {}
    return wrapper

(functools.wraps is to handle the name of and any docstrings on the memoized function). Within the function itself, you don't need to refer to the cache at all; you simply make a recursive call and let the decorator handle the caching. This makes your code much easier to read and write, because the only difference is:

@memoize  # a single line
def pascal(row, column):
    if row < 0 or column < 0 or column > row:
        raise ValueError
    if column == 0 or column == row:
        return 1
    return pascal(row-1, column) + pascal(row-1, column-1)

You can see the cache fill up as you use the function:

>>> pascal.cache
{}
>>> pascal(4, 3)
4
>>> pascal.cache
{(3, 2): 3, (3, 3): 1, (2, 1): 2, (4, 3): 4, (2, 2): 1, (1, 0): 1, (1, 1): 1}
\$\endgroup\$
2
\$\begingroup\$

We can avoid generating some of the numbers of the triangle.

From looking at the triangle, every single value in the first column, ie if column == 0, has to be a 1, if asked to generate it we can just return 1. Similarly we can do the same if the column equals the row.

if(column == 0 or column == row):
    return 1

The next column is just counting upwards, so if column is 1 or if it is row - 1 (both conditions presuming row > 0), we can just return row.

if(row > 0):
    if(column == 1 or column == row - 1):
        return row

Lastly, and most importantly, since the triangle is symmetric, only half of it needs to be generated in the first place.

The mid point of the row is given by row/2 + 1.

0 1 2 ... x ... mid-1 mid mid+1 ... col ... row-1 row

We want the co-ordinate x such that (x + column)/2 = mid, ie mid is the mid point of both values

x = 2*mid - column
x = 2*(row/2 + 1) - column  
x = 2*row/2 + 2 - column
x = row + 2 - column

So the code is something like

if(column > row/2 + 1):
    return cache[row][row + 2 - column] //or pascal(row, row + 2 - column) if that has a check to see if a number is already stored

Important Note: this presumes you are generating each row from left to right, so the value will already produced.

I haven't tested the performance of such code, but since it doesn't have to recalculate half the triangle, I presume it would be faster

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.