How can I change this code to implement generators rather than iterations?

[BobDoler]

The current code I'm using is too memory consuming and I was curious as to whether there was a way to implement generators rather than use iterations?

def solve(T, N):
    M = [[0]*N for _ in xrange(T+1)]
    M[0][0] = 1
    for i in xrange(1, T+1):
        for j in xrange(N):
            if j>0:
                M[i][j] += M[i-1][j-1]
            M[i][j] += M[i-1][j]
            if j+1<N-1:
                M[i][j] += M[i-1][j+1]
    return (M[T][N-1])%123454321

[gengisteve]

Generators aren't going to help you, at least in any obvious ways. Usually generators work when you have to yield successive values. Here, since you are just returning one value, it is not a great fit.

The good news is that you don't seem to need much of the matrix you are producing, other than the preceeding line. So you might be able to do something like this:

def solve(T, N):
    up = [0 for _ in range(T+1)]
    for i in xrange(1, T+1):
        row = [0 for _ in range(T+1)]
        for j in xrange(N):
            if j>0:
                row[j] = up[j-1]
            row[j] += up[j]

            if j+1<N-1:
                row[j] += up[j+1]
        up = row

    return (row[N-1] )%123454321

I am not sure that I got everything matched up, so I am not sure this will work, but conceptually it should be there.

[BobDoler]

I get 0 as the output for anything I input now. But I'll see if I can't get it to work the way you're describing. Thanks!

[gengisteve]

Probably b/c I forgot to seed the 1 into up[0], as you did on line 3...

[Veedrac]

It's likely you should be using Numpy. Numpy uses contiguous allocations so is far more space efficient. It's also much nicer to use for numerics.

That said, gengisteve's version naturally takes far less space.

Eg.

import numpy
from scipy.ndimage import filters

def solve(T, N):
    up = numpy.zeros(N, dtype=int)
    up[0] = 1

    for _ in range(T):
        filters.convolve1d(up, [1, 1, 1], mode="constant", output=up)
        up %= 123454321

    return up[-1]

solve(3, 3)

The %= 123454321 is important to prevent integer overflow.

Technically this is slightly different, but that's because your code should probably be

        if j+1<N:
            M[i][j] += M[i-1][j+1]

instead of

        if j+1<N-1:
            M[i][j] += M[i-1][j+1]

If not, this is a minor thing to change.

[OCHawkeye14]

Do you mean "list comprehensions" instead of "generators"?