Friday, January 27, 2012

A Solution For Project Euler Problem 67 in F#

I'm a fan of the projecteuler site. This site lists some 300+ problems everyone is invited to solve. Some of them are relatively easy, some very tricky. As Wikipedia states:
«... Project Euler (named after Leonhard Euler) is a website dedicated to a series of computational problems intended to be solved with computer programs. The project attracts adults and students interested in mathematics and computer programming. As of 24 January 2012, it includes 368[1] problems of varying difficulty, each solvable in less than a minute using an efficient algorithm on a modestly powered computer.  ...»
From time to time I stop by and pick one or more of the problems and try to implement them in different languages. This is always a very interesting experience because it teaches me a lot about the differences between programming languages, their constructs and - of course - the pros and cons of different programming styles. This by the way can also be a very good and fun way to get your hands dirty while learning new languages.

The Problem

Recently I stumbled upon an interesting problem - problem number 67. Given a triangle of numbers, by starting at the top and moving to adjacent child nodes one level below, you are to find the maximum total from top to bottom by adding the respective values. It follows the example from the projecteuler.net site:
3
7 4
2 4 6
8 5 9 3

The resulting total in this example is 3 + 7 + 4 + 9 = 23.
In fact, problem 67 is the same as problem 18 with the little, but, as you will see in a moment, very important difference of a bigger problem size.

On the way to solve that bastard

In fact, problem 67 is the same as problem 18 with the little, but, as you will see in a moment, very important difference of a bigger problem size.