Project Euler problem number 4 asks the following:

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.

Here follows my solution:

#light open System let rec is_palindromic (a:string) = let length = a.Length; match a with | "" -> true | x -> match length with | 1 -> true | _ -> x.[0] = x.[length-1] && is_palindromic (x.Substring(1,(length - 2))) let max_palindrome = let numbers = seq { for i in 100 .. 999 do for j in 100 .. 999 do if is_palindromic(Convert.ToString(i*j)) then yield (i*j) } Seq.max numbers

A few considerations:

- I first define a general recursive function to determine whether a given string is a palindrome.
I basically check the first and last characters of the string; if they are the same I continue with the second and second last, and so on until I either found a pair of chars that do not match or there’s only one char or none left.

Alternatively, I could have reversed the string and compared the original and reversed strings for equality; however that would have been not just more work than actually needed by the algorithm, but less useful as an excercise in learning F#.

- The actual algorithm uses brute force to test for palindromicity (neologism?) all the numbers that can be composed multiplying together 3 digits numbers (those from 100 to 999), picking the highest one. Again, as in a previous problem, I am using comprehension to generate a list of candidates.

Pingback: DotNetShoutout

Pingback: Rick Minerich's Development Wonderland : F# Discoveries This Week 08/08/2010