2 Solutions To Project Euler Problem #1

In an effort to not go a whole month without blogging, and in the interest of posting some code samples, I give you two solutions to Project Euler: Problem #1. If you’ve never heard of it, Project Euler (pronounced “oiler” after the Swiss mathematician Leonhard Paul Euler) is a set of increasingly difficult programming challenges. Participants can write their programs in any language and the only goal is to solve the problems and learn something. There are no prizes and you don’t have to show your work.

I had looked at this project years ago, and I swear I thought I had already solved some of them, but maybe I only thought about doing it. Anyway, I have two solutions to the first problem; one in Groovy and the other in Scala. Here, then, is how Project Euler describes the problem

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.

So, the goal is to take a series of numbers from 0 to 1000, exclusive, find all the numbers divisible by 3 or 5 and add them together. Here’s the Groovy solution.

def subList = (0..<1000).findAll {it % 3 == 0 || it % 5 == 0} 

def sum = subList.inject(0) {i, sum -> sum + i}

println "Sum = ${sum}"

This is a very simple program, and I could have written it as a one-line program. I broke it up into a few lines for clarity. As you can see, the first line creates an exclusive range from 0 to 1000. It then calls the findAll method on that range, passing in a closure that will return true if the passed-in digit from the range, called “it” here, is evenly divisible by 3 or 5. The result of findAll is another collection, containing only those values that passed the divisibility test. We then take that list, passing 0 into the inject method, which will neatly sum the values up and return that value. Easy peasy.

Now here’s the Scala version. You’ll notice it is very similar to the Groovy solution.

val subList = for {
    i <- List.range(0, 1000)
    if i % 3 == 0 || i % 5 == 0
} yield i 

val sum = subList.foldLeft(0) {(i, j) => i + j}

println("Sum = " + sum)

I used a sequence comprehension to generate the sublist here. The bit beginning with “for” generates an exclusive range from 0 to 1000, which is then iterated over, assigning each value to “i”. Then, if it is divisible by 3 or 5, it is yielded up by the comprehension. The result is a collection of just those numbers that we want, assigned to the val called subList. We then call foldLeft on that sublist, doing exactly what we did in the Groovy solution. Again, pretty simple.

Now, I could have solved this one in an almost identical fashion to the Groovy solution by using the filter method of lists, but I wanted to solve it first using a list comprehension. Here is the second solution

val subList = List.range(0, 1000) filter {i => i % 3 == 0 || i % 5 == 0}

val sum = subList.foldLeft(0) {(i, j) => i + j}

println("Sum = " + sum)

I timed the solutions and all three finished in just over a second. The second Scala solution seemed ever-so-slightly faster than the other two.

As I get time, I will work on additional problems from the site and post the answers here. I don’t know that I’ll always do solutions in two languages, but I might.

Advertisements

One thought on “2 Solutions To Project Euler Problem #1

  1. I have a version which is quite similar to yours, but a bit shorter:


    println((3 until 1000).filter(x => (x % 3 == 0 || x % 5 == 0)).foldLeft(0)(_ + _))

Comments are closed.