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:

http://projecteuler.net/index.php?section=problems&id=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 c
which 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.