Project Euler Problem 4 in F#

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.

See all Project Euler problems solutions.

kick it on DotNetKicks.com

Shout it

This entry was posted in .NET, F# and tagged , , . Bookmark the permalink.
  • Pingback: DotNetShoutout

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

  • Javaman59

    Nearly the same as mine, but I think I can improve the F# idiom a bit…

    I’ll do the palindrome test on an array of chars. Then the pattern matching is more elegant…

    let rec isPalindrome chars =
    match chars with
    | [||] | [|_|] -> true
    | _ -> (chars.[0] = chars.[chars.Length - 1]) &&
    (isPalindrome chars.[1..chars.Length - 2])

    (actually, it’s a generic ‘T array)

    And the main part is a little more elegant with a pipe…

    let Problem4 =
    seq { for i in 1..999 do
    for j in 1..999 do
    if isPalindrome ((i*j).ToString().ToCharArray()) then
    yield i*j }
    |> Seq.max

  • stefanoricciardi

    Javaman59,

    thank you for stepping by. Yes, your solutions is a bit more elegant and idiomatic.

    Hope to see you again here.

    Stefano