Written by romain
on April 15, 2018

Project Euler in Scala

One month ago I have decided to start the Project Euler in Scala. Project Euler is a series of both mathematical and computer programming challenges.

All problems are numbers related, well explained and concise. I find it easy and interesting to get along with them.

My main motivation was to know more about Scala. I’m using it in my day to day work since few months now and I wanted to get a deeper look at all possibilities this language offers, including its functional approach to solve problems.

Scala is focus on expressiveness and composability, meaning that smaller functions can be assembled to create larger programs. This is one of the main idea of functional programming.

Let’s prove this by taking the first problem where we have to find sum of all multiples of 3 or 5 below 1000. If you take an imperative approach you would end up with something like this:

public class Main {
    public static void main(String[] args) {
        int sum = 0;

        for (int i = 1; i < 1000; i++) {
            if (i % 3 == 0 || i % 5 == 0) {
                sum += i;
            }
        }

        System.out.println(sum);
    }
}

I’ve taken Java just for to show an example of an imperative approach in general, Java has now Lambdas and Stream API, but that’s not the purpose of the post.

This code does the job, but is verbose and can be hard to understand because of the following:

nested control structures with for and if
for loop and increment of i describes more about machine work
defining a variable sum which is not yet sum as it’s getting incremented in for loop

Let’s see now how we can make a cleaner version of this program in Scala.

First, we can create list of integers from 1 until 1000 by this way:

scala> val numbers = 1 until 1000 // same as 1.until(1000)
numbers: scala.collection.immutable.Range = Range 1 until 1000

This is a cool shortcut that removes need of a for loop and it’s very readable.

Next, we can use method filter on this range to only keep numbers that are multiple of 3 or 5:

scala> val numbers = (1 until 1000).filter(x => x % 3 == 0 || x % 5 == 0)
numbers: scala.collection.immutable.IndexedSeq[Int] =
Vector(3, 5, 6, 9, 10, 12, 15, ...)

filter method will apply given predicate on every number of the range and will keep the number if it returns true or filter it out otherwise.

filter method is one of many methods available to every Scala collection. You can have a list of these methods by looking at Traversable Trait documentation.

All Scala collection implements this trait and most of available methods use a foreach loop under hound and reduce need to write them in our code. We can use them for different purposes like filtering, transforming every element in another collection or accumulating them with fold methods, and so on.

Finally, we can apply another Scala collection method: sum. It’s a fold method and will give us sum of all elements on the previously filtered number collection:

// Note that we can omit parenthesis when calling
// a method that do not take parameters
scala> val result = numbers.sum
result: Int = 233168

We can reduce what we did in 6 lines of code in our imperative example in a one liner:

object Main {
  def main(args: Array[String]): Unit = {
    println((1 until 1000).filter(x => x % 3 == 0 || x % 5 == 0).sum)
  }
}

We can extract predicate in filter method into a separate method to gain readability:

object Main {
  def isMultipleOf3Or5: Int => Boolean = _ % 3 == 0 || _ % 5 == 0

  def main(args: Array[String]): Unit = {
    println((1 until 1000).filter(x => isMultipleOf3Or5(x)).sum)
  }
}

Compared to the imperative example, we don’t have any nested control structure or variable that’s getting incremented.

To sum up, this example was trivial but it showed one Scala main aspect: composability. We can assemble small functions to create the desired behavior.

Of course not every Euler problems can be solved so easily and sometimes requires math Theorems, plain loops or more complex concepts like recursion.

You can follow my ongoing work here: https://github.com/romibuzi/euler-scala

← Top