Ståle's weblog

The fourth problem in project euler deals with palindromes:

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.

One off the main functions we will need for this, is off course a method to check if a number is a palindrome. This is easiest to check on strings rather than numbers directly. And a string function would work for all integral types we could want to check (Int, Long, BigInt).

object Util {
    def isPalindrome(txt: String, s:Int, e:Int):Boolean = {
        if (s>e) true
        else if (txt(s) == txt(e)) isPalindrome(txt,s+1,e-1)
        else false
    }
    def isPalindrome(txt:String): Boolean = isPalindrome(txt,0,txt.length-1)
    implicit def toStr(n:Int): String = n.toString
}

I have created a separate Util object for this, as I know there are future problems that also deal with palindromes. The code uses 2 pointers, one from the start and one from the end. As long as they point to the same character we move them towards the middle of the string. If the end is less than the start, no conflicts found, and we have a palindrome. Otherwise the number is not a palindrome.

A new concept in this Util class is the implicit def method, that is just a simple converter from Int to String. The implicit tells the Scala compiler that it can use this function for implicit conversion. Implicit conversions are a neat feature off scala that converts expressions to new types if necessary. Here it allows us to call the isPalindrome method with an Int rather than a String. The Compiler sees that there is a mismatch, but it has an implicit conversion in scope that can turn the Int into a String.

So given the following usage:

isPalindrome(91 * 99)

This would be an error, as isPalindrome expects a String, but we are giving it an Int. The compiler finds the implicit conversion, and changes the code to the following:

isPalindrome(toStr(91*99))

With the palindrome method in hand, we can now look for ways to find the highest palindrome that is a product of 2 3 digit numbers. This actually provided me with some problems, as I spent some time finding the optimal solution. If we look at the most brute force approach first, we have:

val products = for (a <- 100 to 999;b <- 100 to 999) yield a*b
println(products.filter(isPalindrome(_)).toList.sort(_>_).head)

The for loop at line 1 will have a iterate from 100 to 999, and for each a iterate b 100 to 999. yield evaluates an expression to return a Seq, in this case off Int. This gives us over 800000 numbers, all the possible products.
Line 2 first filters on all values that are palindromes. isPalindrome(_) is equivalent of (a) => isPalindrome(a). The filtered list will now just contain the Int values that are palindromes. Next we sort the list, here (_>_) is equivalent of (a,b) => a > b as a sort method. And finally we pick the first element from the result.

However, we go through too many solutions here that aren’t necessary. We should instead start from 999*999 and go down, and stop whenver we exceed the highest palindrome earlier found. To do this we are going to take advantage off the filter functions that exists in for loops in Scala. Scala for loops are a lot more powerfull than those we have in Java.

My final solution is thus:

object Euler004 extends Application {
    var max = 0
    val palindromes = for {
        a <- 100 to 999 reverse;
        if (a*999 > max);
        b <- a to 999 reverse;
        c = a*b;
        if (c > max && isPalindrome(c))
    } yield {max=c;max}
    println (palindromes.reverse(0))
}

We here need to have a variable to keep track off the max value found so far. The for expression now expands across multiple lines. On line 3 we say to iterate a from 999 to 100, so every following expression will be evaluated for each value off a from 999 to 100. Next we have an if, this checks if a*999 is bigger than our currently found max. If it isn’t, we don’t need to check anything else. This serves as a guard for the rest of the expressions in the for loop. On line 5 we iterate b from 999 to a, and on line 6 we just store the product in c. Finally we have a guard to check that c is bigger than max, and it is a palindrome.

In the yield we now have a block instead of just a single expression. This is because we need to assign max first, then return max.

Now we have a list of palindromes in increasing order. Any product found less than the highest palindrome will be skipped. To find the actual result, we just reverse the list and print out the first entry.

I did spend quite some time on this task to get a good solution. I have a faster one using while loops, but it doesn’t look as elegant. Additionally I read parts off the for loop segment in the Scala book yesterday, so I was interested in trying out some off the principles on this problem. I was originally planning on doing this with actors, just to see how they worked out, but I haven’t yet read fully about them. Perhaps I will deal with a later problem using actors.