The Curious Schemer

The following sentence is false. The preceding sentence is true.

Archive for April 2011

Scala and Project Euler

with 5 comments

After struggling with Eclipse Scala plugin for so long, FINALLY I managed to get the latest (beta) plugin working with Eclipse Helios (3.6.x).

I’ve got to admit that my expectation was not that high in the beginning, I was expecting yet another episode of WTFs and stupid crashes with this plugin as well. But… the plugin turned out to be pretty good, actually. My very first Scala Hello World actually works! It runs! No crashes (yet)!

So what should one do with a new language to try out? I’m looking for a bunch of bite-sized problems to learn about Scala the language, not a new library, or a new algorithm, and gawd, no web applications! (I especially hate it when a language tutorial starts with a freaking application in a domain that I don’t give a damn about.)

Project Euler comes to the rescue. To quote:

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

The motivation for starting Project Euler, and its continuation, is to provide a platform for the inquiring mind to delve into unfamiliar areas and learn new concepts in a fun and recreational context.

Sounds promising.

The very first problem is very easy, so I don’t think anyone would mind me posting a spoiler here, but SPOILER ALERT anyway if you continue below!

object Test {
  def main(args : Array[String]) : Unit = {
    println(sumMultiplesOfXAndYBelowLimit(3, 5, 1000))
  }

  def sumMultiplesOfXAndYBelowLimit(x: Int, y: Int, limit: Int) = {
    (1 to limit - 1) filter (s => (s % x) == 0 || (s % y) == 0) sum
  }
}

Not a sophisticated solution by any stretch of imagination.

Say instead of doing the modulus stupidly for each number between 1 and 999, one can sum (3, 6, 9…) and (5, 10, 15…) and subtract (15, 30, 45…) (because the numbers in the last group are double counted).

Or if you remember the Gauss anecdote, you can do it even simpler by using a variant of the approach.

But I particularly like how Scala makes it very clear and readable:

    (1 to limit - 1) filter (s => (s % x) == 0 || (s % y) == 0) sum

“From 1 up to but not including the limit, take all the numbers that are not multiples of x or y, and sum them up”

Nice! Maybe I’d get to continue posting actively again after such a long hiatus :)

EDIT: as Jem commented below, this solution can be expressed even more cleanly using until, like this

    (1 until limit) filter (s => (s % x) == 0 || (s % y) == 0) sum

Written by rayfd

April 2, 2011 at 2:33 am

Posted in Scala

Follow

Get every new post delivered to your Inbox.