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