Project Euler-Problem 14

Description

From Project Euler:

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

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

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

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

NOTE: Once the chain starts the terms are allowed to go above one million.

Solution

The relatively straight-forward solution to this problem is to simply create an Enumerator that will generate the appropriate sequence from a given starting point. We can then generate all of the sequences that start with numbers up to one million and find the longest one.

class Problem014
  def sequence(start)
    Enumerator.new do |yielder|
      n = start
      (yielder << n) && (n = n.even ? n / 2 : 3*n + 1) while n > 1
      yielder << 1
    end
  end

  def chain_lengths
    Enumerator.new do |yielder|
      start
      yielder << [start, sequence(start).count] && start += 1 while start < 1_000_000
    end
  end
end

Problem014.new.chain_lengths.max_by { |start,length| length }[0]

There is one glaring problem with this solution though. We are computing sequences hundreds of times over. Take for example a sequence starting with the number 26:

26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Notice that this contains the entire sequence that starts with 13. Therefore, the length of the sequence is just the length of the sequence for 13 plus one. Similarly, the length of sequence 13 is just the length of sequence 40 plus one. And so on and so forth. So with a little memoization, we can actually reuse the sequence lengths we have already computed.

class Problem014
  def initialize
    @known_lengths = { 1 => 1 }
  end

  def sequence(n)
    n.even? ? n / 2 : 3*n + 1
  end

  def chain_length(start)
    return @known_lengths[start] if @known_lengths.include? start
    @known_lengths[start] = chain_length(sequence(start)) + 1
  end

  def chain_lengths
    Enumerator.new do |yielder|
      start = 2
      yielder << [start, chain_length(start)] && start += 1 while start < 1_000_000
    end
  end
end

Notice that now the sequence method only returns the next value in the chain. That is all that is necessary for us to look up and see if we already know that length. The chain_length method will then return a pre-computed length if we already know it, or the chain_length of the next value in the chain plus one. In addition, we will also store this length in case it is needed again for another sequence. Does all of this complication actually help? Well on my system I was able to go from 83s for the original algorithm down to 12s for the memoized version. Well worth the effort I think.

The full source and specifications can be seen on github. Next time, starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?