Learning Scala With Project Euler

by in Programming Languages
6 Flares 6 Flares ×

This article is a quick journey through the mind of a Scala newbie while learning the language. I work through a few Project Euler problems, refining solutions along the way so they use more idiomatic Scala. In the end I give some general impressions of the language, the install and setup process, the Scala community, and support for Scala within different development tools.

Euler

Picking up a new language is a good way to keep your skills up-to-date, feed your inner geek, add a new language to the programming toolbox, and can help to improve job satisfaction. There is some discussion about how often you should learn a new language, but I generally try to do it every few years. I’ve been debating about which of Scala, Ruby, Erlang, or Haskell to learn, but decided to jump in and at least get my feet wet with Scala.

If you haven’t heard of Project Euler yet, it’s a set of problems designed to be solved by some combination of mathematical insight and computer programming. It’s a pretty good way to pick up a new language since it gives you short concrete problems to solve, and once a problem is correctly solved you are given access to the forum for that problem which contains hundreds of solutions written in different languages.

Looking at the other Scala solutions gives me some idea of whether I’m writing nice idiomatic Scala code, or if I’m just mangling Java / Lisp / BASIC / whatever thinking so it can be contorted to fit the Scala syntax.

So lets get to the problems. Warning: Spoilers ahead for the first 3 Project Euler problems.

Project Euler Problem 1

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.

The way I’m going to approach this is to find the sum of all multiples of 3, add the multiples of 5, and subtract out the multiples of 15 so they aren’t counted twice.

Here is the my first attempt that worked:

object e1 {
  def main(args: Array[String]) {
	def answer = multOfX(999, 3) + multOfX(999, 5) - multOfX(999, 15)
	println(answer)
  }
  def multOfX(num: int, x: int): Int = {
	if (num % x != 0) multOfX(num - 1, x)
	else if (num < x) 0
	else num + multOfX(num - x, x);
  }
}

multOfX recursively adds to num as x is decremented to 0. Not too bad for a first try right? Well, here is a solution from the Scala Blog:

(1 until 1000).filter(n => n % 3 == 0 || n % 5 == 0).foldLeft(0)(_ + _)

Its a lot closer to what I would call idiomatic Scala, but is also a bit tougher to understand for the Scala newbie. The (1 until 1000) creates a range of numbers. The filter method then takes all of the numbers that are either a multiple of 3 or 5 and returns the new range. All we have to do now is add up the numbers from the new range. foldLeft applies the anonymous function (_ + _) to two anonymous parameters (represented by the two underscores). So the range (3, 5, 6, 9, 10) is folded like this (((((0 + 3) + 5) + 6) + 9) + 10) where the initial 0 comes from the 0 in foldLeft(0). Cool huh?

Project Euler Problem 2

Moving on to the second Project Euler problem:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

I was tempted to create the range of Fibonacci numbers and use filter and foldLeft like the first problem, but creating a range up to the 4 millionth Fibonacci number didn’t seem that wise. Here is what I came up with instead:

object e2 {
  def main(args: Array[String]) {
	println(getFibs(1, 2, 4000000))
  }
  def getFibs(fib1: int, fib2: int, until: int): int = {
	var newfib = fib1 + fib2
	if (fib2 > until) 0
	else if (fib2 % 2 == 0) fib2 + getFibs(fib2, newfib, until)
	else getFibs(fib2, newfib, until)
  }
}

Here we have another recursive function that goes along calculating the Fibonacci numbers and adding them up if they are even. It works, but lets take another tip from the Scala blog, and use lazy evaluation:

lazy val fib: Stream[Int] = Stream.cons(0, Stream.cons(1, fib.zip(fib.tail).map(p => p._1 + p._2)))
fib.filter(_ % 2 == 0).takeWhile(_ <= 4000000).foldLeft(0)(_ + _)

The first line creates a Stream of Ints called fib that will be evaluated lazily. The magic here is that the Ints in the Stream aren’t calculated until they are needed – fib contains instructions to create an infinite stream of Fibonacci numbers! So how did that work? Fib is defined as 0 followed by Stream.cons(1, fib.zip(fib.tail).map(p => p._1 + p._2)) That second stream is where the magic happens. First fib is zipped with its tail. zip takes two Streams and puts them together: (1, 2, 3) zipped with (a, b, c) gives ((1, a), (2, b), (3, c)). So zipping fib and its tail (every element but the first one), initially gives ((0, 1)). The map function collapses down the inner part by adding the two elements together, giving an initial Stream of (1). As new elements are needed from fib, they are evaluated in the same manner, generating an infinite Fibonacci sequence.

The next line is easy using what was learned from the first problem. We filter to get only even numbers, use takeWhile to force evaluation until the we find a number over 4 million, and then foldLeft to get the sum.

Project Euler Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

So how about creating a Stream of all of the prime factors, and then getting the largest one?

var limit = 600851475143L
lazy val primes: Stream[Long] =
Stream.cons(2,
            primes.map(x => {var tmp = x
			     (while((limit % tmp) != 0 && limit != 1) { tmp=tmp+1 });
			     limit = limit / tmp;
			     tmp}))
print(primes.take(10).last)

This looks a bit complicated, but its not so bad. So the Stream of prime factors stars out with 2 in order to give a starting place for looking for factors. The while loop then iterates through Longs starting with the last value in primes. Once a factor is found, that factor is divided out of limit and the new factor (tmp) is returned by the anonymous function as the next Long in primes. This continues until all the prime factors of limit are found, at which point limit is 1 and the loop just keeps returning the highest factor that was found.

The next line forces the lazy evaluation for the first 10 factors of primes, and then prints the last factor, which gives us the answer. 10 was just an arbitrary number large enough to get the factor we were looking for. A more general solution would take from primes until it got two sequential elements that were the same, and then print that one.

First Impressions of Scala

Euler stamp

A few hours of dabbling isn’t really enough to get a good feel for the syntax, so I won’t comment on that too much, besides to say I was a bit disconcerted that terminating a statement with a semicolon is optional. That just feels strange.

I was very impressed with how easy it was to get set up and running. If you have experience with Java, the scala and scalac commands behave like the familiar java and javac. It was easy to find an emacs mode, one of my standard development tools.

Despite the overall favorable impression I got from the language and supporting tools, all was not well in the land of documentation. The official Scala docs and quick start guides are in PDF format which is a shame since copy-paste don’t work and it doesn’t seem like the documentation is indexed well by google. The Scala community would be much better served by putting its docs in html format so the googlebots can easily index the stuff and start putting it in search results. I tend to use more of a hack and slash method of learning – looking up syntax as I need it. And I was frustrated at the lack of documentation out there when googling for things like “scala keywords” or “loop syntax scala”. In many ways I suppose this is because the Scala community is much smaller than that of many other languages, so there just aren’t enough people writing about Scala and creating tutorials, docs covering basic syntax, etc.

So those are my first impressions of Scala. I’d like to hear Scala gurus and newbies alike give their own impressions or suggest alternate ways of solving the Euler Problems.

6 Flares Twitter 3 Google+ 1 Facebook 2 6 Flares ×
# September 15, 2008 5 Comments