Problem 11 – Products in a Grid


Problem 11 seems somewhat straightforward, once you’ve got the grid read in from a file or so. I should probably feel pretty guilty about not doing these more generally, to accept products of a chosen number (instead of 4) of adjacent terms. Right now, though, I just feel tired.

Here’s what I came up with, as a first go:

def solve(grid):
    ret = 0
    for i in xrange(0,len(grid)):
        for j in xrange(0,len(grid[0]) - 4 + 1):
            p = grid[i][j] * grid[i][j+1] * grid[i][j+2] * grid[i][j+3]
            ret = max(ret, p)
            p = grid[j][i] * grid[j+1][i] * grid[j+2][i] * grid[j+3][i]
            ret = max(ret, p)
            p = grid[j][j] * grid[j+1][j+1] * grid[j+2][j+2] * grid[j+3][j+3]
            ret = max(ret, p)
    return ret

In the inner loop, I compute the products in each direction, starting at the index [i][j]. I realized you can improve this inner loop slightly, by not multiplying each product by grid[i][j] initially. Since all of them are being multiplied by that factor, you might as well find the biggest of the products without that factor, then multiply by it, and then take the max with the previous best result. And if grid[i][j] is 0, there’s no point in doing any products starting there. So you can replace the inner loop above with the following:

                p = max(grid[i][j+1] * grid[i][j+2] * grid[i][j+3],
                        grid[j+1][i] * grid[j+2][i] * grid[j+3][i],
                        grid[j+1][j+1] * grid[j+2][j+2] * grid[j+3][j+3])
                ret = max(ret, p*grid[i][j])

I then realized that this problem could be reduced to problem 8. In that problem, you were just looking for the biggest product among adjacent things in a list. The code I used, today, to solve that, is basically the code from the end of my post last time I talked about problem 8:

def bigprod(list, num):
    """ Largest product of num consecutive elements of list

    Assumptions: len(list) >= num, list contains only positive integers
    p = reduce(lambda x,y:x*y, list[0:num-1], 1)
    f = 1 # a fake (for now) first digit of previous product
    ret = 0

    for idx in xrange(0, len(list) - num + 1):
        p = p // f
        p *= list[idx+num-1]
        f = list[idx]
        ret = max(ret, p)
    return ret

So it remains to see how to convert the grid to a list. We can get sort of “horizontally adjacent” terms by just working across rows. If we stick a 0 between rows, then products of adjacent terms in the list are only non-zero when they came from terms that were adjacent, horizontally, in the grid. We can do essentially the same thing for vertically adjacent, and diagonally adjacent, though the indexing takes slightly more thinking about for the diagonal bits. Here’s my code implementing this idea:

def solve(grid):
    """ The biggest product of 4 adjacent numbers in the grid

    Method: re-write grid as a bunch of lists, have bigprod to the work
    Assumption: the grid is square
    adjH, adjV, adjMD, adjDU, adjDL = [], [], [], [], []
    for i in xrange(0, len(grid)):
        for j in xrange(0, len(grid)):
            if(i and i < len(grid) - 4 + 1 and j < len(grid) - i):

    # stick all of the adjacents together, they already end in 0 (besides MD)
    list = adjH + adjV + adjDU + adjDL + adjMD

    ret = 0

    while(len(list) >= 4):
        endidx = len(list)
            endidx = list.index(0)

        if(endidx >= 4):
            ret = max(ret, bigprod(list[0:endidx], 4))

        list = list[endidx+1:]

    return ret

I’ve not done a particularly formal performance comparison of these, but an informal look indicates that the first solution is much faster. It completes the problem on the assigned input (on my machine) in about .002 seconds, while the second solution takes .003 seconds. Big difference, no? I also fed them random grids of larger sizes. Looking at grids with size 200, the first solution takes along the order of .2 seconds, while the second is more like 1.5 seconds.

Tags: , ,

One Response to “Problem 11 – Products in a Grid”

  1. Whoops! 11 Redux « Leonhard Euler’s Flying Circus Says:

    […] I’d gotten for my past solutions, and did pretty well. However, I messed up number 11 (in 4 versions!). I thought perhaps I should perhaps some corrected […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: