Monday, January 12, 2009

Erlang solution for Euler problem 9

In Euler problem 9 we are asked to find the one and only Pythagoran triplet for which a+b+c=1000.

We simply try all combinations of three numbers and check whether each is the solution we are looking for.

The main the complication is the order in which all combinations of three numbers are generated. The following example illustrates this:

1 2 3
1 2 4
1 3 4
2 3 4
1 2 5
1 3 5
2 3 5
1 4 5
2 4 5
3 4 5
1 2 6
1 3 6
2 3 6
1 4 6
2 4 6
3 4 6
1 5 6
2 5 6
...


Here is the corresponding Erlang program:

%% Project Euler, problem 9
%%
%% Find the greatest product of five consecutive digits in a given 1000-digit number.

%% A Pythagorean triplet is a set of three natural numbers, a < 2 =" c^2" 2 =" 9" 16 =" 25" c =" 1000.">
(A*A + B*B == C*C) and (A + B + C == 1000).

solve(A,B,C) ->
case isSolution(A,B,C) of
true -> A * B * C;
false ->
if
A+1 <>
solve(A+1, B, C);
true ->
if
B+1 <>
solve (1, B+1, C);
true ->
solve (1, 2, C+1)
end
end
end.

solve() ->
solve(1,2,3).

No comments: