#### Description

From Project Euler:

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

n→n/2 (nis even)n→ 3n+ 1 (nis 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?

## No comments:

Post a Comment