New beginnings on Project Euler and F# – Problem 1

Very nice. I recently did a complete re-install together with an upgrade to Windows 7.

I have backups of everything and even backups of backups, do no problems there….I thought.

It seems I had backups of everything except my ProjectEuler source code…bugger.

Lets recreate all source code I had, starting simple 🙂

 

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

let Problem1a =
   let SoT = [3..3..999]
   let SoF = [5..5..999]
   List.append SoT SoF
   |> Seq.ofList
   |> Seq.distinct
   |> Seq.fold (+) 0

Which amount to :

  1. create a list of multiples of three
  2. create a list of multiples of 5
  3. Combine both into one list
  4. Create a Sequence out of this list
  5. Create a Sequence with only distinct numbers
  6. Sum all items in the sequence

Nice, but why start with two lists? Lets start with one list with all numbers 0 to 999:

let Problem1b bound =
  [0..bound]
  |> List.filter (fun x -> x%3=0 || x%5=0)
  |> List.sum
  1. Create a list of all numbers from 0 to 999
  2. filter out any number not divisible by 3 or 5
  3. sum the remaining numbers

Using Fold we can devise any function by which to fold a list in to it self so to speak. Why not fold the complete list summing only numbers divisible by 3 or 5:

let Problem1c bound =
  [0..bound]
  |> List.fold (fun s x -> match x with | n when n%3=0 || n%5=0 -> s+x | _ -> s) 0
  1. Create  a list of numbers from 0 to 999
  2. Fold summing all numbers divisible by 3 or 5

So which is fastest? (measurement of only one run)

Problem 1a : 00.0101217 sec
Problem 1b : 00.0038361 sec
Problem 1c : 00.0025146 sec


Geef een reactie

Deze website gebruikt Akismet om spam te verminderen. Bekijk hoe je reactie-gegevens worden verwerkt.