Geeks With Blogs
Mark Pearl

 

Another day flown by… another Euler problem to tease me… today I attempted problem 9.

The Problem

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which a^2 + b^2 = c^2

For example, 3^2 + 4^2 = 9 +16 = 25 = 5^2.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

The Solution

Initially I thought I would try and tackle this problem by setting up 3DArrays in F#, thus my question on StackOverflow regarding 2D Array.

However, if I used the arrays I would not be able to use the handy Seq methods. After some more thinking, I decided to use tuples instead and generate the permutations using the Seq.unfold method.

let generatePossibleCandidates =  
          (1,1) 
          |> Seq.unfold(fun (x,y) ->                                
                let z = TargetResult - (x+y)
                let xyz = x*y*z
                if (y>TargetResult) then None                
                else if (x>=y-1) then Some((Square(x),Square(y),Square(z),xyz), (1,y+1))
                else Some((Square(x),Square(y),Square(z),xyz), (x+1,y))                
          )

 

I must be honest I am not to happy with the formatting of this code… it looks a bit clunky and messy… but it did the trick for now. Once I had all possible permutations generated, filtering the result was relatively simple.

let FilterCandidates data = 
    data |> Seq.filter(fun (x,y,z,r) -> (x+y=z))    
         |> Seq.filter(fun (x,y,z,r) -> (x<y) && (y<z))    
         |> Seq.iter(fun x -> 
            let (a,b,c,d) = x            
            printfn "%f" (Math.Sqrt(a|>float)) 
            printfn "%f" (Math.Sqrt(b|>float))
            printfn "%f" (Math.Sqrt(c|>float))
            printfn "%d" d
            ()
          )

The entire solution looked like this…

open System

let TargetResult = 1000
let Square x = x*x

///
/// Generate all permutations, by producing squares of x & y with z being the 
/// targetresult - the sum of x & y
///
let generatePossibleCandidates =  
          (1,1) 
          |> Seq.unfold(fun (x,y) ->                                
                let z = TargetResult - (x+y)
                let xyz = x*y*z
                if (y>TargetResult) then None                
                else if (x>=y-1) then Some((Square(x),Square(y),Square(z),xyz), (1,y+1))
                else Some((Square(x),Square(y),Square(z),xyz), (x+1,y))                
          )

///
/// Filter permutation by reducing the collection by the
/// problem criteria.
///
let FilterCandidates data = 
    data |> Seq.filter(fun (x,y,z,r) -> (x+y=z))    
         |> Seq.filter(fun (x,y,z,r) -> (x<y) && (y<z))    
         |> Seq.iter(fun x -> 
            let (a,b,c,d) = x            
            printfn "%f" (Math.Sqrt(a|>float)) 
            printfn "%f" (Math.Sqrt(b|>float))
            printfn "%f" (Math.Sqrt(c|>float))
            printfn "%d" d
            ()
          )

FilterCandidates generatePossibleCandidates

I understand that there are some algebraic approaches to solving this problem, but I found the brute force approach to be performant enough for me not to worry about it any further….

Posted on Tuesday, July 27, 2010 5:20 PM F# | Back to top


Comments on this post: F# - Euler Problem 9

# re: F# Euler Problem 9
Requesting Gravatar...
Here's how I solved that problem...

seq { 1..500 }
|> Seq.map (fun a -> seq { a..500 } |> Seq.map (fun b -> (a,b,1000-a-b)))
|> Seq.concat
|> Seq.filter (fun (a,b,c) -> a * a + b * b = c * c)
|> Seq.head
|> fun (a,b,c) -> a * b * c
Left by Joel on Jul 30, 2010 11:02 PM

# re: F# - Euler Problem 9
Requesting Gravatar...
Joel... love the approach - thanks for the input
Left by MarkPearl on Aug 10, 2010 8:41 PM

Your comment:
 (will show your gravatar)


Copyright © MarkPearl | Powered by: GeeksWithBlogs.net