When doing Project Euler problem #14 I was running into a problem.
1 2 3 4 5 6 7 8 9 10 11 12 13
I started out by writing a method that took a number and returned the length of its Collatz sequence.
1 2 3 4 5 6 7 8 9 10 11 12
I was pretty sure the logic was correct, but when I ran it on a random number it generated a strange error.
I tried a bunch of different approaches to solve this, but none of them were working. I eventually realized that my method needed to be part of a class. I made a new class called Collatz and made each number a new instance of that class. After half an hour of nothing but error messages I decided I needed a new approach.
Without an internet connection I couldn’t just google the problem, so I thought a bit more. It dawned on me that numbers are already objects (since everything in Ruby is an object) and that they are already part of the Fixnum class.
I’ve never modified a core Ruby class or ‘reopened’ a class before, but I did vaguely remember learning about this in a lecture a few weeks ago. So I decided to just reopen the Fixnum class and add this new method.
1 2 3 4 5 6 7 8 9 10 11 12 13 14
I tired it out on a test number and it worked! Victory! This is pretty basic stuff, but it’s always satisfying to get past a problem you are stuck on it for a while. All that was left was to iterate over the first million numbers and determine which one had the longest Collatz sequence.
1 2 3 4 5
The program I built determined correctly that out of the first million numbers - 837,799 has the longest Collatz sequence. My code could be optimized further - it takes a good minute to run now. That would involved determining which numbers I don’t need to iterate over - for instance it seems that even numbers generally (but not always) have longer sequences as you increase, and that odd numbers generally have longer sequences than even numbers.