Friday, December 23, 2011

Project Euler Problem 4 in Scala

This is 4 in a series.  The previous post is at, Project Euler Problem 3 in Scala.

So I've already worked through 3 problems in Euler in hopes of using the exercises to help me learn some Scala.  In each of the previous solutions, I had a LOT of mutable state in my code.  As I get more comfortable with the language, however, I think I'm improving quite a bit.  Even so, it appears I still had a mutable variable in my first solution to this problem.  Problem 4 on the Project Euler site reads:

 A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91  99.
 Find the largest palindrome made from the product of two 3-digit numbers.
This doesn't seem too difficult to solve.  We can cast our integer values to strings, reverse them, and compare them to determine if they are a palindrome, and iterating all the 3 digit numbers, 100-999 is easy.  So, here's my first solution:

 object Problem4 {


  def main(args: Array[String]): Unit = {  
var highestPalendrome = 0;
    for(i <- 100 to 999) {
for(y <- 100 to 999) {
 var product = i * y;
 var productStr = product toString;
 
 if(productStr.reverse equals(productStr)) { 
   println(productStr)
   highestPalendrome = highestPalendrome max product;
 }
}
}
    println("Highest is " + highestPalendrome);
  }
}


In this solution I iterate the numbers and store the highest palendrome as I go.  Of course, the purpose of doing these exercises is to try and code without mutable state, so I had to get rid of that pesky highestPalendrome variable.  To do this, I took advantage of the Scala fold left facilities.  Turns out, this is a handy way to iterate a list and record results.  Here's version 2:



object Problem4 {
  def main(args: Array[String]): Unit = {  
val highestPalendrome = (0 /: (100 to 999))((highest, next)=>{
(0 /: (100 to 999))((tot2, nex2)=>{
 val product = next*nex2;
 if(product.toString.reverse.equals(product.toString)) {
     next*nex2
 } else {
 tot2
 }
}) max highest 
})
    println("Highest is " + highestPalendrome);
  }
}


You'll notice that this is essentially 1 statement, if you remove the main method and println.  You should also notice that I'm using some of Scala's syntactic goodness to make the code easier to read - the end of that statement, 'max highest' would be much uglier in Java - .max(highest).

Well, on to #5.  Maybe this time, I won't need a second iteration of the code...