Tuesday, May 06, 2008

Project Euler problem six is another easy one.

The sum of the squares of the first ten natural numbers is,

12 + 22 + ... + 102 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + ... + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

The solution to this problem boils down to a few folding operations and a map. The one-liner is below.

List.fold_left (+) 0 [1..100] * List.fold_left (+) 0 [1..100] - List.fold_left (+) 0 (List.map (fun x -> x * x) [1..100])

Pretty nasty, eh? Quite a bit of code duplication can be removed. Since they're identical, let's generalize all of the folds first by extracting them to a sum function.

let sum lst = List.fold_left (+) 0 lst

sum [1..100] * sum [1..100] - sum (List.map (fun x -> x * x) [1..100])

That already looks a lot better.

Next, we can generalize the multiplication operations. Each time multiplication occurs in the solution above, it's simply squaring a value. So, we can extract those operations into a square function.

let square x = x * x

square (sum [1..100]) - sum (List.map (fun x -> square x) [1..100])

We can simplify that even further. Because the anonymous function passed to List.map just applies its argument to the square function, we can pass square directly.

square (sum [1..100]) - sum (List.map square [1..100])

Next, let's generalize the call to List.map that produces a list of squares by moving it to a new function, squares.

let squares lst = List.map square lst

square (sum [1..100]) - sum (squares [1..100])

At this point, we have a perfectly acceptable solution. It states the problem almost like natural English: "The square of the sum of 1 to 100 minus the sum of the squares of 1 to 100." So, why are there a few more inches left in this article? Well, I'd like to take this a step further.

Thinking more abstractly, what does our solution do? It computes the difference of two calculations that are based on the same list. We can extract this general process to a new function like so:

let difference f1 f2 lst = f1 lst - f2 lst

difference (fun l -> square (sum l)) (fun l -> sum (squares l)) [1..100]

It turns out that we can simplify these anonymous functions in the same way that we did with the square function earlier. However, because there are two functions involved in each calculation, we must compose the functions together. In F#, there are two operators used to perform function composition: the >> operator, which applies the functions from left to right, and the << operator, which applies the functions from right to left. Obviously, we need the latter.

difference (square << sum) (sum << squares) [1..100]

After using the forward pipe operator to move the list to the front, we're finished.

[1..100] |> difference (square << sum) (sum << squares)

"Take the numbers 1 to 100 and find the difference of the square of the sum and the sum of the squares."

Function composition is beautiful.

posted on Tuesday, May 06, 2008 3:21:26 AM (Pacific Standard Time, UTC-08:00)  #    Comments [3]

kick it on DotNetKicks.com