How to resolve the algorithm Maximum triangle path sum step by step in the BASIC programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Maximum triangle path sum step by step in the BASIC 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 BASIC programming language
Source code in the basic programming language
arraybase 1
dim ln(19)
ln[1] = " 55"
ln[2] = " 94 48"
ln[3] = " 95 30 96"
ln[4] = " 77 71 26 67"
ln[5] = " 97 13 76 38 45"
ln[6] = " 07 36 79 16 37 68"
ln[7] = " 48 07 09 18 70 26 06"
ln[8] = " 18 72 79 46 59 79 29 90"
ln[9] = " 20 76 87 11 32 07 07 49 18"
ln[10] = " 27 83 58 35 71 11 25 57 29 85"
ln[11] = " 14 64 36 96 27 11 58 56 92 18 55"
ln[12] = " 02 90 03 60 48 49 41 46 33 36 47 23"
ln[13] = " 92 50 48 02 36 59 42 79 72 20 82 77 42"
ln[14] = " 56 78 38 80 39 75 02 71 66 66 01 03 55 72"
ln[15] = " 44 25 67 84 71 67 11 61 40 57 58 89 40 56 36"
ln[16] = " 85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52"
ln[17] = " 06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15"
ln[18] = " 27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93"
ln[19] = "end"
dim matrix(20,20)
x = 1
tam = 0
for n = 1 to length(ln) - 1
ln2 = trim(ln[n])
for y = 1 to x
matrix[x, y] = fromradix((left(ln2, 2)), 10)
if length(ln2) > 4 then ln2 = mid(ln2, 4, length(ln2)-4)
next y
x += 1
tam += 1
next n
for x = tam - 1 to 1 step - 1
for y = 1 to x
s1 = matrix[x+1, y]
s2 = matrix[x+1, y+1]
if s1 > s2 then
matrix[x, y] = matrix[x, y] + s1
else
matrix[x, y] = matrix[x, y] + s2
end if
next y
next x
print " maximum triangle path sum = " + matrix[1, 1]
100 DIM LN$(19)
110 LN$(1) = "55"
120 LN$(2) = "94 48"
130 LN$(3) = "95 30 96"
140 LN$(4) = "77 71 26 67"
150 LN$(5) = "97 13 76 38 45"
160 LN$(6) = "07 36 79 16 37 68"
170 LN$(7) = "48 07 09 18 70 26 06"
180 LN$(8) = "18 72 79 46 59 79 29 90"
190 LN$(9) = "20 76 87 11 32 07 07 49 18"
200 LN$(10) = "27 83 58 35 71 11 25 57 29 85"
210 LN$(11) = "14 64 36 96 27 11 58 56 92 18 55"
220 LN$(12) = "02 90 03 60 48 49 41 46 33 36 47 23"
230 LN$(13) = "92 50 48 02 36 59 42 79 72 20 82 77 42"
240 LN$(14) = "56 78 38 80 39 75 02 71 66 66 01 03 55 72"
250 LN$(15) = "44 25 67 84 71 67 11 61 40 57 58 89 40 56 36"
260 LN$(16) = "85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52"
270 LN$(17) = "06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15"
280 LN$(18) = "27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93"
290 LN$(19) = "end"
300 DIM MATRIX(20,20)
310 X = 1
320 TAM = 0
330 FOR N = 1 TO 19
340 LN2$ = LN$(N)
350 FOR Y = 1 TO X
360 MATRIX(X,Y) = VAL(LEFT$(LN2$,2))
370 IF LEN(LN2$) > 4 THEN LN2$ = MID$(LN2$,4,LEN(LN2$)-4)
380 NEXT Y
390 X = X+1
400 TAM = TAM+1
410 NEXT N
420 FOR Z = TAM-1 TO 1 STEP -1
430 FOR Y = 1 TO Z
440 S1 = MATRIX(Z+1,Y)
450 S2 = MATRIX(Z+1,Y+1)
460 IF S1 > S2 THEN MATRIX(Z,Y) = MATRIX(Z,Y)+S1
470 IF S1 <= S2 THEN MATRIX(Z,Y) = MATRIX(Z,Y)+S2
480 NEXT Y
490 NEXT Z
500 PRINT " maximum triangle path sum = ";MATRIX(1,1)
OpenConsole()
Dim ln.s(19)
ln(1) = " 55"
ln(2) = " 94 48"
ln(3) = " 95 30 96"
ln(4) = " 77 71 26 67"
ln(5) = " 97 13 76 38 45"
ln(6) = " 07 36 79 16 37 68"
ln(7) = " 48 07 09 18 70 26 06"
ln(8) = " 18 72 79 46 59 79 29 90"
ln(9) = " 20 76 87 11 32 07 07 49 18"
ln(10) = " 27 83 58 35 71 11 25 57 29 85"
ln(11) = " 14 64 36 96 27 11 58 56 92 18 55"
ln(12) = " 02 90 03 60 48 49 41 46 33 36 47 23"
ln(13) = " 92 50 48 02 36 59 42 79 72 20 82 77 42"
ln(14) = " 56 78 38 80 39 75 02 71 66 66 01 03 55 72"
ln(15) = " 44 25 67 84 71 67 11 61 40 57 58 89 40 56 36"
ln(16) = " 85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52"
ln(17) = " 06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15"
ln(18) = " 27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93"
ln(19) = "end"
Dim matrix.i(20,20)
Define.i x = 1, tam = 0
Define.i i, y, s1, s2, n
For n = 1 To ArraySize(ln(),1) - 1
ln2.s = LTrim(ln(n))
For y = 1 To x
matrix(x, y) = Val(Left(ln2, 2))
If Len(ln2) > 4:
ln2 = Mid(ln2, 4, Len(ln2)-4)
EndIf
Next y
x + 1
tam + 1
Next n
For x = tam - 1 To 1 Step - 1
For y = 1 To x
s1 = matrix(x+1, y)
s2 = matrix(x+1, y+1)
If s1 > s2:
matrix(x, y) = matrix(x, y) + s1
Else
matrix(x, y) = matrix(x, y) + s2
EndIf
Next y
Next x
PrintN(#CRLF$ + " maximum triangle path sum = " + Str(matrix(1, 1)))
Input()
CloseConsole()
dim ln$(19)
ln$(1) = " 55"
ln$(2) = " 94 48"
ln$(3) = " 95 30 96"
ln$(4) = " 77 71 26 67"
ln$(5) = " 97 13 76 38 45"
ln$(6) = " 07 36 79 16 37 68"
ln$(7) = " 48 07 09 18 70 26 06"
ln$(8) = " 18 72 79 46 59 79 29 90"
ln$(9) = " 20 76 87 11 32 07 07 49 18"
ln$(10) = " 27 83 58 35 71 11 25 57 29 85"
ln$(11) = " 14 64 36 96 27 11 58 56 92 18 55"
ln$(12) = " 02 90 03 60 48 49 41 46 33 36 47 23"
ln$(13) = " 92 50 48 02 36 59 42 79 72 20 82 77 42"
ln$(14) = " 56 78 38 80 39 75 02 71 66 66 01 03 55 72"
ln$(15) = " 44 25 67 84 71 67 11 61 40 57 58 89 40 56 36"
ln$(16) = " 85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52"
ln$(17) = " 06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15"
ln$(18) = " 27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93"
ln$(19) = "end"
dim matrix(20,20)
x = 1
tam = 0
for n = 1 to 19 'ubound(ln$) - 1
ln2$ = trim$(ln$(n))
for y = 1 to x
matrix(x, y) = val(left$(ln2$, 2))
if len(ln2$) > 4 then ln2$ = mid$(ln2$, 4, len(ln2$)-4)
next y
x = x +1
tam = tam +1
next n
for z = tam-1 to 1 step -1
for y = 1 to z
s1 = matrix(z+1, y)
s2 = matrix(z+1, y+1)
if s1 > s2 then
matrix(z, y) = matrix(z, y) +s1
else
matrix(z, y) = matrix(z, y) +s2
end if
next y
next z
print " maximum triangle path sum = "; matrix(1, 1)
DATA " 55"
DATA " 94 48"
DATA " 95 30 96"
DATA " 77 71 26 67"
DATA " 97 13 76 38 45"
DATA " 07 36 79 16 37 68"
DATA " 48 07 09 18 70 26 06"
DATA " 18 72 79 46 59 79 29 90"
DATA " 20 76 87 11 32 07 07 49 18"
DATA " 27 83 58 35 71 11 25 57 29 85"
DATA " 14 64 36 96 27 11 58 56 92 18 55"
DATA " 02 90 03 60 48 49 41 46 33 36 47 23"
DATA " 92 50 48 02 36 59 42 79 72 20 82 77 42"
DATA " 56 78 38 80 39 75 02 71 66 66 01 03 55 72"
DATA " 44 25 67 84 71 67 11 61 40 57 58 89 40 56 36"
DATA " 85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52"
DATA " 06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15"
DATA " 27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93"
DATA "END" ! no more DATA
DIM matrix(1 TO 20, 1 TO 20)
LET x = 1
DO
READ ln$
LET ln$ = LTRIM$(RTRIM$(ln$))
IF ln$ = "END" THEN EXIT DO
FOR y = 1 TO x
LET matrix(x, y) = VAL((ln$)[1:2])
LET ln$ = (ln$)[4:maxnum]
NEXT y
LET x = x+1
LET tam = tam+1
LOOP
FOR x = tam-1 TO 1 STEP -1
FOR y = 1 TO x
LET s1 = matrix(x+1, y)
LET s2 = matrix(x+1, y+1)
IF s1 > s2 THEN LET matrix(x, y) = matrix(x, y)+s1 ELSE LET matrix(x, y) = matrix(x, y)+s2
NEXT y
NEXT x
PRINT " maximum triangle path sum ="; matrix(1, 1)
END
dim ln$(19)
ln$(1) = " 55"
ln$(2) = " 94 48"
ln$(3) = " 95 30 96"
ln$(4) = " 77 71 26 67"
ln$(5) = " 97 13 76 38 45"
ln$(6) = " 07 36 79 16 37 68"
ln$(7) = " 48 07 09 18 70 26 06"
ln$(8) = " 18 72 79 46 59 79 29 90"
ln$(9) = " 20 76 87 11 32 07 07 49 18"
ln$(10) = " 27 83 58 35 71 11 25 57 29 85"
ln$(11) = " 14 64 36 96 27 11 58 56 92 18 55"
ln$(12) = " 02 90 03 60 48 49 41 46 33 36 47 23"
ln$(13) = " 92 50 48 02 36 59 42 79 72 20 82 77 42"
ln$(14) = " 56 78 38 80 39 75 02 71 66 66 01 03 55 72"
ln$(15) = " 44 25 67 84 71 67 11 61 40 57 58 89 40 56 36"
ln$(16) = " 85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52"
ln$(17) = " 06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15"
ln$(18) = " 27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93"
ln$(19) = "end"
dim matrix(20,20)
x = 1
tam = 0
for n = 1 to arraysize(ln$(),1) - 1
ln2$ = trim$(ln$(n))
for y = 1 to x
matrix(x, y) = val(left$(ln2$, 2))
if len(ln2$) > 4 ln2$ = mid$(ln2$, 4, len(ln2$)-4)
next y
x = x + 1
tam = tam + 1
next n
for x = tam - 1 to 1 step - 1
for y = 1 to x
s1 = matrix(x+1, y)
s2 = matrix(x+1, y+1)
if s1 > s2 then
matrix(x, y) = matrix(x, y) + s1
else
matrix(x, y) = matrix(x, y) + s2
end if
next y
next x
print "\n maximum triangle path sum = ", matrix(1, 1)
You may also check:How to resolve the algorithm Day of the week step by step in the C++ programming language
You may also check:How to resolve the algorithm Sierpinski pentagon step by step in the Ruby programming language
You may also check:How to resolve the algorithm Compound data type step by step in the EchoLisp programming language
You may also check:How to resolve the algorithm Test a function step by step in the Odin programming language
You may also check:How to resolve the algorithm Bitwise operations step by step in the Go programming language