Project Euler - Problem 34

 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!

Comments

• Anonymous
  April 15, 2008
  PingBack from http://microsoftnews.askpcdoc.com/?p=2630

• Anonymous
  May 09, 2008
  Now that we have covered the basics, in minutes 8 - 14 we will cover the foundational concepts and types

• Anonymous
  June 06, 2008
  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

• Anonymous
  October 09, 2008
  The comment has been removed

• Anonymous
  May 28, 2009
  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...

• Anonymous
  May 31, 2009
  :) i liked the bug, it was harder to find then it was to solve the problem