CODEWITHSUNDEEP
performancealgorithmf#
Algamest
Algamest

Reputation: 1529

Optimising F# answer for Euler #4

I have recently begun learning F#. Hoping to use it to perform any mathematically heavy algorithms in C# applications and to broaden my knowledge

I have so far avoided StackOverflow as I didn't want to see the answer to this until I came to one myself.

I want to be able to write very efficient F# code, focused on performance and then maybe in other ways, such as writing in F# concisely (number of lines etc.).

Project Euler Question 4:

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.

My Answer:

let IsPalindrome (x:int) = if x.ToString().ToCharArray() = Array.rev(x.ToString().ToCharArray()) then x else 0

let euler4 = [for i in [100..999] do
            for j in [i..999] do yield i*j]
                |> Seq.filter(fun x -> x = IsPalindrome(x)) |> Seq.max |> printf "Largest product of two 3-digit numbers is %d"

I tried using option and returning Some(x) and None in IsPalindrome but kept getting compiling errors as I was passing in an int and returning int option. I got a NullRefenceException trying to return None.Value. Instead I return 0 if the number isn't a palindrome, these 0's go into the Sequence, unfortunately.

Maybe I could order the sequence and then get the top value? instead of using Seq.Max? Or filter out results > 1?

Would this be better? Any advice would be much appreciated, even if it's general F# advice.

Upvotes: 0

Views: 360

Answers (6)

ildjarn
ildjarn

Reputation: 62975

Efficiency being a primary concern, using string allocation/manipulation to find a numeric palindrome seems misguided – here's my approach:

module NumericLiteralG =
    let inline FromZero () = LanguagePrimitives.GenericZero
    let inline FromOne () = LanguagePrimitives.GenericOne

module Euler =
    let inline isNumPalindrome number =
        let ten = 1G + 1G + 1G + 1G + 1G + 1G + 1G + 1G + 1G + 1G
        let hundred = ten * ten
        let rec findHighDiv div =
            let div' = div * ten
            if number / div' = 0G then div else findHighDiv div'
        let rec impl n div =
            div = 0G || n / div = n % ten && impl (n % div / ten) (div / hundred)
        findHighDiv 1G |> impl number

    let problem004 () =
        { 100 .. 999 }
        |> Seq.collect (fun n -> Seq.init (1000 - n) ((+) n >> (*) n))
        |> Seq.filter isNumPalindrome
        |> Seq.max

Upvotes: 4

Dima_
Dima_

Reputation: 81

Optimized version:

let Euler dgt=
  let [mine;maxe]=[dgt-1;dgt]|>List.map (fun x->String.replicate x "9"|>int)
  let IsPalindrom (str:string)=
    let rec fn(a,b)=a>b||str.[a]=str.[b]&&fn(a+1,b-1)
    fn(0,str.Length-1)
  let IsIntPalindrome = (string>>IsPalindrom)
  let rec fn=function
    |x,y,max,a,_ when a=mine->x,y,max
    |x,y,max,a,b when b=mine->fn(x,y,max,a-1,maxe)
    |x,y,max,a,b->a*b|>function
                   |m when b=maxe&&m<max->x,y,max
                   |m when m>max&&IsIntPalindrome(m)->fn(a,b,m,a-1,maxe)
                   |m when m>max->fn(x,y,max,a,b-1)
                   |_->fn(x,y,max,a-1,maxe)
  fn(0,0,0,maxe,maxe)

Log (switch #time on):

> Euler 2;;
Real: 00:00:00.004, CPU: 00:00:00.015, GC gen0: 0, gen1: 0, gen2: 0
val it : int * int * int = (99, 91, 9009)
> Euler 3;;
Real: 00:00:00.004, CPU: 00:00:00.015, GC gen0: 0, gen1: 0, gen2: 0
val it : int * int * int = (993, 913, 906609)
> Euler 4;;
Real: 00:00:00.002, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : int * int * int = (9999, 9901, 99000099)
> Euler 5;;
Real: 00:00:00.702, CPU: 00:00:00.686, GC gen0: 108, gen1: 1, gen2: 0
val it : int * int * int = (99793, 99041, 1293663921) //int32 overflow

Extern to BigInteger:

let Euler dgt=
  let [mine;maxe]=[dgt-1;dgt]|>List.map (fun x->new System.Numerics.BigInteger(String.replicate x "9"|>int))
  let IsPalindrom (str:string)=
    let rec fn(a,b)=a>b||str.[a]=str.[b]&&fn(a+1,b-1)
    fn(0,str.Length-1)
  let IsIntPalindrome = (string>>IsPalindrom)
  let rec fn=function
    |x,y,max,a,_ when a=mine->x,y,max
    |x,y,max,a,b when b=mine->fn(x,y,max,a-1I,maxe)
    |x,y,max,a,b->a*b|>function
                   |m when b=maxe&&m<max->x,y,max
                   |m when m>max&&IsIntPalindrome(m)->fn(a,b,m,a-1I,maxe)
                   |m when m>max->fn(x,y,max,a,b-1I)
                   |_->fn(x,y,max,a-1I,maxe)
  fn(0I,0I,0I,maxe,maxe)

Check:

Euler 5;;
Real: 00:00:02.658, CPU: 00:00:02.605, GC gen0: 592, gen1: 1, gen2: 0
val it :
  System.Numerics.BigInteger * System.Numerics.BigInteger *
  System.Numerics.BigInteger =
  (99979 {...}, 99681 {...}, 9966006699 {...})

Upvotes: 0

Dima_
Dima_

Reputation: 81

let IsPalindrom (str:string)=
  let rec fn(a,b)=a>b||str.[a]=str.[b]&&fn(a+1,b-1)
  fn(0,str.Length-1)
let IsIntPalindrome = (string>>IsPalindrom)
let sq={100..999}
sq|>Seq.map (fun x->sq|>Seq.map (fun y->(x,y),x*y))
  |>Seq.concat|>Seq.filter (snd>>IsIntPalindrome)|>Seq.maxBy (snd)

Upvotes: 1

Luka Rahne
Luka Rahne

Reputation: 10457

  • simplest way is to go from 999 to 100, because is much likley to be product of two large numbers.
  • j can then start from i because other way around was already tested
  • other optimisations would go in directions where multiplactions would go descending order, but that makes everything little more difficult. In general it is expressed as list mergeing.

Haskell (my best try in functional programming)

merge f x [] = x
merge f [] y = y
merge f (x:xs) (y:ys)
               | f x y     =  x : merge f xs     (y:ys) 
               | otherwise =  y : merge f (x:xs)   ys 

compare_tuples (a,b) (c,d) = a*b >= c*d

gen_mul n = (n,n) : merge compare_tuples 
                         ( gen_mul (n-1) ) 
                         ( map (\x -> (n,x)) [n-1,n-2 .. 1] )

is_product_palindrome (a,b) = x == reverse x where x = show (a*b)

main = print $ take 10 $  map ( \(a,b)->(a,b,a*b) ) 
   $ filter is_product_palindrome $  gen_mul 9999

output (less than 1s)- first 10 palindromes => 

[(9999,9901,99000099),
 (9967,9867,98344389),
 (9999,9811,98100189),
 (9999,9721,97200279),
 (9999,9631,96300369),
 (9999,9541,95400459),
 (9999,9451,94500549),
 (9767,9647,94222249),
 (9867,9547,94200249),
 (9999,9361,93600639)]

One can see that this sequence is lazy generated from large to small

Upvotes: 0

Daniel
Daniel

Reputation: 47904

Here's one way to do it:

/// handy extension for reversing a string
type System.String with
    member s.Reverse() = String(Array.rev (s.ToCharArray()))

let isPalindrome x = let s = string x in s = s.Reverse()

seq {
    for i in 100..999 do
    for j in   i..999 -> i * j
}
|> Seq.filter isPalindrome
|> Seq.max
|> printfn "The answer is: %d"

Upvotes: 3

Alexan
Alexan

Reputation: 8637

just my solution:

let isPalin x =
    x.ToString() = new string(Array.rev (x.ToString().ToCharArray()))
let isGood num seq1 = Seq.exists (fun elem -> (num % elem = 0 && (num / elem) < 999)) seq1
{998001 .. -1 .. 10000} |> Seq.filter(fun x -> isPalin x) |> Seq.filter(fun x -> isGood x {999 .. -1 .. 100}) |> Seq.nth 0

Upvotes: 0

Related Questions