Posts Tagged ‘prob 11’

Problem 11 – Products in a Grid

June 19, 2009

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:

            if(grid[i][j]):
                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)):
            adjH.append(grid[i][j])
            adjV.append(grid[j][i])
            if(i and i < len(grid) - 4 + 1 and j < len(grid) - i):
                adjDU.append(grid&#91;j&#93;&#91;j+i&#93;)
                adjDL.append(grid&#91;j+1&#93;&#91;j&#93;)
        adjH.append(0)
        adjV.append(0)
        adjDU.append(0)
        adjDL.append(0)
        adjMD.append(grid&#91;i&#93;&#91;i&#93;)

    # 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)
        try:
            endidx = list.index(0)
        except:
            pass

        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.

Advertisements

A Question About Input

June 18, 2009

Has anyone figured out how to import data from text files?  My initial approach to problem 11 was to convert the entire table to a string by hand.  This was slow and tedious, but it worked.  After getting the correct answer, I looked at the posts on Project Euler.net and learned some more efficient methods.  But these still require me to type a few characters for each line of input and I don’t think they’d be practical for something like problem 67.