{"id":269,"date":"2010-06-27T19:43:50","date_gmt":"2010-06-28T03:43:50","guid":{"rendered":"http:\/\/www.madpickles.org\/rokjoo\/?p=269"},"modified":"2012-04-09T20:10:54","modified_gmt":"2012-04-10T04:10:54","slug":"project-euler-problems-15-16-17","status":"publish","type":"post","link":"https:\/\/www.madpickles.org\/rokjoo\/2010\/06\/27\/project-euler-problems-15-16-17\/","title":{"rendered":"Project Euler Problems #15, #16, #17"},"content":{"rendered":"

Problem #15<\/a>
\nStarting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?<\/p>\n

I often used this question during interviews and suprisingly, very few candidates were able to make much progress with it. I wasn’t looking for a candidate to code it 100% correctly on a whiteboard, but I expected them to at least come up with a way to attack the problem as well as a way to optimize their code. I struggled to optimize it initially due to a stupid bug and the fact I had just driven 4hrs to Yosemite after work, but at least I had an idea \ud83d\ude09<\/p>\n

Of course there is a way to arrive at the solution purely via combinatorics, but that’s no fun…the first step to breaking down the problem is to realize one can only move right or down at any given point in the grid. This leads to a simple recursive solution:<\/p>\n

\r\ndef computeSlow(d,r):\r\n if d == 0 or r == 0:\r\n  return 1\r\n else:\r\n  return computeSlow(d-1,r) + computeSlow(d,r-1)\r\n\r\n# compute a 5x5 grid\r\nprint computeSlow(5,5)\r\n<\/pre>\n
This works, but an 11×11 grid gives my computer pause, and by 13×13 it doesn’t return. The problem is many of the sub-problems being solved by the recursion get solved over and over and over again. Using caching\/memoization<\/a> allows us to solve the problem in the blink of an eye:<\/p>\n
\r\ncache = dict()\r\n\r\ndef compute(d,r):\r\n key = str(d) + \",\" + str(r)\r\n if r > d: #no point storing the same value for 3,5 and 5,3\r\n  key = str(r) + \",\" + str(d)\r\n if d == 0 or r == 0:\r\n  return 1\r\n else:\r\n  if key in cache:\r\n   return cache[key]\r\n  else:\r\n   temp = compute(d-1,r) + compute(d,r-1)\r\n   cache[key] = temp\r\n   return temp\r\n<\/pre>\n
Problem #16<\/a>
\nWhat is the sum of the digits of the number 2^1000?<\/p>\n
This can be solved easily via the commandline:<\/p>\n
\r\npython -c 'sum(map(int,str(2**1000)))'\r\n<\/pre>\n
Problem #17<\/a>
\nHow many letters would be needed to write all the numbers in words from 1 to 1000?<\/p>\n
I tried to solve this via pen and paper, but made an error along the way, so I ended up translating it to code. Computers are really good at not making arithmatic mistakes. First I broke the numbers down into reusable parts:<\/p>\n
\r\noneToNine = [\"one\",\"two\",\"three\",\"four\",\"five\",\"six\",\"seven\",\"eight\",\"nine\"]\r\ntenToNineteen = [\"ten\",\"eleven\",\"twelve\",\"thirteen\",\"fourteen\",\"fifteen\",\"sixteen\",\"seventeen\",\"eighteen\",\"nineteen\"]\r\nties = [\"twenty\",\"thirty\",\"forty\",\"fifty\",\"sixty\",\"seventy\",\"eighty\",\"ninety\"]\r\n<\/pre>\n
Then I totalled up the number of characters for the numbers 1-99:<\/p>\n
\r\noneToNinetynineCount = sum([len(x) for x in oneToNine])\r\noneToNinetynineCount += sum([len(x) for x in tenToNineteen])\r\noneToNinetynineCount += sum([len(x) for x in ties])\r\noneToNinetynineCount += sum([len(x)+len(y) for x in ties for y in oneToNine])\r\n\r\ntotal = oneToNinetynineCount\r\n<\/pre>\n
Next I computed 100-999. It’s easy to shortcut since, for example the range 300-399 contains 1 threehundred, 99 threehundredand and then the counts for 1-99.<\/p>\n
\r\nfor x in oneToNine:\r\n xHundredCount = len(x) + 7 # hundred = 7 chars\r\n total += xHundredCount + (xHundredCount + 3) * 99 + oneToNinetynineCount # and = 3 chars\r\n<\/pre>\n
Lastly one just needs to add 11 to the total for the number onethousand.<\/p>\n","protected":false},"excerpt":{"rendered":"
Problem #15 Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner? I often used this question during interviews and suprisingly, very few candidates were able to make much progress with it. I wasn’t looking for a candidate to code it 100% correctly […]<\/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\/269"}],"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=269"}],"version-history":[{"count":5,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/posts\/269\/revisions"}],"predecessor-version":[{"id":666,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/posts\/269\/revisions\/666"}],"wp:attachment":[{"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/media?parent=269"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/categories?post=269"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/tags?post=269"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}