Sunday, November 17, 2013

Problem 67 - Prolog

Problem 67 is really identical to problem 18, other than that the data set is larger. Luckily, my solution in Prolog to problem 18 was plenty fast for it to scale well to this problem. My solution runs in about half a second, having to perform 34,211 inferences in Prolog. And yeah...maybe I should find a way to load the input from a text file, but for now, the entire data table is explicitly in the program...therefore, below is an abbreviated version, the full solution, with the 100 line triangle description, is linked to from the Progress table.
getRow(R, Row) :-
nth0(R,[[59],
[73,41],
[52,40,9],
[26,53,6,34],
...,59,63,35]], Row).

max(X, Y, Y) :- Y >= X.
max(X, Y, X) :- X >= Y.

prepend([], Z, [Z]).
prepend([X|Y], Z, [Z,X|Y]).

combineRows([X, Y], [Z], Row) :-
    XZ is X + Z,
    YZ is Y + Z,
    max(XZ, YZ, N),
    prepend([], N, Row).

combineRows([X,Y|T1], [Z|T2], Row) :-
    XZ is X + Z,
    YZ is Y + Z,
    max(XZ, YZ, N),
    combineRows([Y|T1], T2, Tail),
    prepend(Tail, N, Row).

ans(99, W) :- getRow(99, W).
ans(N, W)  :-
    N1 is N + 1,
    getRow(N, Top),
    ans(N1, Bottom),
    combineRows(Bottom, Top, W).

%% Command to Find the Answer:
e67(W) :- ans(0, List),
    nth0(0, List, W).

No comments:

Post a Comment