Another Euler problem. It has a cute recursive solution, and the problem looks like something that might have real applications, say the scoring of a decision tree. I’ll leave the description of the problem to link above. Might as well send Project Euler some link love. And it would be tedious to provide the nice visual layout PE does.

One annoyance I have to mention is that I have not been able to find where Erlang defines the max of two numbers, so I am forced to define it. That just seems wrong.

Here’s the solution.

-module(p18).
-export([start/0]).

max(X,Y) when X > Y -> X;
max(X,Y) -> Y.

%% A and B are rows of the triangle
%% merge takes two rows of lengths
%% k and k+1 and returns one row of
%% length K
merge(A,B)-> merge(A,B,[]).

merge([A,B], [C], Result)->
    lists:reverse([C + max(A,B) | Result]);

merge([A,B|Rest], [C|Tail], Result)->
    merge([B|Rest], Tail,  [C+ max(A,B) | Result]).

%% the triangle is a list of lists
%% each call to reduce in effect reduces the
%% length of triangle by 1 till only one row is left
reduce([A,B|Tail])-> reduce([merge(A,B)| Tail]);
reduce([A])-> A.

start() ->
    Triangle =
	[[75],
	 [95, 64],
	 [17, 47, 82],
	 [18, 35, 87, 10],
	 [20, 04, 82, 47, 65],
	 [19, 01, 23, 75, 03, 34],
	 [88, 02, 77, 73, 07, 63, 67],
	 [99, 65, 04, 28, 06, 16, 70, 92],
	 [41, 41, 26, 56, 83, 40, 80, 70, 33],
	 [41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
	 [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
	 [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
	 [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
	 [63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
	 [04, 62, 98, 27, 23, 09, 70, 98, 73, 93, 38, 53, 60, 04, 23]],
    io:format("~p ~n",[reduce(lists:reverse(Triangle))]).