Sunday, July 6, 2008

[2008.07.06] Project Euler: Problem 1

My goal in this series is to use Functional Programming, namely F# to solve the problems given by Project Euler. As previously stated, I am in the process of learning F# and I thought this would be a good way to illustrate my progress.

Project Euler: Problem 1

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

Example

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Solution 1

This is the long version where everything is nicely laid out and annotated:
NOTE: I will leave running and getting the results to you.

    1 #light

    2 // Name: Sparky Dasrath

    3 // Date: 2008.07.06

    4 // Code: Project Euler: Problem 1 - Solution 1

    5

    6 // create a function sumNumbers that take on argument, n,

    7 //  which represents the upper limit on the numbers we

    8 //  want to sum

    9 //  n = 999 for this problem

   10 let sumNumbers n =

   11     // generate a list of numbers using

   12     //  Sequence Expression,in the

   13     //  input, n, that are multiples of

   14     //  three, five and fifteen 

   15     let multOfThree   = {for x in 1 .. n when x%3=0 -> x}

   16     let multOfFive    = {for x in 1 .. n when x%5=0 -> x}

   17     let multOfFifteen = {for x in 1 .. n when x%15=0 -> x}

   18

   19     // combine the sequences of multiples of 3 and 5

   20     let firstGroup = Seq.append multOfThree multOfFive

   21

   22     // convert the sequence to an array to take advantage

   23     //  of some of array's built in functionality

   24     let arr1 = Seq.to_array firstGroup

   25

   26     // now convert the multiples of 15 to an array

   27     let arr2 = Seq.to_array multOfFifteen

   28

   29     // use the Sum function of array to add

   30     //  members of the array

   31     let sumOfThreeFive = Array.sumByInt (fun a -> a) arr1

   32     let sumOfFifteen   = Array.sumByInt (fun a -> a) arr2

   33

   34     // return the difference between the two array sums

   35     (sumOfThreeFive-sumOfFifteen)

Solution 2

Here is a much simplified version of the solution.

    1 #light

    2 // Name: Sparky Dasrath

    3 // Date: 2008.07.06

    4 // Code: Project Euler: Problem 1 - Solution 2

    5 // this is a much shorter version using

    6 //  lists instead of sequences

    7 // here using List Expressions two lists

    8 //  are created and appended, then the

    9 //  new list is converted to an array

   10 //  and the items summed

   11 // another list with multiples of 15

   12 //  is subtracted from the previous

   13 //  list

   14 (Array.sumByInt

   15     (fun x -> x)

   16     (List.to_array

   17         ([0 .. 3 .. 999]@[0 .. 5 .. 999]))) -

   18 (Array.sumByInt (fun x-> x) [|0 .. 15 .. 999|])

Solution 3

Even more simplified!

    1 #light

    2 // Name: Sparky Dasrath

    3 // Date: 2008.07.06

    4 // Code: Project Euler: Problem 1 - Solution 3

    5 

    6 // this version avoids using the second

    7 //  list of multiples of 15

    8 // the Set operator actually strips out

    9 //  any duplicate values after the lists

   10 //  are combined and the pipeline

   11 //  operator, |> lets you feed values

   12 //  to a function

   13 let a = [0..3..999]@[0..5..999]

   14 Set.of_list a |> Set.to_array |> Array.sumByInt (fun x->x)

2 comments:

Nitin R.K. said...

Hi Dasrath!

How do you get the line numbers and the formatting for the code that you've pasted on your blog post? Did you have to modify the CSS for the template or did you define it within the HTML of the post?

-Nitin

Sparky said...

Nitin, I figured others may have the same questions, so I did a post explaining how I got things to look how I want them. Hope it helps.
~sparky D