nosuchblogger

I'm starting my Scala journey with baby steps. As mentioned in my initial Scala post, I've picked the very first Project Euler problem as my first Scala kata.

As it is very short, I'll repeat it here:

Find the sum of all the multiples of 3 or 5 below 1000.

This is very similar to the FizzBuzz programming problem so shouldn't cause me too many problems:

Write a program that prints the numbers from 1 to 100. But for multiples of three print "Fizz" instead of the number and for the multiples of five print "Buzz". For numbers which are multiples of both three and five print "FizzBuzz".

The Spec

Anyway, let's get going. Starting small, the sum of 3 and 5 below 1 should be zero:

import SumOfMultiples3And5._
import org.scalatest.Spec
import org.scalatest.matchers.ShouldMatchers
import org.scalatest.junit.JUnitRunner
import org.junit.runner.RunWith

@RunWith(classOf[JUnitRunner])
class SumOfMultiples3And5Spec extends Spec with ShouldMatchers {
  describe("Sum under 1") {
    it ("should total 0") {
      sumOfMultiples(0) should equal (0)
    }
  }
}

And to get this to pass, this is the simplest object I could find to create in Scala:

object SumOfMultiples3And5 {
  def sumOfMultiples(upto:Int) = 0
}

This wasn't too bad to start with, looks somewhat similar to Java. The very first time I had the = 0 part slightly differently: more verbose and Java like with : Int = { return 0 }. You can remove the return type (it will be inferred) and also the return statement, so simply becomes = 0.

The next test of interest is the sum below 4 should be 3:

describe("Sum under 4") {
  it ("should total 3") {
    sumOfMultiples(3) should equal (3)
  }
}

This fails, but with a slight tweak, we can get it working:

def sumOfMultiples(upto:Int) = if (upto < 3) 0 else 3;

OK, ploughing on, let's move up to 5:

describe("Sum under 6") {
  it ("should total 8") {
    sumOfMultiples(5) should equal (8)
  }
}

I'll make it pass again, but realise I will now have to do some refactoring to remove the nested if clauses:

def sumOfMultiples(upto:Int) =
  if (upto < 3) 0 else
    if (upto < 5) 3 else 8;

My first instinct is to take an imperative approach: create a sum variable, loop round updating the sum as we go. However, that's not very interesting, so let's see how a recursive approach goes.

I'll start off at the number passed in, then calling ourselves, adding the value to the result if that number is divisible by 3 or 5. Something like this:

def sumOfMultiples(upto:Int) : Int = {
  if (upto < 3) return 0
  return valueIfDivisible(upto) + sumOfMultiples(upto - 1)
}

And the valueIfDivisible method:

def valueIfDivisible(value:Int) = if (value == 3 || value == 5) value else 0

Really just trying out some aspects of the language here, but the valueIfDivisible method could be a little more generic by passing in the 'condition' (also renamed so it reads a little better):

def valueIf(value:Int,isDivisibleCond:Int=>Boolean) = if (isDivisibleCond(value)) value else 0

This also shows passing functions into a method - the isDivisibleCond argument. The Int=>Boolean definition specifies the function takes an integer and returns a boolean. We need the actual method which supports our condition:

def isDivisibleBy3Or5(value:Int) = value%3 == 0 || value%5 == 0

And the recursive call now adds the function isDivisibleBy3Or5 as an argument:

return valueIf(upto, isDivisibleBy3Or5) + sumOfMultiples(upto - 1)

This should be it. Check with the actual initial requirement:

describe("Sum under 1000") {
  it("should total 233168") {
    sumOfMultiples(999) should equal (233168)
  }
}

Yes, it's green.

Going a little further

I can't simply leave it here. After a bit more reading, we can simplify the class - instead of having the 3 separate methods, we can nest methods within one another. The class simply becomes the following:

object SumOfMultiples3And5 {
  def sumOfMultiples(upto:Int) : Int = {
    def valueIf(divisibleCond:()=>Boolean) = if (divisibleCond()) upto else 0
    def divisibleBy3Or5() = upto%3 == 0 || upto%5 == 0

    if (upto < 3) return 0
    return valueIf(divisibleBy3Or5) + sumOfMultiples(upto - 1)
  }
}

Note that the nested methods can use the arguments from the outer method, therefore making these even easier to read.

Where next

I think this code is relatively clear, but I was still intrigued to see if we can do better. I think I managed it, but that will have to wait until the next post. In my next post, I'll also give my initial impressions of Scala.

Update: Can we do better?