Fortune Cookie Says

You have much skill in expressing yourself to be effective.

Project Euler Problems 18 and 67

Problem 18 and problem 67 are the same problems. The difference being that problem 67 cannot be brute forced. These problems are given a triangle on numbers starting at the top and moving to adjacent numbers on the row below, find the path with the maximum sum.

My first thought was building a tree and using a greedy algorithm to find the path. However, a little thought, and sketching out trees, will show that you can easily build a tree where a greedy algorithm will fail to find maximum path. So what we need to no is traverse the tree and calculate the maximum value for each node. We can do the going down and then scan for the largest value form the nodes that form the bottom of the triangle, or go from the bottom up which causes the root node to have the largest value.

For my solution the triangle represented as an array of arrays. Where each element represents a row of the triangle, and each row is one element longer than the previous. Also each element e[r,i] has to be compared to the elements e[r+1,i] and e[r+1, i+1] where r is index of the row and i the index of the element in that row. The code is as follows.

# receives the table generated from readTable and calculate the largest
# value. The calculation starts with the second to the last table row and
# modifies every element e[r,i] = e[r,i] + max( e[r+1,i], e[r+1, i+1] ).
#
def calcTable( table )
  (table.length - 2).downto(0){ |r|
      table[r].each_with_index{ |val, idx|
          table[r][idx] =
              table[r][idx] + max(
                 table[r+1][idx],
                 table[r+1][idx+1])     
      }        
 }    
table[0][0]
end

Fortune Cookie Says

Your success in life must be earned with earnest efforts.

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 2020 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
       }
   }
   maxVal
end

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 euler13
numArr = [...]
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
   end
end

def 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, maxLen
end

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, maxLen

end

Problem 15: How many routes are there through a 2020 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!).

Visitor at Work

This needs a more clever title than this, but its been a long day.

Coming into work this morning I saw this guy at the revolving door and had to take his picture.

Fortune Cookie Says

You will have a long and wealthy life.

Project Euler problems 6 - 10

I finally found some time to sit down and do problems 6 through 10 on Project Euler.

Problem 6: Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

def euler6()
  (1..100).inject(0){|val,k| val += k} ** 2 -
  (1..100).inject(0){|val,k| val += k**2}
end

Problem 7: What is the 10001st prime number?

def euler7()
  myprime = Prime.new
  (1..10000).each{ myprime.next}
  myprime.next
end

Problem 8: Find the greatest product of five consecutive digits in the 1000-digit number.

The 1000 digit number is a string in my code.

def euler8(bigNum)
  len = bigNum.size
  stopAt = len - 5
  sliceStart = 0
  res = 0
  while sliceStart < stopAt do
      val = 1
      s = bigNum.slice(sliceStart, 5)
      s.each_char{|x| val *= x.to_i}
      res = val if res < val
      sliceStart += 1
  end
  res
end

Problem 9: There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

def euler9()
  val = 0
  (1..500).each{ |a|
      (a..500).each{ |b|
          c = (a**2 + b**2)**0.5
          next unless c == c.to_i # continue unless c is an integer
          val = a + b + c
          return a * b * c if val == 1000
          break if val > 1000
      } 
  } 

end

Project 10: Find the sum of all the primes below two million.

This was the only really challenging problem in this set. I tried to use Ruby's Prime class in a loop for this. When ran for 50,000 iterations it would return in about 14 seconds. For 2,000,000 I eventually killed the process after 15 minutes. The algorithm used in the Prime class seems to fall down when used to generate large lists of prime numbers.

I did some searching and found that most people were using some type of number sieve to generate the list of prime numbers, see Wikipedia here and here. I found and shamelessly stole a Ruby implementation of the Sieve of Eratosthenes from Paul Callagher. I slightly modified Paul's implementation to make it a standalone function instead of a class method.

# problem 10, find the sum of all primes below 2,000,000.
# prime series up to this limit, using Sieve of Eratosthenes method
# http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
#
# from http://tardate.blogspot.com/2008/10/rolling-project-euler-on-ruby.html
def sieve_of_eratosthenes( maxVal )
  limit = Math.sqrt(maxVal)                        
  a = (2..maxVal).to_a                             
  n = 2                                            
  while (n < limit) do                             
      x = n*2
      begin                                        
          a[x-2]=2                                 
          x+=n                                     
      end until (x > maxVal )
      begin
          n+=1
      end until ( a[n-2] != 2 )
  end
  a.uniq!
end

def euler10()
  sieve_of_eratosthenes( 2_000_000 ).inject(0){|val, x| val += x }
end

This code returns in about 4 seconds.