The last few days I began to play around with problem 4 of Euler. I really enjoyed this problem since it dealt with a few functions in F# that I haven’t dealt with in the past.

__Problem__

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.

__Solution__

So I divided the problem up into a few functions…

reverseString simply reverses a string.

isPalindrome converts a number to a string and compares the number forwards to the number in reverse.

ProductOfNumbers is the interesting one for me – basically with my initial attempt I just generated a series of numbers and their product. The issue I was having with this approach was that it is the brute force approach, and I could not rely on the first or last palindrome to be the largest palindrome. To solve the second area of my problem I added an additional field to my solution Tuple which was the sum of x & y, because the largest sum of x & Y will result in the largest product of x & Y

let ProductOfNumbers num minnum = (num, num) |> Seq.unfold(fun(x,y)-> match y with | y when y < minnum -> None | y when y = x -> Some((x*y,x,y,x+y), (num,y-1)) | _ -> Some((x*y,x,y,x+y), (x-1,y)) ) |> Seq.sortBy(fun x -> let _,_,_,key = x -key)

Finally in the res function I filter my results so that I only have palindromes and get the first one, which will be the largest one.

let res = // // Generate tuple combinations // ProductOfNumbers 999 100 // // Filter out only palidromes // |> Seq.filter(fun x -> let a,_,_,_ = x isPalidrome a) // // Display the results // |> Seq.head |> fun x -> let a,b,c,d = x Console.WriteLine(a.ToString() + " = " + b.ToString() + " x " + c.ToString())

__Whole Solution__

open System let reverseString (s:string) = new string(s |> Seq.toArray |> Array.rev) let isPalidrome (x:int) = x.ToString() = reverseString(x.ToString()) let ProductOfNumbers num minnum = (num, num) |> Seq.unfold(fun(x,y)-> match y with | y when y < minnum -> None | y when y = x -> Some((x*y,x,y,x+y), (num,y-1)) | _ -> Some((x*y,x,y,x+y), (x-1,y)) ) |> Seq.sortBy(fun x -> let _,_,_,key = x -key) let res = // // Generate tuple combinations // ProductOfNumbers 999 100 // // Filter out only palidromes // |> Seq.filter(fun x -> let a,_,_,_ = x isPalidrome a) // // Display the results // |> Seq.head |> fun x -> let a,b,c,d = x Console.WriteLine(a.ToString() + " = " + b.ToString() + " x " + c.ToString()) res Console.ReadLine()

__Conclusion__

So I am aware that this does get the correct result, however I would be interested in looking at other approaches to solving this problem in F#. Any feedback / suggestions would be much appreciated.

Posted on Thursday, June 24, 2010 7:02 PM F# | Back to top
Your comment:
Title:
Name:
Comment: *Allowed tags: blockquote, a, strong, em, p, u, strike, super, sub, code*
Verification:
var RecaptchaOptions = {
theme : 'white',
tabindex : 0
};

Why sort by sum descending when you've already got the product? Just sort by product descending instead... (Also, it's not true that the largest sum must necessarily correspond to the largest product: compare 100 + 1 vs. 50 + 50).

In the places where you have patterns like fun x -> let a,b,c,d = x in ..., you could just write fun (a,b,c,d) -> ... instead and save yourself a meaningless identifier.

Favor printfn over Console.WriteLine - it's more idiomatic, concise, and typesafe.

There doesn't seem to be any point to your res binding, since the it is of type unit.

Here's what I would have done:

seq {

for x in 100 .. 999 do

for y in x .. 999 do

yield x,y,x*y}

|> Seq.sortBy (fun (_,_,p) -> -p)

|> Seq.filter (fun (_,_,p) -> isPalindrome p)

|> Seq.head

|> fun (x,y,p) -> printfn "%d = %d x %d" p x y

let problem4 =

let isPalindrome x =

let xstr = string x

xstr = new string(xstr.ToCharArray() |> Array.rev)

seq { 999..-1..100 }

|> Seq.map (fun x -> seq { 999..-1..x } |> Seq.map ((*) x) |> Seq.filter isPalindrome)

|> Seq.concat

|> Seq.max

Can anyone else confirm what Joel is saying that s.ToCharArray will be faster than s |> Seq.toArray? Would love to know...

Great solution though - what I am really loving about F# is how concise everything is... very little code bloat for problems like these!

seq { for a in 100..999 do for b in a..999 -> a * b } |> Seq.filter (fun n -> let s = n.ToString() |> List.ofSeq in s = List.rev s) |> Seq.max

Here's my benchmark. It times the application of a string->string function one million times, reusing the same test data between function calls to keep things fair:

let test =

let R = System.Random()

let data = [for _ in 1..1000000 -> R.Next() |> string]

fun (f:string -> string) -> for s in data do f s |> ignore

And the test candidates:

let rev1 (s:string) = System.String(s.ToCharArray() |> Array.rev)

let rev2 (s:string) = System.String(s |> Seq.toArray |> Array.rev)

Result: test rev1 [0.19s], test rev2 [0.67s].

I like project Euler problems kicking my behind as well. Solving those problems has taught me a lot about thinking like a functional programmer. Seeing others' solutions (and trying to understand them) is also very rewarding.

By the way, I solved the problem reversing integers as integers, like this:

let rec reverse n =

let rec aux acc = function

| n when n<0 -> -(reverse -n) //or raise an error here

| 0 -> acc

| n -> aux ((n%10) + 10*acc) (n/10)

aux 0 n

let ispalindrome n = reverse n = n