Friday, June 11, 2010

Problem 33: Discover all the fractions with an unorthodox cancelling method.

With F#, there are two ways to solve this: the easy way, and the slightly easier way.  The first way, we’ll work entirely with integers, including an implementation of gcd using the Euclid’s algorithm for reducing our final fraction.

gcd and accompanying abs are a sure candidates for inclusion in our Numerics module.

let inline abs (g:G<'a>) n = 
    if n < g.zero then n*g.negone else n
    
let inline gcd (g:G<'a>) n m =
    if n = g.zero || m = g.zero then 
        raise (System.ArgumentOutOfRangeException("n and m must non-zero"))
    else
        let rec gcd n m = 
            if n = m then n
            else
                if n > m then gcd (n-m) m
                else gcd n (m-n)
        gcd (abs g n) (abs g m)

And then our solution is fairly straightforward:

let problem33a =
    let unorthodoxPairs =
        [for numer = 10 to 99 do
            for denom = (numer+1) to 99 do
                let reduced = (numer |> float)/(denom |> float)
                let digitPair n = //decompose digit list of n into a pair
                    let nDigits = n |> string |> Seq.map (string >> float) |> Seq.toArray
                    (nDigits.[0], nDigits.[1])
                let (a,b) = digitPair numer
                let (c,d) = digitPair denom
                let isUnorthodox w x y z = (w/x) = 1. && (y/z) = reduced
                if isUnorthodox a c b d || 
                   isUnorthodox a d b c || 
                   isUnorthodox b d a c || 
                   isUnorthodox b c a d then yield (numer, denom)]
    
    let product = unorthodoxPairs |> List.fold (fun (w,x) (y,z) -> (w*y,x*z)) (1,1)
    snd product / (gcd (fst product) (snd product)) 

Next is our very easy solution which takes advantage of BigRational included in the F# PowerPack:

let problem33b =
    let unorthodoxPairs =
        [for numer = 10 to 99 do
            for denom = (numer+1) to 99 do
                let reduced = (numer |> float)/(denom |> float)
                let digitPair n = //decompose digit list of n into a pair
                    let nDigits = n |> string |> Seq.map (string >> float) |> Seq.toArray
                    (nDigits.[0], nDigits.[1])
                let (a,b) = digitPair numer
                let (c,d) = digitPair denom
                let isUnorthodox w x y z = (w/x) = 1. && (y/z) = reduced
                if isUnorthodox a c b d || 
                   isUnorthodox a d b c || 
                   isUnorthodox b d a c || 
                   isUnorthodox b c a d then yield BigRational.Parse(sprintf "%d/%d" numer denom)]
    
    let product = unorthodoxPairs |> List.fold (*) 1N
    product.Denominator

Here’s a third version which avoids string parsing and the need for conversions between int and float:

let problem33c =
    let unorthodoxPairs =
        [for numer = 10. to 99. do
            for denom = (numer+1.) to 99. do                
                let digitPair n =
                    let tensPlace = System.Math.Truncate(n/10.)
                    (tensPlace, n-tensPlace*10.)    

                let (a,b) = digitPair numer
                let (c,d) = digitPair denom

                let isUnorthodox w x y z = (w/x) = 1. && (y/z) = numer/denom
                if isUnorthodox a c b d || 
                   isUnorthodox a d b c || 
                   isUnorthodox b d a c || 
                   isUnorthodox b c a d then yield BigRational.Parse(sprintf "%.0f/%.0f" numer denom)]
    
    let product = unorthodoxPairs |> List.fold (*) 1N
    product.Denominator

No comments:

Post a Comment