Saturday, October 15, 2011

Project Euler and Scala problem 1

I recently found a Web site called, Project Euler (PE).  Its a site full of problems that are intended to be solved by coding.  As I am also experimenting with Scala, I figured this would be a fun way to keep my skills sharp solving problems while learning the nuances of another language.


What I am finding is very interesting.  First, my 'functional' skills need work.  I'm attempting to solve each problem with no mutable state, but as you will see, my first iteration usually has some sort of mutable state and it takes me a little bit to refactor it.  Part of this is due to the fact that I spend my day job programming in an OO language, part of it is due to learning Scala, but part of it is just that I need more practice in the functional way of thinking.


I am fortunate in that I have two friends who are also interested in PE and who have started working through the problems as well, so we swap notes after we solve the solutions, which further helps understanding.  


I thought I would blog about the problems as I work through them.  The format I have settled on this this:

  1. I will present my first, rough, solution to the problem, along with a brief summary of the PEdocumentation.
  2. I will present a refactored version of the same problem that makes the code much more functional and maintainable.
  3. If the PE documentation reveals a math or programming concept that would improve the code, another version of the algorithm may be posted.
It's my hope that presenting my progress in this fashion is both interesting and revealing for other programmers. I work primarily in Java, so this might also be a good way for Java programmers to see how things translate to Scala.  Of course I am not a Scala expert, so I'm sure there will be lots of comments with room for improvement.  At least, that's my hope.


Here is PE's first problem:

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.
Well, this seems simple enough.  Simply iterate all the numbers to 1000, testing if they are divisible by 3 or 5 along the way.  The first version of my code looks like this:

object Problem1 {


  def main(args: Array[String]): Unit = {  
    var sum = 0;
    for( i <- Iterator.range(0,1000) if i % 3 == 0 || i % 5 == 0) {
      sum += i;
    }
    print(sum);
  }
}


There's nothing inherently wrong with the code above.  Except I have that mutable variable, sum,  in there.  So, what's a more functional way to think about this?  Thanks to the inspiration from my co-worker, Sean, we have a more functional version of the code above:


object Problem1 {
  def main(args: Array[String]): Unit = {
    val count = (1 to 999);
    val sum = (0 /: count)((total, next) =>
      {
        if (next % 3 == 0 || next % 5 == 0) {
          total + next;
        } else {
          total;
        }
      });
    println(sum);
  }
}


In this version, we've made the sum immutable (by using val instead of var), so it can only be assigned once.  We've also used the left-fold operator, \:, to iterate the range.  Finally, we've converted the contents of the for loop to a function block that gets executed on each 'fold'.  This version looks pretty good, but after reviewing the PE docs, we pick up another little math trick.  


Instead of iterating the numbers, we can take the sum of all the multiples of 3, sum of all the multiples of 5 and then subtract all the multiples of 15.  There's also a proof that demonstrates how to find the sum (I won't reprint it here, if you are interested, unlock the problem on the PE site).


The final version of our code looks like:


object Problem1 {
  def main(args: Array[String]): Unit = {
println(sumDivisibleBy(999,3) + sumDivisibleBy(999, 5) - sumDivisibleBy(999, 15));
  }
  
  def sumDivisibleBy(limit:Int, divisor:Int) : Int =  {
val p = limit/divisor;  
divisor * (p*(p+1))/2; 
  }
}


So in the end, we don't iterate the range at all.  This solution would also scale well (what if we wanted to add all the multiples of 3 and five for all numbers under 1 million...)


So there it is. A brief walk through my process on Project Euler problem 1. Let me know what you think.