Microsoft Small Basic

Program Listing:

' 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

    im1jpos = (ai-1) + "," + MaxJPos
    im1jm1pos = (ai-1) + "," + (MaxJPos-1)

    Max2 = math.Max(Array.GetValue("ArrMA",im1jpos),Array.GetValue("ArrMA",im1jm1pos))


    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

EndSub