Saturday, December 31, 2011

Project Euler Problem 6 in Scala

This is 6 in a series.  The previous post is at, Project Euler Problem 5 in Scala.


Problem 6 was particularly satisfying for me.  You will see why when you see the code below.  I think the code deserves some discussion because it takes advantage of some pretty nice Scala features.

Project Euler problem 6 reads:
The sum of the squares of the first ten natural numbers is,  12 + 22 + ... + 102 = 385The square of the sum of the first ten natural numbers is, (1 + 2 + ... + 10)2 = 552 = 3025Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is   3025-385 = 2640. Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
So reading this question, we want to come up with an algorithm that iterates all the numbers 1..100.  During each iteration, we want to capture the sum of the squares, and the sum of the number.  Finally, we want to square the sum of the number and subtract the two values.  

Using some of Scala's syntactic sugar and its excellent functional handling we get:


object Problem6 {
  def main(args: Array[String]): Unit = {
    val results = ((0, 0) /: (1 to 100))((i, s) => {
      (i._1 + (s * s), i._2 + s)
    })
    println((results._2 * results._2) - results._1);
  }
}

If we take out the object definition and main method call, you can see that this is a two-liner (I could make it a one-liner, but I think that would sacrifice readability).  Once again, I am using the foldeLeft operator (/:).  This time, however, I am folding left on a sequence of values instead of a single value.  Because of this, you see the (0,0) declaration.  Scala also infers this type inside the body of the function, so I am storing to values i._1 and i._2.  Finally, we square the sums and subtract the sum of the squares.


Note that I actually multiplied results._2 by itself.  the '^' operator in Scala seems to work differently than I expected, and was giving me weird results.  I might have to look into that, but for now, we have a very succinct solution to this problem.