Saturday, May 8, 2010

Problem 1: Add all the natural numbers below one thousand that are multiples of 3 or 5.

Solutions (a)-(c) take the same approach but use different Seq function applications. Every integer from 1 to 999 is tested.

let problem1a =
    {1..999}
    |> Seq.filter (fun i -> i % 3 = 0 || i % 5 = 0)
    |> Seq.sum

let problem1b =
    {1..999}
    |> Seq.fold (fun acc i -> if i % 3 = 0 || i % 5 = 0 then acc + i else acc) 0
    
let problem1c =    
    {1..999}
    |> Seq.sumBy (fun i -> if i % 3 = 0 || i % 5 = 0 then i else 0)

Solution (d) uses inclusion/exclusion instead of an exhaustive search.

let problem1d = 
    let a = Seq.append {0..3..999} {0..5..999} |> Seq.sum
    let b = {0..15..999} |> Seq.sum
    a - b    

I like solution (a) the best since it's the clearest.

1 comment:

  1. Yes, solution (a) wins on clarity, but (b) wins on raw speed.

    In theory, (c) should run as fast as (b), for one would expect sumBy to do exactly the same thing behind the scenes as one's own fold addition, but on my computer it always takes 2ms instead of 1ms.

    Solution (d) is the slowest, but it's certainly a clever variation on a theme. It would get really unwieldy with more than two factors!

    ReplyDelete