James Pine Has A Blog

It’s time to get back to discovering how much math and python I’ve forgotten…

Problem #9
Find the only Pythagorean triplet (a,b,c where a < b < c and a^2 + b^2 = c^2) where a + b + c = 1000. The first thing I decided to do was figure out some bounds based on the various constraints. Since a < b < c, the minimum value of c is approximately (1000 / 3) + 2. The maximum value of c is 1000 - 3; however, since a^2 + b^2 has to equal c^2, the maximum value of c is actually much less, approximately 1000 / 2. If I had thought about it more, perhaps I would have realized this was another problem that could be solved with pen and paper...alas, instead I wrote this:

def findPythagoreanTriplet(abcSum):
 for c in xrange(abcSum / 3 + 2, abcSum / 2):
  aPlusB = abcSum – c
  for b in xrange(aPlusB / 2 + 1, min(c, aPlusB)):
   a = aPlusB – b
   if a**2 + b**2 == c**2:
    return a * b * c

print findPythagoreanTriplet(1000)

Problem #10
Find the sum of all the primes below two million.

I just brute forced this problem, generating all prime numbers below 2 million with a Sieve of Eratosthenes. Since I new I had to sum them, I replaced all the numbers that weren’t prime in the sieve with 0. I’m sure at some point I’ll have to use more efficient prime number generating algorithms, but this is still pretty fast.

max = 2000000
maxM = max - 2
r = range(2,max)
c = 1
for n in r:
 m = n - 2
 if r[m] != 0:
  c += 1
  m += n
  while m < maxM:
   r[m] = 0
   m += n

print sum(r)

Problem #11
What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20×20 grid?

The first thing I did was convert the 20x20 grid into a python list of lists:

g = []
file = open("problem0011.txt","r")
while True:
 temp = file.readline()
 if not temp:
  break
 g.append(map(int,temp.split()))
file.close()

Then I wrote a function to solve the general problem of finding the maximum product of N adjacent numbers. The function just walks the grid in N square size chunks. It doesn't do any dividing to save on the number of multiplications, so it is doing some extra work, but it is still pretty fast:

james-eeepc% time python problem0011.py
[70600674, [89, 94, 97, 87]]
python problem0011.py 0.08s user 0.02s system 98% cpu 0.101 total

import operator
def findMaxProduct(grid,subSize):
 numCols = len(grid[0])
 numRows = len(grid)
 maxProduct = 0
 maxSubList = []
 for x in xrange(numCols):
  for y in xrange(numRows):
   doRight = x <= numCols - subSize
   doDown = y <= numRows - subSize
   doLeft = y >= subSize - 1
   if doRight:
    subList = grid[y][x:x+subSize]
    product = reduce(operator.mul,subList)
    if product > maxProduct:
     maxProduct = product
     maxSublist = subList
   if doDown:
    subList = [grid[y+i][x] for i in xrange(subSize)]
    product = reduce(operator.mul,subList)
    if product > maxProduct:
     maxProduct = product
     maxSublist = subList
   if doDown and doRight:
    subList = [grid[y+i][x+i] for i in xrange(subSize)]
    product = reduce(operator.mul,subList)
    if product > maxProduct:
     maxProduct = product
    maxSublist = subList
   if doDown and doLeft:
    subList = [grid[y+i][x-i] for i in xrange(subSize)]
    product = reduce(operator.mul,subList)
    if product > maxProduct:
     maxProduct = product
     maxSublist = subList
 return [maxProduct,maxSublist]

print findMaxProduct(g,4)