* Edit 2/8/2010: Updating for recent F# language changes.*

In our continuing series of how to solve Project Euler problems easily with F#, we now arrive at problem 34 which is defined as:

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Our solution in F# **demonstrates the epic power of the** ‘**forward pipe’ **operator (|>), on subject of which Brian McNamara has written an excellent blog post.

**The Algorithm**

While more clever solutions to this problem exist, let’s walk through how to compute the result by trial and error.

We start with simply enumerate all numbers which we guess will be in the range of valid numbers with the desired property, say 3 to 10! (since 1! and 2! don’t count as per the problem description). For each number __Map__ it to the sum of the factorial of its digits. (Which we will refer to as ‘SumFactDigit’.)

To compute the SumFactDigit we will take the string-representation of a number and __Map__ each character to its integer value, __Map__-ing that its factorial, and finally __Fold__-ing the sequence via the plus operator. (E.g., 145 -> “145” -> {‘1’, ‘4’, ‘5’} -> {1!, 4!, 5!} -> 145.)

Once we have the SumFactDigit of each number, we use __Mapi__ which is the same as Map, but there is an additional parameter which is the index in the sequence. This way we can get index i paired with the SumFactDigit of i.

Then, we __Filter__ out all numbers which aren’t equal to their SumFactDigit. Next we __Map__ again, simply to drop tuple of (i, sum of fact of digits) to just i. And finally we __Fold__ again, summing the sequence.

Nothing tricky about that, just a series of computations. If we tried to write this in C# we would probably have to create a lot of variables to store intermediate results, pass those into functions to store computations, and generally write a lot of code. In F# however, we simply pipe (|>) the results of one step into the next, yielding a very clean solution.

#light

// PE 34

let rec fact x = if x <= 1 then 1 else x * (fact (x – 1))

let _ =

seq { for i in [3 .. (fact 10)] -> (i.ToString()) }

|> Seq.map

(fun str -> str

|> Seq.map (fun c -> int c – int ‘0’)

|> Seq.map fact

|> Seq.fold (+) 0)

|> Seq.mapi

(fun idx x -> (idx = x), idx)

|> Seq.filter (fun (eq, idx) -> eq)

|> Seq.map (fun (eq, idx) -> idx)

|> Seq.fold (+) 0

|> printfn “%d”

As you can see, the pipe forward operator goes a long way to simplifying code. Notice that you didn’t even to store the result, as you can pipe the answer directly to printfn J.

**Caveat**: As much as I want the average ‘genius rating’ for F# programmers to be as high as possible, to discourage allegations of me helping people cheat I’ve left a very subtle bug in the program above. If you put this into the F# compiler the result will be zero. So to get credit for solving the problem you have to understand the code well enough to find and fix the error. Good luck!

PingBack from http://microsoftnews.askpcdoc.com/?p=2630

Now that we have covered the basics, in minutes 8 – 14 we will cover the foundational concepts and types

In our continuing series of how to solve Project Euler problems easily with F#, we now arrive at problem 34 which is defined as: 145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145. Find the sum of all numbers which are equal to the sum of th

Ooh, that was subtle. *glare* I’m an F# noob, granted. Thanks for the brain teaser *on top of* a brain teaser. =)

Actually, I didn’t find that bug "subtle". It was so glaring that I actually convinced myself mapi was doing some magic beyond my understanding. When I finished reading the blog and went after the bug, it never ocurred to me to question it…

🙂 i liked the bug, it was harder to find then it was to solve the problem