[2009.02.23] Project Euler: Problem 4

Project Euler in F#!

Project Euler: Problem 4

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

Example

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Solution

I seriously don't like how I came about with this solution and I think to myself that it is the worst of them out there. I suppose not knowing every single operator or trick in F# results in coding like this.

The idea behind this was that once I found a product, I needed to test if it was a palindrome. I even thought about trying out regular expressions but I felt more comfortable with this approach although it is a bit more verbose than I had hoped for. So I converted each product to a string and further broke the String down to a character array since I could then use the Array.rev function to reverse the members of an array.

So the formula here is to calculate the produce, convert it to a string, get the reverse of the string and compare the two for equality. Note that F# has built in support for reverse for loops using the downto keyword. Also, the problem asked specifically for 3-digit computations, so I figured out that the best best was the try all products in the range of 900-999 first, then go lower if need be.

    1 #light

    2 #r "FSharp.PowerPack.dll"

    3 

    4 // function to reverse a string

    5 let reverseString (num: int) =

    6     // convert to a string, then to char array,

    7     //  then call Array.rev

    8     let charArray =

    9         Array.rev ((num.ToString()).ToCharArray())

   10     let mutable str = ""

   11     // loop through each character in

   12     //  the char array and add each to an

   13     //  empty string

   14     for i = 0 to charArray.Length - 1 do

   15         let value = string charArray.[i]

   16         str <- str + value

   17     str // return reversed string

   18 

   19 let palindrome (p: int) =

   20     // create emtpty string to hold results

   21     let mutable res = "" 

   22     for i = p downto 900 do

   23         for j = p downto 900 do

   24             let num = i * j

   25             let numToStr = num.ToString()

   26             let revString = reverseString num

   27             if (revString = numToStr) then

   28                 printfn "------%d, %d" i j

   29                 res <- numToStr 

   30     res // this will not return the correct result

   31     // need to use the command window and get the

   32     // first i,j pair

   33 // the result is: 993 * 913 = 906609