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