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

Published on 12 May 2024 09:40 PM
#Autohotkey

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

Source code in the autohotkey programming language

data :=[
(join ltrim 
                 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
)]

i	:= data.MaxIndex()
row	:= Ceil((Sqrt(8*i+1) - 1) / 2)
path:=[]

loop % row {
	path[i] := data[i]
	i--
}

while i {
	row := Ceil((Sqrt(8*i+1) - 1) / 2)
	path[i] := data[i] "+" (data[i+row] > data[i+row+1] ? path[i+row] : path[i+row+1])
	data[i] += data[i+row] > data[i+row+1] ? data[i+row] : data[i+row+1]
	i --
}

MsgBox % data[1] "`n" path[1]

You may also check:How to resolve the algorithm Variables step by step in the 360 Assembly programming language
You may also check:How to resolve the algorithm Compare sorting algorithms' performance step by step in the Python programming language
You may also check:How to resolve the algorithm Greatest common divisor step by step in the CoffeeScript programming language
You may also check:How to resolve the algorithm Magnanimous numbers step by step in the AWK programming language
You may also check:How to resolve the algorithm Non-decimal radices/Input step by step in the C++ programming language