Ståle’s weblog

The first problem in project Euler is trivial:

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.

This can be solved quite easily mathematically. By using the formulas for calculating the sum of all numbers up to a given number. However, since I am working on learning Scala, I think it’s a nice problem to start the language at.

Let’s first try and solve it in a traditional Java way in scala

1
2
3
4
5
6
7
8
9
10
11

object Euler001 {
    def main(args:Array[String]) {
        var i=1
        var sum=0
        while (i<1000) {
            if (i%3 == 0 || i%5 ==0) sum += i
            i += 1
        }
        println(sum)
    }
}

Now, anyone that has done functional programming will cringe at this. There are several problems with this program. First, it’s too verbose, we can express the same in less code. Additionally we are using var instead of val. In Scala, we prefix variables with var or val. For Java comparison, val means the variable is final and not reassignable, var means it is. We don’t need to say the types here, as that’s inferred.

But, I don’t want to drone on too much about language details, you can learn those other places for Scala. I will first make an example that is more compact, and introduces things that are different from Java.

1
2
3
4
5
6
7

object Euler001 extends Application {
    var sum = 0
    for (i <- 1 to 999) {
        if (i%3 == 0 || i%5 ==0) sum += i    
    }
    println(sum)
}

Now we still have a var variable here, but the iteration part looks much nicer. The thing to note here is the 1 to 999 construct. This actually is a 1.to(999) call. Numbers are true objects in Scala, with methods on them. However, the dots can be replaced with spaces for a more natural language. In addition, methods that take just 1 argument, we don’t have to include (), so this makes for a nicer to read syntax. We also changed the object to extend Application, which means we don’t need to declare the main method.

I have also not really explained how object works in Scala. They are like static methods in Java classes, but you can extend them. So you can add methods from another class in your static context by simply extending a class.

Still, we can do better. Functional languages focus on immutable values, and extracting information from expressions. The reality is that every expression in Scala results in a value, the value from the last statement in the expression.
So we could actually write:

1

    sum += if (i%3 == 0 || i%5 ==0) i else 0

But functional languages are more about immutability, so we should get rid of the last var, sum. Instead we should construct expressions that results in final parts off the process:

1
2
3
4
5

object Euler001 extends Application {
    val numbers = 1 to 1000 filter((x)=>x%3 == 0 || x%5==0)
    val sum = numbers reduceLeft(_+_)
    println(sum)
}

Here I introduce even more unfamiliar constructs for Java programmers. 1 to 999 produces a sequence of the numbers 1 to 999, the filter method applies a method to this sequence. The expression (X)=> means that we are creating a function that takes x. The code following could be a block in {}, but since it’s a simple statement we just include it directly. This method will actually get inferred by the compiler to have type (x:Int):Boolean – because it’s a method taking and Int (Scala wrapper for the integer primitive) and returns a boolean. The Int type is inferred from the type of the sequence, Int. And the return type is inferred from the result off our expression. The filter method also requires the return type to be boolean, so anything else would have been a compiler error.

The next piece of the magic is the reduceLeft on numbers. This method, basing on the previous line, should have looked something like (a,b)=>a+b. But in Scala there is a shorthand for such expressions, called partial functions. The underscore serves as a placeholder, and the first underscore will take the value off the first method parameter, and the second will take the second parameter and so on. The reduceLeft method takes a 2 argument functions, and returns another value off the same type. This is applied to all elements in the sequence, and the final reduced value is returned, which is the sum.

I might have gotten some terminology and concepts wrong in the text, but all the above code works in Scala. I hope to do more posts on Scala in the future, possibly solving some harder Euler problems. The above problem can of course also be solved by simple math:

(Add every 3rd number to 999 to every 5th number to 999 and subtract every 15th number, as we count those twice otherwise)

Staale Programming, Scala Euler, Programming, Scala