Functional Practice: Euler Problem #1

I've learned about Euler problems quite a while back. If you're not familiar with them, you can check out Project Euler.

These are very mathematically focused problems, and I was thinking about using them as practice problems for C#. Many people have done that; here's one example: http://www.mathblog.dk/project-euler-solutions/.

When I was looking at the problems, though, I always felt that my C# solutions would be a bit of a mess -- lots of if/else, while, switch, and so on. The solution is not functional or elegant (which always makes me think of this song).

But these seem like a great place to start using functional programming. Since I'm learning functional programming with Haskell, that's the language I'll use for my solutions.

Now, I'm not going to blog about all of the Euler problems (there are a lot of solutions out there). I'm just going to go over my thinking to solve the first problem. This will show how learning about functional programming will let you start to think a bit differently if you come from the OO world.

Euler Problem #1
Here's the first problem:

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. Find the sum of all the multiples of 3 or 5 below 1000.

This doesn't sound that hard. We'll start by trying to replicate the sample: the natural numbers below 10.

Thinking Functionally
What I found myself doing immediately was breaking this problem down into different parts. We need the natural numbers below a certain value. We need to find the ones that are multiples of 3. We need to find the ones that are multiples of 5. We need to sum things up.

This is a great place to use a list in Haskell.

First, let's get a list of all the natural numbers less than 10. We'll use a list comprehension with a range:

[x | x <- [1..9]]

And here's the output

[1,2,3,4,5,6,7,8,9]

That's a good start.  Now we need to filter things a bit. Let's add the modulo function (mod) to get the values evenly divisible by 3:

[x | x <- [1..9], mod x 3 == 0]

 The "mod" function takes 2 parameters. This may look a little strange, so we'll change this to use infix notation by using a backtick around the function name:

[x | x <- [1..9], x `mod` 3 == 0]

This seems a little less strange. And here's the output:

[3,6,9]

And since we want multiples of 5 along with multiples of 3, we can "or" these together with "||". Here's how that looks:

[x | x <- [1..9], x `mod` 3 == 0 || x `mod` 5 == 0]

And here's the output:

[3,5,6,9]

Success! This matches the list from the sample. Now we just have to sum these numbers. Fortunately, we can just pass a list to the "sum" function.

sum [x | x <- [1..9], x `mod` 3 == 0 || x `mod` 5 == 0]

And the output:

23

This matches the sample case. Now we just need to swap out the "below 10" for "below 1000":

sum [x | x <- [1..999], x `mod` 3 == 0 || x `mod` 5 == 0]

And the answer:

233168

Note: I've verified this is correct by looking at the answer to Euler Problem #1.

Making a Reusable Function
The last thing that I want to do is create a reusable function. (I'm not really sure what use I would have for this, but anyway...) So, let's parameterize this with the "below this number" value (ignore any line breaks you might see).

euler1 belowThis = sum [x | x <- [1..(belowThis-1)], x `mod` 3 == 0 || x `mod` 5 == 0]

Basically, we created a named function "euler1" with a parameter for our "belowThis" number. Since ranges are inclusive, we subtract one from the value before creating our original list.

Now we can use this function with the sample:

euler1 10
23

Or with the target value:

euler1 1000
233168

That's pretty cool.

To create this function, we just started with the inside and worked our way out. And this is a big difference between thinking functionally and thinking procedurally. If I were to try this with C#, I would probably just "brute force" it. You can see an example of that here: http://www.mathblog.dk/project-euler-problem-1/.

But instead, we have something functional and elegant. And also a good way to stretch a bit to learn functional programming. And I'm already starting to see how I can use these techniques to make my everyday programming (in C#) much better.

I'll leave the rest of the Euler Problems as an exercise for the reader.

Happy Coding!