Scala + Project Euler

Someone at work posted a message to our scala mailgroup asking about the solution to the first problem on Project Euler, which for the uninitiated is a set of increasingly complicated problems designed to provide the reader with some interesting challenges to learn a new language.

The specific question asked was about why a collection based implementation would be slower in scala than java, but raised a couple of interesting points for me. First of all I didn't actually look at the problem, but went straight to the code, and unsurprisingly neither implementations were particularly clear. Another colleague then posted an alternative implementation, and then I went to read the problem description because the solution seemed so simple! So, know the problem you are trying to solve - that's lesson 1.

Part of the reason the original solution was not immediately clear was the use of a getMultiples method, which was using recusion. Nothing wrong with that, as refactoring promotes lots of small methods, but in writing java in scala the author had produced something unclear.

Contrast:

def getMultiples(base: Int, bound: Int, ms: List[Int]) = {
 bound match {
   case 0 => ms
   case _ => getMultiples(base, bound - 1, (base * bound) ++ ms)
 }
}

with

def getMultiples(base: Int, bound: Int) =
       base until bound by base

I think this is a great illustration of how a higher level language can make a solution much clearer, or really unclear.

And then a better solution:

Stream.from(3)
     .filter(i => i % 3 == 0 || i % 5 == 0)
     .takeWhile(_ < 1000)
     .foldLeft(0)(_ + _)