Beginner Algorithms in Ruby: Sum of Multiples of 3 and 5

If you are new to programming, I’m going to recommend a book that will allow you to take your eyes off a screen (unless you really prefer it online) for 30min-1hr day: Code Complete (link to amazon).

In this blog, I will apply some lessons learned from chapter 9 on Pseudocode Programming Process (PPP) with an easy algorithm. If you’re looking into this blog, I’m hoping you have an understanding of procedural and object-oriented Ruby, and little bit of math. We’ll be using a few essential methods to solve our problem.

First things first, here is our problem statement:

• If we list all of 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.

Before we write some pseudocode, we’ll need to do a little research in order to check the prerequisites, and fully define the problem.

What is a multiple of 3 or 5 or any number for that matter? If that is elusive to you, brush up here. What’s a natural number? Brush up here. So basically, x divided by either three or five has a remainder of 0.

Do we include our limit (10, or 1000, etc)? Carefully read the problem, and you’ll notice it’s less than 10, not ‘less than or equal to’.

What is the expected return? True, false, an array, etc? In this case, return the sum, an integer.

Do we have any tests or examples given to us? In this scenario, RSpec is used. But sometimes, its as easy as logging to the command terminal, so we’ll implement a little of that too.

Let’s talk big-Oh here. But not much. The shortest vs longest time taken, aka time and space complexity is an important consideration when dealing with two functions. Spare yourself confusion and let’s keep it simple. Follow:

First part of strategy, the program needs to collect all of the numbers that return true when evaluated as multiples of 3 or 5 somewhere (one loop, cost will be the limit, or n). Second part, I need to add together the value of each multiple collected, and have that returned. We know that not every number is a multiple of 3 and 5, of course, so the multiples collected as we approach our limit is always a fraction of n, but as n goes to infinity that fraction is negligible as less than 1, so this second loop is then n as well. Thus, we’re looking at n² as the run time for this algorithm, worse case.

We’re not persisting anything to db. Yet storage is important. We’ll use an array.

In considering worse case scenarios, a syntax error could start an endless loop (consider breaking points)…maybe ruby blocks up my CPU usage to 99% like this from an endless loop…

I feel ready to write my pseudocode:

/* given a limit, collect all the multiples of 3 or 5 up to 1 less than the limit, and return the sum of those multiples*/
create a function to collect the multiples that takes a limit as an argument
  define data-type/structure for the storing
    create a loop for each non-zero number to 1 less than limit
      test each one of those numbers against some mathematical evaluation, and if either comes back true, shovel that number into my defined data structure
    return that data
end
create a function that uses the other function to return a sum, that also takes in the limit as an argument
  define our sum and set a base, in this case 0
    call our first function, and use its return to do some math
      return that math
end

So first time through here’s what I come up with:

It’s verbose and not very concise, but as far as procedural Ruby is concerned, it takes what I’ve spelled out in plain english, and converted into Ruby talk.

But is it efficient? Can it be refactored? And where are our tests? No, yes, and when I was asked to solve this in real life, as maybe you have been, tests were already pre-written. This scenario, the environment was configured with the use gem rspec in the Gemfile to write the tests. I simply run:

$ruby <file name>.rb

But rather than lament the ugliness of this code, I’m going to push on forward to the object oriented method because it brings up a good reinforcement of the basics, and I’ll do refactoring there, how about that? Moreover, its not really ugly, its just a skeletal idea of how it could really work.

Let’s pseudocode our class by first asking ourselves some simple questions.

First, when will our objects be created? How will we access instances, variables, and methods, and what are their scope? What functions will we need, and when will they be called?

Pseudocode:

class name
 class attributes - need to read, not write
   create objects asap when given a limit
     upon creation, make the limit variable accessible
     make our multiples immediately available too by calling a function that will return a data-type that is a collection of our multiples
   end
   function to return collection of multiple
    make use of our limit, but make sure to go 1 less 
    do some math, evaluate, what returns true goes into our collection
      return that collection
   end
   function to add up those multiples
    do math and return the sum
   end
end

Unfamiliar with some of that syntax? For reject, and reduce (see also inject). What’s happening here? Calling new ie initializing a new object, we are immediately invoking, or calling an action, collect_multiples to set our instance variable @mutliples to the array returned, and with our reader, we can then use it in our sum_multiples method, which when called will ultimately satisfy our original task. This code, while given some white space for visual clarity, is clean and concise, opting for meta-code to simplify. Yes, I could avoid the attr_reader scenario, and opt for using instance variables to satisfy the tests, but I like that this way says upfront “hey, we have some instance variables that available through methods that can be used throughout this class/program” — its just a little more ‘classy’ to me doing it like that. A last little bit of research for a refresher: readers and writers. But if you want to see another cool way to write it, with tests…

Some fun little changes there, like setting @limit to limit minus 1, then when calling .collect_multiples on our object saved to an instance, changing the spread to include the value of the instance variable ‘limit’ as well. Also, we can’t call a.multiples anymore, since we’ve removed the attr_reader. Does that matter for larger apps, of course. For this problem we’re solving, we can get around not having to make use of that. Little tricky, but it spells things out in a more streamlined way.

Hope this read helps someone new on their journey into programming. It’s when you start working on a higher level like this that you’ll begin to see the fun in challenges, rather than that hopeless feeling of despair that nothing is quite clicking yet. Test, fail, test, fail, repeat till the lightbulb turns on, or its clicks, or you go ‘aha’, and it’ll be very satisfying work.