## Saturday, April 11, 2009

### Project Euler problems 11 - 15

Here are problems 11 - 16 for project Euler.

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? I used an array of arrays to represent the grid.

``def euler11(grid)   maxVal = 0   (0..19).each{ |i|       (0..19).each{ |j|           # calculate horizontal           if j < 15 then               val = grid[i][j] * grid[i][j+1]                    * grid[i][j+2] *grid[i][j+3]               maxVal = val if maxVal < val               # calculate diag down right               if i < 15 then                                     val = grid[i][j] * grid[i+1][j+1]                       * grid[i+2][j+2] * grid[i+3][j+3]                   maxVal = val if maxVal < val               end               # calculate diag up right               if i > 3 then                   val = grid[i][j] * grid[i-1][j+1]                        * grid[i-2][j+2] * grid[i-3][j+3]                   maxVal = val if maxVal < val               end           end             # calculate vertical           if i < 15 then               val = grid[i][j] * grid[i+1][j]                    * grid[i+2][j] * grid[i+3][j]               maxVal = val if maxVal < val           end       }   }   maxValend``
Problem 12: What is the value of the first triangle number to have over five hundred divisors?

A triangle number is calculated as Tn = (n**2 + n) / 2.

``def euler12()   maxInt = 1 << 64   (500..maxInt).each{|val|       numT = (val**2 + val)/2       limit = Math.sqrt(numT)       stepVal = (0 == numT % 2) ? 1 : 2       divs = 0       (1..limit).step(stepVal){ |x|           if 0 == numT % x then               divs += 2           end       }                                                      return numT if divs > 500                         }                                                  end                                                    ``
Problem 13: Find the first 10 digits (most significant) of the sum of 100 50-digit numbers.

``def euler13numArr = [...]sum = numArr.inject(0){|s,n| n+s}val=sum.to_s.slice(0..9)end``
Problem 14: Find the starting number, under 1,000,000, that produces the longest chain for the Collatz problem.

The Collatz conjecture, or problem, generates a chain of numbers that terminates at 1. The chain is generated as Ni+1 = { Ni / 2 if Ni is even, 3 Ni + 1 if Ni is odd. At first read this was an "egads!" problem. But after looking at it was depressing easy to solve. The immediate solution that came to mind is a recursive algorithm using memoization. As follows, this runs in just under 59 seconds on my computer.

``def findLen(start, cache)   len = cache[start]   if len       return start, len   else       nextVal = (0 == start%2) ? start / 2 : 3 * start + 1       nextVal, len = findLen(nextVal, cache)       cache[start] = len + 1       return start, len +1   endenddef euler14()   cache  = { 1 => 1 }   maxVal = 1   maxLen = 1   (2..1000000).each{ |start|       val, len = findLen(start, cache)       if maxLen < len           maxLen = len           maxVal = val       end   }   return maxVal, maxLenend``
I came up with an iterative approach as well. This is the same algorithm as the recursive solution, but it pushes values with unknown chain length onto a stack, instead of pushing them onto the call stack. This runs in just over 10 seconds which give a good indication on how expensive function calls can be.

``def euler14_b()   cache = {1 => 1}   maxVal = 1   maxLen = 1   stack = []   (2..1000000).each{ |start|       val = start       len = cache[val]       while !len           stack.push(val)           val = (0 == val%2) ? val / 2 : 3 * val + 1           len = cache[val]       end       val = stack.pop       while val           len += 1           cache[val] = len           val = stack.pop                                     end       if maxLen < len           maxLen = len           maxVal = start       end   }   return maxVal, maxLenend``
Problem 15: How many routes are there through a 20 20 grid?

This was the most interesting problem out of this set. My first idea was to start at the end and generate valid paths back to the start. My second idea was, hey this is a tree, I should be able to calculate the number of paths directly. I thought that the number of paths should be proportional to the height of the tree. A good initial thought, but a little time at the white board showed that it was incorrect. A Google search turned up a blog entries by James Horsley and Real Ultimate Programming, after reading them and cracking open my dusty old discrete math books the answer is 40! / (20! * 20!) or C(40, 20).

To describe the answer in a bit more detail. One must always make 40 moves to get from the start to the finish. 20 moves down and 20 moves right. This gives 40! possibilities (20 down + 20 right). But since moves are indistinguishable, unordered, and without replacement, the total is reduced by 20! ways to select down moves, and 20! ways to select right moves. Or 40! / (20! * 20!).