Thursday, July 1, 2010

Project Euler Problem 1

Today's post is short; my solution to Project Euler problem 1. In brief, the problem is to sum the multiples of 3 or 5 which are less than 1000.

It's possible to use F# aggregate operators and a bit of comprehension meta-programming to get a really succinct solution. The technique is to sum all the multiples of 3, all the multiples of 5, and then subtract out the redundant sum of the multiples of 15. I generalized the solution for any two multiples and any limit (note that my limit is inclusive). (As always, presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.)

let euler1 d0 d1 n =
  (seq {d0..d0..n}       |> Seq.sum) +
  (seq {d1..d1..n}       |> Seq.sum) -
  (seq {d0*d1..d0*d1..n} |> Seq.sum)

The main thing I like about this solution is something that has become a theme for me in F#: it resembles the problem in such a way that I could explain the solution to someone who wasn't a programmer. This is important for a number of reasons, but particulary because it is allows non-programmer domain experts to participate in the software design and validation process. With the addition of a few domain-specific language extenstions, this becomes even more true. Thus F# can act as an excellent platform for software integration into areas like business, finance, and science.

The code above is not earth-shaking. But it demonstrates how F# permits, and even encourages, something one could call "fluent programming." That is, the encoding of a solution in a way that comprehends and explains a problem, recognizing that a problem and its solution are two sides of the same coin. (In contrast to solutions which do violence to this complementarity by forcing an "unnatural" solution.) And domain experts respond to that kind of representation because that's how they think about problems and solutions. They can look at the code and, even if they're not programmers, they can develop intuitions about its correctness or incorrectness.

And that's what I like about F#.


p.s. I don't intend to follow the entire sequence of Project Euler problems here; I'll just pick and choose a few to illustrate some aspects of F#. For an excellent F# series about Project Euler (and other good stuff), please follow the posts and comments at Mark Pearl's blog.

No comments: