Geeks With Blogs
Mark Pearl

 

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


Comments on this post: F# - Euler Problem 4

# re: F# Euler Problem 4
Requesting Gravatar...
Some comments:

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
Left by Keith on Jun 24, 2010 7:56 PM

# re: F# Euler Problem 4
Requesting Gravatar...
Thanks Keith... great feedback!
Left by Mark Pearl on Jun 24, 2010 8:04 PM

# re: F# Euler Problem 4
Requesting Gravatar...
I think that s.ToCharArray() is going to be slightly faster than s |> Seq.toArray, since it just returns the internal data of the string instead of looping through it to build a new array. That said, here's now I solved this one:

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
Left by Joel on Jun 24, 2010 8:50 PM

# re: F# Euler Problem 4
Requesting Gravatar...
Thanks Joel -

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!
Left by MarkPearl on Jun 24, 2010 9:13 PM

# re: F# Euler Problem 4
Requesting Gravatar...
The Euler problems are great! Inefficient of course, but fun to go for tiny brute force:

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
Left by Monkey on Jun 24, 2010 10:52 PM

# re: F# Euler Problem 4
Requesting Gravatar...
Joel's right. The .ToCharArray() approach is almost 3.5 times as fast on my machine, because it avoids walking along an iterator, which happens in all Seq.something operations.

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
Left by Arjen on Jun 25, 2010 11:12 AM

# re: F# Euler Problem 4
Requesting Gravatar...
Ever the contrarian, I solved this one by first generating the palindromes and then testing them.
Left by TechNeilogy on Jun 25, 2010 4:54 PM

Your comment:
 (will show your gravatar)


Copyright © MarkPearl | Powered by: GeeksWithBlogs.net