{"id":215,"date":"2010-02-05T22:55:39","date_gmt":"2010-02-06T06:55:39","guid":{"rendered":"http:\/\/www.madpickles.org\/rokjoo\/?p=215"},"modified":"2010-02-18T13:26:21","modified_gmt":"2010-02-18T21:26:21","slug":"project-euler-problems-9-10-11","status":"publish","type":"post","link":"https:\/\/www.madpickles.org\/rokjoo\/2010\/02\/05\/project-euler-problems-9-10-11\/","title":{"rendered":"Project Euler Problems #9, #10, #11"},"content":{"rendered":"

It’s time to get back to discovering how much math and python I’ve forgotten…<\/p>\n

Problem #9
\nFind the only Pythagorean triplet (a,b,c where a < b < c and a^2 + b^2 = c^2) where a + b + c = 1000.\n\nThe 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:\n\n\n\n

\r\ndef findPythagoreanTriplet(abcSum):\r\n for c in xrange(abcSum \/ 3 + 2, abcSum \/ 2):\r\n  aPlusB = abcSum – c\r\n  for b in xrange(aPlusB \/ 2 + 1, min(c, aPlusB)):\r\n   a = aPlusB – b\r\n   if a**2 + b**2 == c**2:\r\n    return a * b * c\r\n\r\nprint findPythagoreanTriplet(1000)\r\n<\/pre>\n
Problem #10
\nFind the sum of all the primes below two million.<\/p>\n
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.<\/p>\n
\r\nmax = 2000000\r\nmaxM = max - 2\r\nr = range(2,max)\r\nc = 1\r\nfor n in r:\r\n m = n - 2\r\n if r[m] != 0:\r\n  c += 1\r\n  m += n\r\n  while m < maxM:\r\n   r[m] = 0\r\n   m += n\r\n\r\nprint sum(r)\r\n<\/pre>\n
Problem #11
\nWhat is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20\u00c3\u201420 grid<\/a>?<\/p>\n
The first thing I did was convert the 20x20 grid into a python list of lists:<\/p>\n
\r\ng = []\r\nfile = open(\"problem0011.txt\",\"r\")\r\nwhile True:\r\n temp = file.readline()\r\n if not temp:\r\n  break\r\n g.append(map(int,temp.split()))\r\nfile.close()\r\n<\/pre>\n
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:<\/p>\n
james-eeepc% time python problem0011.py
\n[70600674, [89, 94, 97, 87]]
\npython problem0011.py  0.08s user 0.02s system 98% cpu 0.101 total<\/p>\n
\r\nimport operator\r\ndef findMaxProduct(grid,subSize):\r\n numCols = len(grid[0])\r\n numRows = len(grid)\r\n maxProduct = 0\r\n maxSubList = []\r\n for x in xrange(numCols):\r\n  for y in xrange(numRows):\r\n   doRight = x <= numCols - subSize\r\n   doDown = y <= numRows - subSize\r\n   doLeft = y >= subSize - 1\r\n   if doRight:\r\n    subList = grid[y][x:x+subSize]\r\n    product = reduce(operator.mul,subList)\r\n    if product > maxProduct:\r\n     maxProduct = product\r\n     maxSublist = subList\r\n   if doDown:\r\n    subList = [grid[y+i][x] for i in xrange(subSize)]\r\n    product = reduce(operator.mul,subList)\r\n    if product > maxProduct:\r\n     maxProduct = product\r\n     maxSublist = subList\r\n   if doDown and doRight:\r\n    subList = [grid[y+i][x+i] for i in xrange(subSize)]\r\n    product = reduce(operator.mul,subList)\r\n    if product > maxProduct:\r\n     maxProduct = product\r\n    maxSublist = subList\r\n   if doDown and doLeft:\r\n    subList = [grid[y+i][x-i] for i in xrange(subSize)]\r\n    product = reduce(operator.mul,subList)\r\n    if product > maxProduct:\r\n     maxProduct = product\r\n     maxSublist = subList\r\n return [maxProduct,maxSublist]\r\n\r\nprint findMaxProduct(g,4)\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
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 […]\n<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[18,11,19,17],"_links":{"self":[{"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/posts\/215"}],"collection":[{"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/comments?post=215"}],"version-history":[{"count":4,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/posts\/215\/revisions"}],"predecessor-version":[{"id":219,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/posts\/215\/revisions\/219"}],"wp:attachment":[{"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/media?parent=215"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/categories?post=215"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/tags?post=215"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}