Saturday, September 21, 2013

Problem 18 redo - Prolog

I used Prolog briefly a long time ago, around the time that I first got into Project Euler and solved programs in Scheme, but it has been a very long time, and I never did anything vaguely useful with it. So, now I decided to use it for a Project Euler problem. I didn't have very fond memories of my brief foray into Prolog, but after solving this problem in Prolog, I have found that it can actually be a pretty nice language, and I may want to use it for some future problems. It is certainly very different from most other languages, being a logical language and all, calculating through inferences on and trees and such, but it worked out in the end.

My first solution to this problem in Prolog accidentally ended up having exponential complexity and took a couple minutes to run, but this solution below runs in less than a milisecond (it requires Prolog to perform only 799 inferences). Solving this problem in Prolog freed up Scala, but now I would not be surprised if some time down the line I use some sillier language for this problem and recover Prolog.
getRow(R, Row) :-
nth0(R, [[75],
 [95,64],
 [17,47,82],
 [18,35,87,10],
 [20,4,82,47,65],
 [19,1,23,75,3,34],
 [88,2,77,73,7,63,67],
 [99,65,4,28,6,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,4,68,89,53,67,30,73,16,69,87,40,31],
 [4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]], 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(14, W) :- getRow(14, W).
ans(N, W)  :-
    N1 is N + 1,
    getRow(N, Top),
    ans(N1, Bottom),
    combineRows(Bottom, Top, W).

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

No comments:

Post a Comment