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

Published on 12 May 2024 09:40 PM
#Nim

How to resolve the algorithm Maximum triangle path sum step by step in the Nim 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 Nim programming language

Source code in the nim programming language

import sequtils, strutils, sugar

proc solve(tri: seq[seq[int]]): int =
  var tri = tri
  while tri.len > 1:
    let t0 = tri.pop
    for i, t in tri[tri.high]: tri[tri.high][i] = max(t0[i], t0[i+1]) + t
  tri[0][0]

const data = """
                          55
                        94 48
                       95 30 96
                     77 71 26 67
                    97 13 76 38 45
                  07 36 79 16 37 68
                 48 07 09 18 70 26 06
               18 72 79 46 59 79 29 90
              20 76 87 11 32 07 07 49 18
            27 83 58 35 71 11 25 57 29 85
           14 64 36 96 27 11 58 56 92 18 55
         02 90 03 60 48 49 41 46 33 36 47 23
        92 50 48 02 36 59 42 79 72 20 82 77 42
      56 78 38 80 39 75 02 71 66 66 01 03 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 01 01 99 89 52
  06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15
27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93"""

echo solve data.splitLines.map((x: string) => x.strip.split.map parseInt)

You may also check:How to resolve the algorithm Truncatable primes step by step in the C# programming language
You may also check:How to resolve the algorithm ASCII art diagram converter step by step in the Wren programming language
You may also check:How to resolve the algorithm Terminal control/Cursor positioning step by step in the Kotlin programming language
You may also check:How to resolve the algorithm Knapsack problem/Continuous step by step in the BBC BASIC programming language
You may also check:How to resolve the algorithm Create an HTML table step by step in the Euphoria programming language