Posts Tagged ‘prob11’

Whoops! 11 Redux

September 4, 2009

For some reason, this week I decided to actually sign up for an account on projecteuler.net, our source of programming exercises. Then I went back and entered the answers 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 code.

I had two things incorrect. First, my inner loop wasn’t going far enough (shame!). Second, I was only accounting for one type of diagonal (shame!). Here’s my corrected (hopefully!) code:

def solve(grid):
    t = time.time()
    print grid
    ret = 0
    diffs = ( (1,0), (0,1), (1,1), (1,-1) )
    for i in xrange(0,len(grid)):
        for j in xrange(0,len(grid[0])):
            for dt in diffs:
            dx,dy = dt
            try:
                p = 1
                for k in xrange(0,4):
                    p *= grid[i+dx*k][j+dy*k]
                    ret = max(ret, p)
            except:
                pass
    t = time.time() - t
    return (ret, t)

I feel like I’m cheating a little when I use try-catch blocks like that. I feel like I should just index into the array to places I know exist, instead of relying on try to sort it out otherwise. But I also like not worrying about indexing (it was the source of one of my errors, after all). I also like looping over the “diffs”, to compute the product across, or down, or diagonally (either diagonal).

Now, on to new problems! I hope to post a solution to at least one this evening, before the (well-extended) deadline.

Advertisements