I guess my solution to #18 was good enough since it worked for #67 as well.

Problem #67

Find the maximum total from top to bottom of the triangle below:

input = # triangle goes here

tree = []
cache = []

input.split("n").each do |row|
  tree << []
  cache << []
  row.split("s").each do |i|
    tree.last << i.to_i
  end
end

def sum tree, cache, row, index, total

  if tree[row] == nil or tree[row][index] == nil
    return 0
  end

  if cache[row][index] != nil
    return total += cache[row][index]
  end
  
  left  = sum( tree, cache, row + 1, index, total )
  right = sum( tree, cache, row + 1, index + 1, total )

  cache[row][index] = [left, right].max + tree[row][index]

end

puts sum( tree, cache, 0, 0, 0 )

Ran pretty fast in 1.8.6

$ time ruby 18.rb
real	0m0.012s
user	0m0.008s
sys	0m0.004s

$ time ruby 67.rb
real	0m0.115s
user	0m0.104s
sys	0m0.012s

And a little worse in 1.9

$ time ruby1.9 18.rb
real	0m0.028s
user	0m0.016s
sys	0m0.008s

$ time ruby1.9 67.rb
real	0m0.116s
user	0m0.104s
sys	0m0.004s

I found this one to be very similar to problem #15, so it “clicked” pretty quickly. I basically just store the solutions so I don’t have to do any re-computing.

I saw a pretty slick method in the forums that made use of Ruby’s Enumerable module which I’ll have to give a go next time I run into something like this.

Problem #18

Find the maximum total from top to bottom of the triangle below:

input = # triangle goes here

tree = []
cache = []

input.split("n").each do |row|
  tree << []
  cache << []
  row.split("s").each do |i|
    tree.last << i.to_i
  end
end

def sum tree, cache, row, index, total

  if tree[row] == nil or tree[row][index] == nil
    return 0
  end

  if cache[row][index] != nil
    return total += cache[row][index]
  end
  
  left  = sum( tree, cache, row + 1, index, total )
  right = sum( tree, cache, row + 1, index + 1, total )

  cache[row][index] = [left, right].max + tree[row][index]

end

puts sum( tree, cache, 0, 0, 0 )

I overrode the Fixnum class, and there’s a teensy bit of recursion going on, but over all it was really simple. The hardest part was writing out all the unique numbers for my word hash.

Problem #17

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

words = {
  1 => "one",
  2 => "two",
  3 => "three",
  4 => "four",
  5 => "five",
  6 => "six",
  7 => "seven",
  8 => "eight",
  9 => "nine",
  10 => "ten",
  11 => "eleven",
  12 => "twelve",
  13 => "thirteen",
  14 => "fourteen",
  15 => "fifteen",
  16 => "sixteen",
  17 => "seventeen",
  18 => "eighteen",
  19 => "nineteen",
  20 => "twenty",
  30 => "thirty",
  40 => "forty",
  50 => "fifty",
  60 => "sixty",
  70 => "seventy",
  80 => "eighty",
  90 => "ninety"
}

class Fixnum

  def to_english words
    str = ""
    if self >= 100
      str = "#{words[(self / 100)]}hundred"
      if self % 100 > 0
        str = "#{str}and#{(self % 100).to_english(words)}"
      end
    elsif self > 20
      str = '#{words[(self / 10) * 10]}#{words[ self % 10 ]}'
    elsif self == 1000
      str = 'onethousand'
    else
      str = words[self]
    end
    str
  end

end

total = 0

(1..1000).each do |i|
  total += i.to_english(words).size
end

puts total

Cake.

Problem #16

What is the sum of the digits of the number 2^(1000)?

n = 0

(2 ** 1000).to_s.scan(/./).each do |i|
  n += i.to_i
end

puts n

I spent a lot of time drawing this on paper trying to figure out an equation behind it before I gave up and went the recursive route. There was an obvious pattern behind it…but I’m not a mathematician. I could see from the traces that I could store information about exhausted routes to save a lot of cycles, so I’m happy with my solution.

Problem #15

How many routes are there through a 20 x 20 grid? (no backtracking)

def move grid, x, y
  size = grid.size - 1

  if x > size or y > size
    return 0
  end

  if x == size and y == size
    return 1
  end

  if grid[x][y] != nil
    return grid[x][y]
  end

  grid[x][y] = move(grid, x + 1, y) + move(grid, x, y + 1)
  
end

size = ARGV[0].to_i
grid = Array.new(size + 1) do |i|
  i = Array.new(size + 1)
end

puts move(grid, 0, 0)

Straight up brute force was too slow, so I would store the sequence counts for numbers I’d already seen in a hash table.

Problem #14

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Which starting number, under one million, produces the longest chain?

def advance heap, n, count

  if heap.has_key? n
    return heap[n] + count
  end

  if (n & 1) == 0
    return advance(heap, n / 2, count + 1)
  end

  advance(heap, 3 * n + 1, count + 1)

end

heap = Hash[0,0,1,1]
answer, max = 1, 1

1_000_000.times do |i|

  heap[i] = advance(heap, i, 1)

  if heap[i] > max
    max = heap[i]
    answer = i
  end
  
end

puts answer 

Just finished up Problem #13. Straight up brute force ran really well, but I figured I could save some cycles by only adding up the last 11 digits.

I ran this and #25 through ruby 1.8.6 and 1.9.1 and was suprised to see that it ran much slower in the newer version. Everything else I’ve tried has run much better.

Here are some numbers I found to be pretty indicative. Bummer.

$ time ruby 13.rb

real	0m0.009s
user	0m0.008s
sys	0m0.000s

$ time ruby1.9 13.rb

real	0m0.026s
user	0m0.020s
sys	0m0.004s

Problem 13

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

input = File.new("files/13.txt", "r")
total = 0

input.each do |i|
  total += i.slice(0..10).to_i
end

puts total.to_s.slice(0,10)

Skipping around a bit, I saw that #25 looked pretty easy. It was. I saw in the forums that someone had used binary search and a calculator which I thought was pretty clever, but mine was just brute force.

Problem #25

What is the first term in the Fibonacci sequence to contain 1000 digits?

Solution

max  = 10 ** 999
a, b, i = 1, 1, 2

while b < max
  i += 1
  a, b = b, b + a
end

puts i

I took a couple swings at problem #12 before I finally got it. I’m definitely over my head mathematically, but that’s part of the fun and I’m certainly learning a lot along the way. Big thanks to Dr. Math for his excellent explanation of how to find a number’s number of factors.

Problem #12

What is the value of the first triangle number to have over five hundred divisors?

Surely it’s not the perfect solution, but it ran in under 4 seconds on ruby 1.9, so I’m happy with it. Looking at it now, it all seems obvious but I must have started over at least a dozen times. Here are a few recurring Project Euler themes I’ve picked up on, as applied to this problem.

1. Like every other Project Euler problem, don’t repeat your calculations, cache it! Prime number computation is heavy.
2. If you don’t have to store something don’t. In this case it’s enough to count the distinct factors, you don’t have to store them.
3. Cut down your data set. Since we’re looking for a number that has over 500 factors then we don’t need to start looking until after the 500th triangle.

Enough talk, here’s the code:

require 'mathn'

primer  = Prime.new
primes  = [ primer.next ]
seed    = 500
n       = (seed * (seed + 1)) / 2
i       = seed + 1

def count_prime_factors primer, primes, n
  total = 1
  max   = Math.sqrt(n).to_i

  while primes.last < max
    primes << primer.next
  end
  
  primes.each do |i|
    count = 0
    while n % i == 0
      n = n / i
      count += 1
    end
    if count > 0
      total *= count + 1
    end
  end

  total
end

while(count_prime_factors(primer, primes, n) < seed)
  n += i
  i += 1
end

puts n