## Sunday, October 31, 2010

### Problem: Euler Task 4 - Largest Palindrome

Let's continue with the euler task programming series (http://projecteuler.net/index.php?section=problems ). Now, we will attack the 4th problem.

OK. Here it is, problem number 4:

"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."

First, we need  a function to check if a String is palindrom. Here is the code:

```   1 def isPalindrome(s: String) = {
2    val incr =  s.length % 2
3    s.substring(0, s.length/2) ==
4        s.substring(incr + s.length/2).reverse
5 }
```
```
```
```Note the use of incr that has value either 0 or 1. It is intended to handle the case where the length of the string is odd.

Then, a little analysis.

The product of two 3-digit numbers has 5 or 6 digits. Assume that we will find the largets palindrome as 6 digit number.. The number then  will be in the form of 'abccba' with the following property: The largest palindrom =

100000 a + 10000 b + 1000 c + 100 c + 10 b + a = 10 0001 a + 10010 b + 1100 cwhich is a multiply of 11. So, one of the 3 digit number will then multiply of 11. This information can be used to reudce the brute force nature of the search. The largest multiply of 11 is 11 * 90 = 990. The search then starts from 990, followed by 979, and subsequent mutliply 11 until 11 * 9 that is no longer 3 digit number. The multiply 11 number is then multiplied by all 3 digit numbers. To optimize further, we take advantage of the iteration nature that goes down from the largest multiply 11 until 99. If  we have a maximum number  xi * y, the product of xii < xi with z can only be larger than xi * y if z > y. This allows us to stop earlier.

The code is the following. Note the annotation tailrec that asks the compiler to check if the method is tail recursive.

1 @tailrec
2 def getLargestPalindrome(
3     x : Int, y : Int,
4     max: Int, xMax:Int, yMax: Int) : Int  = {
5   if ( x * 11 < 100) {
6      max
7    } else {
8        val mul = x * 11 * y
9
10        if ( mul > max ) {
11           if (isPalindrome(mul.toString))
12              getLargestPalindrome(x - 1, 999, mul, x, y )
13            else
14              getLargestPalindrome(x, y -1, max, xMax, yMax)
15        }
16        else {
17            getLargestPalindrome(x - 1, 999, max, xMax, yMax)
18        }
19    }
20 }
When executed, the largest palindrom is indeed 6 digits, so the algorithms above are applied.
What's xMax and yMax for ? It's the two 3 digit numbers. ```