Maximum triangle path sum: Difference between revisions

=={{Header|Fortran}}==

This being Fortran, why not a brute-force scan of all possible paths? This is eased by noting that from a given position, only two numbers are accessible, and always two numbers. Just like binary digits. So, for three levels, the choices would be 000, 001, 010, 011, 100, 101, 110, 111 or somesuch. Since however the pinnacle of the pyramid is always chosen, there is no choice there so the digits would be 100, 101, 110,111.

A triangular array can be defined in some languages, and in some circumstances a square array is used with a lower triangle and upper triangle partition, but here, a simple linear array is in order, with some attention to subscript usage. The first layer has one number, the second has two, the third has three, ... easy enough.

For input, free-format is convenient. Bad input still is a problem, and can lead to puzzles. If say when N values are to be read but an input line is short of numbers, then additional lines will be read and confusion is likely. So, read the file's record into a text variable and then extract the expected N values from that. Should a problem arise, then the troublesome record can be shown.

<lang Fortran>

MODULE PYRAMIDS !Produces a pyramid of numbers in 1-D array.

INTEGER MANY !The usual storage issues.

PARAMETER (MANY = 666) !This should suffice.

INTEGER BRICK(MANY),IN,LAYERS !Defines a pyramid.

CONTAINS

SUBROUTINE IMHOTEP(PLAN)!The architect.

CHARACTER*(*) PLAN !The instruction file.

INTEGER I,IT !Steppers.

CHARACTER*666 ALINE !A scratchpad for input.

IN = 0 !No bricks.

LAYERS = 0 !In no courses.

WRITE (6,*) "Reading from ",PLAN !Here we go.

OPEN(10,FILE=PLAN,FORM="FORMATTED",ACTION="READ",ERR=6) !I hope.

GO TO 10 !Why can't OPEN be a function?@*&%#^%!

6 STOP "Can't grab the file!"

Chew into the plan.

10 READ (10,11,END = 20) ALINE !Get the whole line in one piece.

11 FORMAT (A) !As plain text.

IF (ALINE .EQ. "") GO TO 10 !Ignoring any blank lines.

IF (ALINE(1:1).EQ."%") GO TO 10 !A comment opportunity.

LAYERS = LAYERS + 1 !Righto, this should be the next layer.

READ (ALINE,*,END = 15,ERR = 15) BRICK(IN + 1:IN + LAYERS) !Free format.

IN = IN + LAYERS !Insufficient numbers will provoke trouble.

GO TO 10 !Extra numbers/stuff will be ignored.

Caught a crab? A bad number, or too few numbers on a line? No read-next-record antics, thanks.

15 WRITE (6,16) LAYERS,ALINE !Just complain.

16 FORMAT ("Bad layer ",I0,": ",A)

Completed the plan.

20 WRITE (6,21) IN,LAYERS !Announce some details.

21 FORMAT (I0," bricks in ",I0," layers.")

CLOSE(10) !Finished with input.

Cast forth the numbers in a nice pyramid.

30 IT = 0 !For traversing the pyramid.

DO I = 1,LAYERS !Each course has one more number than the one before.

WRITE (6,31) BRICK(IT + 1:IT + I) !Sweep along the layer.

31 FORMAT (<LAYERS*2 - 2*I>X,666I4) !Leading spaces may be zero in number.

IT = IT + I !Thus finger the last of a layer.

END DO !On to the start of the next layer.

END SUBROUTINE IMHOTEP !The pyramid's plan is ready.

SUBROUTINE TRAVERSE !Clamber around the pyramid. Thoroughly.

C The idea is that a pyramid of numbers is provided, and then, starting at the peak,

c work down to the base summing the numbers at each step to find the maximum value path.

c The constraint is that from a particular brick, only the two numbers below left and below right

c may be reached in stepping to that lower layer.

c Since that is a 0/1 choice, recorded in MOVE, a base-two scan searches the possibilities.

INTEGER MOVE(LAYERS) !Choices are made at the various positions.

INTEGER STEP(LAYERS),WALK(LAYERS) !Thus determining the path.

INTEGER I,L,IT !Steppers.

INTEGER PS,WS !Scores.

WRITE (6,1) LAYERS !Announce the intention.

1 FORMAT (//,"Find the highest score path across a pyramid of ",

1 I0," layers."/) !I'm not worrying over singular/plural.

MOVE = 0 !All 0/1 values to zero.

MOVE(1) = 1 !Except the first.

STEP(1) = 1 !Every path starts here, without option.

WS = -666 !The best score so far.

Commence a multi-level loop, using the values of MOVE as the digits, one digit per level.

10 IT = 1 !All paths start with the first step.

PS = BRICK(1) !The starting score,.

c write (6,8) "Move",MOVE,WS

DO L = 2,LAYERS !Deal with the subsequent layers.

IT = IT + L - 1 + MOVE(L) !Choose a brick.

STEP(L) = IT !Remember this step.

PS = PS + BRICK(IT) !Count its score.

c WRITE (6,6) L,IT,BRICK(IT),PS

6 FORMAT ("Layer ",I0,",Brick(",I0,")=",I0,",Sum=",I0)

END DO !Thus is the path determined.

IF (PS .GT. WS) THEN !An improvement?

IF (WS.GT.0) WRITE (6,7) WS,PS !Yes! Announce.

7 FORMAT ("Improved path score: ",I0," to ",I0)

WRITE (6,8) "Moves",MOVE !Show the choices at each layer..

WRITE (6,8) "Steps",STEP !That resulted in this path.

WRITE (6,8) "Score",BRICK(STEP) !Whose steps were scored thus.

8 FORMAT (A8,666I4) !This should suffice.

WS = PS !Record the new best value.

WALK = STEP !And the path thereby.

END IF !So much for an improvement.

DO L = LAYERS,1,-1 !Now add one to the number in MOVE.

IF (MOVE(L).EQ.0) THEN !By finding the lowest order zero.

MOVE(L) = 1 !Making it one,

MOVE(L + 1:LAYERS) = 0 !And setting still lower orders back to zero.

GO TO 10 !And if we did, there's more to do!

END IF !But if that bit wasn't zero,

END DO !Perhaps the next one up will be.

WRITE (6,*) WS," is the highest score." !So much for that.

END SUBROUTINE TRAVERSE !All paths considered...

END MODULE PYRAMIDS

PROGRAM TRICKLE

USE PYRAMIDS

c CALL IMHOTEP("Sakkara.txt")

CALL IMHOTEP("Cheops.txt")

CALL TRAVERSE

END

</lang>

Output:

<pre>

Reading from Cheops.txt

171 bricks in 18 layers.

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

Find the highest score path across a pyramid of 18 layers.

Moves 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Steps 1 2 4 7 11 16 22 29 37 46 56 67 79 92 106 121 137 154

Score 55 94 95 77 97 7 48 18 20 27 14 2 92 56 44 85 6 27

Improved path score: 864 to 904

Moves 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0

Steps 1 2 4 7 11 16 22 29 37 46 56 67 79 92 106 121 138 155

Score 55 94 95 77 97 7 48 18 20 27 14 2 92 56 44 85 71 2

Improved path score: 904 to 994

Moves 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1

Steps 1 2 4 7 11 16 22 29 37 46 56 67 79 92 106 121 138 156

Score 55 94 95 77 97 7 48 18 20 27 14 2 92 56 44 85 71 92

Improved path score: 994 to 1041

Moves 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1

Steps 1 2 4 7 11 16 22 29 37 46 56 67 79 93 108 124 141 159

Score 55 94 95 77 97 7 48 18 20 27 14 2 92 78 67 85 94 71

Improved path score: 1041 to 1087

Moves 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 1

Steps 1 2 4 7 11 16 22 29 37 46 56 68 80 93 108 124 141 159

Score 55 94 95 77 97 7 48 18 20 27 14 90 50 78 67 85 94 71

Improved path score: 1087 to 1104

Moves 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1

Steps 1 2 4 7 11 16 22 29 37 46 56 68 81 95 109 124 141 159

Score 55 94 95 77 97 7 48 18 20 27 14 90 48 80 84 85 94 71

Improved path score: 1104 to 1137

Moves 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1

Steps 1 2 4 7 11 16 22 29 37 46 57 68 80 93 108 124 141 159

Score 55 94 95 77 97 7 48 18 20 27 64 90 50 78 67 85 94 71

Improved path score: 1137 to 1154

Moves 1 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 1

Steps 1 2 4 7 11 16 22 29 37 46 57 68 81 95 109 124 141 159

Score 55 94 95 77 97 7 48 18 20 27 64 90 48 80 84 85 94 71

Improved path score: 1154 to 1193

Moves 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1

Steps 1 2 4 7 11 16 22 29 37 47 57 68 80 93 108 124 141 159

Score 55 94 95 77 97 7 48 18 20 83 64 90 50 78 67 85 94 71

Improved path score: 1193 to 1210

Moves 1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 1

Steps 1 2 4 7 11 16 22 29 37 47 57 68 81 95 109 124 141 159

Score 55 94 95 77 97 7 48 18 20 83 64 90 48 80 84 85 94 71

Improved path score: 1210 to 1249

Moves 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1

Steps 1 2 4 7 11 16 22 29 38 47 57 68 80 93 108 124 141 159

Score 55 94 95 77 97 7 48 18 76 83 64 90 50 78 67 85 94 71

Improved path score: 1249 to 1266

Moves 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1

Steps 1 2 4 7 11 16 22 29 38 47 57 68 81 95 109 124 141 159

Score 55 94 95 77 97 7 48 18 76 83 64 90 48 80 84 85 94 71

Improved path score: 1266 to 1303

Moves 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1

Steps 1 2 4 7 11 16 22 30 38 47 57 68 80 93 108 124 141 159

Score 55 94 95 77 97 7 48 72 76 83 64 90 50 78 67 85 94 71

Improved path score: 1303 to 1320

Moves 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 1

Steps 1 2 4 7 11 16 22 30 38 47 57 68 81 95 109 124 141 159

Score 55 94 95 77 97 7 48 72 76 83 64 90 48 80 84 85 94 71

1320 is the highest score.

</pre>