Project Euler–Problem 1

In my constant effort to learn more, I’ve run into  a number of road blocks with my progression with YABE. Why? Because I’m trying to write my blog engine in Ruby on Rails, while I have little real experience with Ruby, Rails, RSpec, Gems, etc. etc. So I am trying to rectify this by at least getting the basics of the “Ruby way” down. My solution? Well simple really. I am going to go through and start implementing the problems from Project Euler in Ruby and testing my solutions using RSpec. I’ve already completed a few of the problems, which you can see here. 

Basic Structure

The project has a very simple structure. There is a batch file in the \bin folder that allows you to run a simple console with all of the problems I have completed. Selecting a problem will give the result and how many seconds it took to generate that result. Every problem will have a corresponding specification, and possibly a number of utility classes (which will have their own specifications in turn).

Problem #1

From the Project Euler website:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

The trivial solution for this problem is actually quite easy. Simply loop through all of the number from 1 to 1000 (exclusive) and add all of the numbers that are divisible by 3 or 5. It might look something like this:

def sum
 (3...1000).inject do |sum,value|
  if value % 3 == 0 or value % 5 == 0
   sum + value
  else
   sum
  end
 end
end

Of course, I wasn’t satisfied with this solution, as there are two divisions going on for every value tested. And we are testing every value conceivable, even ones we can easily see will not be used. What if instead we were to only iterate through the multiples of 3 and 5, skipping all the other integers. We could then eliminate the division and the extra iterations.
How do we iterate over only the multiples of 3 and 5 though? Well, the first step is to notice that the multiples are spaced in a cyclical pattern. Take a look at this:

3	5	6	9	10	12	15	18
18	20	21	24	25	27	30	33
33	35	36	39	40	42	45	48
	+2	+1	+3	+1	+2	+3	+3

The cycle repeats itself every 6 values. So we can simply use this sequence to iterate over all of the multiples and just add all of the values less than 1000 together! Here is were it gets fun, we can use an Enumerable to handle the iteration of these values, and then use the standard Enumerable mixin methods to solve the problem, like so:

class Problem001
 include Enumerable
 ADD_VALUES = [2,1,3,1,2,3,3]  
 def each    
  n = 3    
  i = 0    
  while (true) do      
   yield n      
   n += ADD_VALUES[i]      
   i = (i + 1) % ADD_VALUES.length    
  end  
 end
 def sum(maximum)
  inject { |sum,value| break if value > maximum; sum + value; }
 end
end

You can see the full source and specification on github. Next time, we’ll take a look at problem #2: summing the even values of a Fibonacci sequence less than four million.