How to resolve the algorithm Maximum triangle path sum step by step in the Prolog programming language

Published on 12 May 2024 09:40 PM
#Prolog

How to resolve the algorithm Maximum triangle path sum step by step in the Prolog programming language

Table of Contents

Problem Statement

Starting from the top of a pyramid of numbers like this, you can walk down going one step on the right or on the left, until you reach the bottom row: One of such walks is 55 - 94 - 30 - 26. You can compute the total of the numbers you have seen in such walk, in this case it's 205. Your problem is to find the maximum total among all possible paths from the top to the bottom row of the triangle. In the little example above it's 321.

Find the maximum total in the triangle below: Such numbers can be included in the solution code, or read from a "triangle.txt" file. This task is derived from the Euler Problem #18.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Maximum triangle path sum step by step in the Prolog programming language

Source code in the prolog programming language

max_path(N, V) :-
	data(N, T),
	path(0, T, V).

path(_N, [], 0) .
path(N, [H | T], V) :-
	nth0(N, H, V0),
	N1 is N+1,
	path(N, T, V1),
	path(N1, T, V2),
	V is V0 +  max(V1, V2).

data(1, P) :-
	P =
	[ [55],
	  [94, 48],
	  [95, 30, 96],
	  [77, 71, 26, 67]].


data(2, P) :-
	P =
	[ [55],
	  [94, 48],
	  [95, 30, 96],
	  [77, 71, 26, 67],
	  [97, 13, 76, 38, 45],
	  [7, 36, 79, 16, 37, 68],
	  [48, 7, 9, 18, 70, 26, 6],
	  [18, 72, 79, 46, 59, 79, 29, 90],
	  [20, 76, 87, 11, 32, 7, 7, 49, 18],
	  [27, 83, 58, 35, 71, 11, 25, 57, 29, 85],
	  [14, 64, 36, 96, 27, 11, 58, 56, 92, 18, 55],
	  [2, 90, 3, 60, 48, 49, 41, 46, 33, 36, 47, 23],
	  [92, 50, 48, 2, 36, 59, 42, 79, 72, 20, 82, 77, 42],
	  [56, 78, 38, 80, 39, 75, 2, 71, 66, 66, 1, 3, 55, 72],
	  [44, 25, 67, 84, 71, 67, 11, 61, 40, 57, 58, 89, 40, 56, 36],
	  [85, 32, 25, 85, 57, 48, 84, 35, 47, 62, 17, 1, 1, 99, 89, 52],
	  [6, 71, 28, 75, 94, 48, 37, 10, 23, 51, 6, 48, 53, 18, 74, 98, 15],
	  [27, 2, 92, 23, 8, 71, 76, 84, 15, 52, 92, 63, 81, 10, 44, 10, 69, 93]].

You may also check:How to resolve the algorithm Walk a directory/Non-recursively step by step in the UNIX Shell programming language
You may also check:How to resolve the algorithm Simple database step by step in the REXX programming language
You may also check:How to resolve the algorithm Poker hand analyser step by step in the REXX programming language
You may also check:How to resolve the algorithm Euler's sum of powers conjecture step by step in the Arturo programming language
You may also check:How to resolve the algorithm Voronoi diagram step by step in the ReScript programming language