Its been a while but F# and Project Euler have been on my mind of late. Problem four plays with palindromes.

Find the largest palindrome made from the product of two 3-digit numbers.

What I like about this question is that we can still break out the math and improve on the obvious brute force method. For instance the palindrome we are after can be written as ABCCBA which can be simplified thusly:

100000a + 10000b + 1000c + 100c + 10b + a

= 100001a + 10010b + 1100c

By finding the lowest common factor for a, b & c we can prove our palindrome must be divisible by that factor. In this case, it happens to be:

11(9091a + 910b + 100c)

So our palindrome must be divisible by 11.

Armed with this knowledge we can hunt for numbers divisible by 11 that are between 100000 and 998001 that are palindromic and choose the biggest one. Using F# we can take advantage of list comprehension, lambdas and some great built in functionality.

In this case I want a list of products of 11 that will match the pattern ABCCBA. This means I can ignore integers below 100 as factors since 99*99=9801 and doesn't fit the ABCCBA pattern. In F# this can be achieved like this:

let products = [ for x in 110 .. 11 .. 999 do for y in 100 .. 999 -> x * y ]

In this example we are taking the multiples of 11 between 110 and 999 and assigning it to x, and then assigning y a number between 100 and 999 and then yielding the product of x and y.

The next trick we need is to be able to check if a number is palindromic. The .NET framework has no real built in for this, but we can use the F# Array class to reverse arrays. Lucky us, because the String class implements seq<char>. That is to say in F# we can treat strings as sequences of chars and indirectly as Arrays:

let reverse_string (s:string) = 
    new string(s |> Seq.to_array |> Array.rev)

Using a function like this we could compare the original string with the reverse to tell if it is indeed a palindrome. Finally we can use List.max to choose the max value of a list.

Putting these techniques together makes for an elegant solution:

#light

let solve() =  
   [ for x in 110 .. 11 .. 999 do for y in 100 .. 999 -> x * y ] 
   |> List.filter (fun x -> x.ToString() = new string( x.ToString() |> Seq.to_array |> Array.rev )) 
   |> List.max

In the above code I hope you can see how I'm using the string reversal code in a lambda expression to filter the non-palindromic numbers out of the list. Once I've done that List.max outputs the final answer. On my dev box, this runs in under 2 tenths of a second. Not bad... Hopefully I'll get some time to compare a similar C# solution. I'll bet C# is faster, but I won't be solving this problem in 4 readable lines...

Oh...and if you can see a more optimal approach please share!