' Euler problem no. 67
' Find the maximum total from top to bottom in "triangle.txt"...
' a 15K text file containing a triangle with one-hundred rows
' Big thanks to excellent explanation of the solution that you can find here:
' http://blog.functionalfun.net/2008/08/project-euler-problems-18-and-67.html
ArSize = 15 'max = 100 for triangle.txt, set it to i.e. 10 to see only for top 10 rows of the triangle
path = "D:\Moje Dokumenty\SmallBasic\MARCIN\Triangle.txt" ' path to triangle.txt file (enter accordingly)
MaxVal=0 ' reset initial value
' populate the ArrA triangle - import it from file row by row (depends how many rows you want to solve)
For ai = 1 To ArSize
' The following line could be harmful and has been automatically commented.
' Atxtline = File.ReadLine(path, ai) ' read the file line by line (row by row)
For aj = 1 To ai ' column by column within the row (ai)
ATempVal = Text.GetSubText(Atxtline,(aj - 1) * 3+1,2) ' substract numbers from the row just read
ijpos = ai + "," + aj ' set the position [i,j]
Array.SetValue("ArrA",ijpos,ATempVal) ' put the number to the table
EndFor
EndFor
TextWindow.WriteLine("") '- for table printing, set the new row after whole triangle
' populating ArrMA triangle - this is exact solution part
For ai = 1 To ArSize
For aj = 1 To ai
ijpos = ai + "," + aj
im1jpos = (ai-1) + "," + aj 'set the position [i-1,j] - up-right number on the triangle
im1jm1pos = (ai-1) + "," + (aj-1) 'set the position [i-1;j-1] - up-left number on the triangle
MaxOf2 = Math.Max(Array.GetValue("ArrMA",im1jpos),Array.GetValue("ArrMA",im1jm1pos))
ValMA = Array.GetValue("ArrA",ijpos) + MaxOf2
'ValMA is the sum of corresponding number in ArrA triangle and the higher of 2 values above it in ArrMA table (MaxOf2)
Array.SetValue("ArrMA",ijpos,ValMA) ' put the number to the table
CheckMaxVal() 'verify if value of sums is the max up to now
EndFor
EndFor
TextWindow.Writeline("")
TextWindow.Writeline("The maximum total from top to row no. " + ArSize +" in triangle.txt is: "+ MaxVal)
FindMaxPath() ' Must be executed AFTER finding the MaxVal for the triangle !!! Not required for the problem solving
' used for drawing the path leading to result value
'---------------------------------------
Sub CheckMaxVal
If ValMA > MaxVal Then 'if new MaxValue found then keep it as MaxVal
MaxVal = ValMA
MaxJPos = aj
EndIf
EndSub
'---------------------------------------
Sub FindMaxPath ' Must be executed AFTER finding the MaxVal for the triangle !!! Not required for the problem solving
For ai = ArSize To 1 Step -1 'check backward the max path, starting from MaxVal
Array.SetValue("MaxPath",ai,MaxJPos) 'put the j position of max value to the MaxPath array
If Max2 = Array.GetValue("ArrMA",im1jpos) Then 'check which one of parents is higher to store it as next MaxJPos
MaxJPos = MaxJPos
Else
MaxJPos = MaxJPos-1
EndIf
EndFor
TrName = "ArrA"
PrintPathTriangle()
TextWindow.WriteLine("Press any key to see the triangle with sub sums leading to the maximum total:")
TextWindow.PauseWithoutMessage()
TrName = "ArrMA"
PrintPathTriangle()
EndSub
'---------------------------------------
Sub PrintPathTriangle ' print the triangle with the max sum path
For ni = 1 To ArSize 'row by row
If ArSize<16 Then ' An attempt to place the triangle right :), skip it for more than 15 rows
For SpNo = (ArSize-ni) To 0 Step -1
TextWindow.Write(" ")
EndFor
EndIf
For nj = 1 To ni ' column by column
ijpos = ni + "," + nj ' set the position [i,j]
If nj = Array.GetValue("MaxPath", ni) Then
TextWindow.ForegroundColor = "Red" 'mark the number if leads to next max sum number
EndIf
PrintNumber() ' print next number of the triangle
TextWindow.ForegroundColor = "Gray" ' turn off highlightning the number
EndFor
TextWindow.WriteLine("") '- for table printing, set the new row after last column of previous one
EndFor
TextWindow.WriteLine("") '- for table printing, set the empty row
EndSub
'---------------------------------------
Sub PrintNumber
TextWindow.Write(Array.Getvalue(TrName,ijpos)+" ") '- for table printing, write the array numbers, separate with space
Program Listing: NXP803