Euler Problem 83
Euler Problem 83 asks:
NOTE: This problem is a significantly more challenging version of Problem 81.
In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in red and is equal to 2297.
131 673 234 103 18 201 96 342 965 150 630 803 746 422 111 537 699 497 121 956 805 732 524 37 331Find the minimal path sum, in matrix.txt (right click and 'Save Link/Target As...'), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by moving left, right, up, and down.
In the Problem 123 thread Doug Jenkins provided a spreadsheet solution for Problem 83, as well as suggesting an alternate method to solve the problem by padding the matrix. He thereby relieved a huge mental block of mine, but it's in the wrong thread. So I started this one.
Padding the matrix has its advantage. It allows you to use a common relationship in the area of interest without having to worry about variable subscripts being out of range because you'd otherwise reference a row or column that you haven't dimensioned (akin to trying to reference Row(0) on a spreadsheet.) There's some overhead to do this, but it saves special cases at the corners and borders. Doug recommended using 1000000, and that's as good a choice as any. With that in mind, the above matrix comes to look like this:
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 131 673 234 103 18 1000000 1000000 201 96 342 965 150 1000000 1000000 630 803 746 422 111 1000000 1000000 537 699 497 121 956 1000000 1000000 805 732 524 37 331 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000
Since a picture = 1 kiloword, you can see how we have slop all the way around for subscripts, with the added advantage that if you make the matrix zero-based, the action starts at Row(1), Column(1). My mind likes it better that way. I used this same padding trick for Problem 67, where you can turn a triangle into a square. It really simplifies the code. With all that for background, here is my code that turns Doug's spreadsheet solution into VBA. It runs in about 3/10's of a second.
Dim Matrix(0 To 81) As Variant
Dim Cell(0 To 81, 0 To 81) As Long
Dim R As Long, C As Long
Dim Min As Long
Dim Answer As Long, T As Single
Dim TEMP1 As Long, TEMP2 As Long
Dim NumRows As Long, NumCols As Long
Dim IsTest As Boolean, i As Long
Const text As String = "D:\Downloads\Euler\matrix.txt"
T = Timer
R = 1
Open text For Input As #1 '80 lines, comma delimited
Do While Not EOF(1)
Line Input #1, Matrix(R) 'fills rows 1 to 80; 0 and 81 come later
R = R + 1
Loop
Close #1
IsTest = False
If IsTest Then
NumRows = 6
NumCols = 6
Matrix(1) = "131,673,234,103,18"
Matrix(2) = "201,96,342,965,150"
Matrix(3) = "630,803,746,422,111"
Matrix(4) = "537,699,497,121,956"
Matrix(5) = "805,732,524,37,331"
Else
NumRows = 81
NumCols = 81
End If
For C = 1 To NumCols - 1
Matrix(0) = Matrix(0) & "1000000 "
'adds top padding @(0), sets up TRIM()
Next C
Matrix(0) = Replace(Trim(Matrix(0)), " ", ",") 'makes it comma-delimited
Matrix(NumRows) = Matrix(0) ' adds bottom padding @(NumRows)
For R = 0 To NumRows
Matrix(R) = "1000000," & Matrix(R) & ",1000000"
' pads all rows left and right
Matrix(R) = Split(Matrix(R), ",")
'makes a zero-based NumRows X NumCols matrix
Next R
For R = 0 To NumRows
For C = 0 To NumCols
Cell(R, C) = CLng(Matrix(R)(C))
If C GT 0 Then Cell(R, C) = Cell(R, C) + Cell(R, C - 1)
' seeds the Cell array
Next C
Next R
Do
TEMP1 = Cell(NumRows - 1, NumCols - 1)
'start value of unpadded LR corner
i = i + 1 'counts iterations
For R = 1 To NumRows - 1 'inside the padding
For C = 1 To NumCols - 1 'inside the padding
If R = 1 And C = 1 Then 'reset Cell(1,1) from above
Cell(R, C) = CLng(Matrix(R)(C))
Else 'do the hard work
Min = Application.WorksheetFunction.Min(Cell(R + 1, C), Cell(R - 1, C), _
Cell(R, C + 1), Cell(R, C - 1))
Cell(R, C) = CLng(Matrix(R)(C)) + Min
End If
Next C
Next R
TEMP2 = Cell(NumRows - 1, NumCols - 1)
'finish value of unpadded LR corner
If i GT NumRows * NumCols Then Exit Do 'escape clause
Loop Until TEMP1 = TEMP2 'stable when start = finish
Answer = Cell(NumRows - 1, NumCols - 1)
Debug.Print Answer; " Time:"; Timer - T, i
End Sub
Doug mentions seeding the Cell array. This makes a huge difference. It goes through the Do-Loop only 5 times. The answer is known after 4 loops, but it takes 5 for the starting TEMP1 to know it. I couldn't figure out how to avoid that without apriori knowledge of the Answer, which is in the bottom right cell before the padding.
Playing with the spreadsheet solution, I made a third matrix of the array by "pasting special" a copy when all is stable. Then with conditional formatting comparing the two, I could see how the data flows and settles as I stepped through it. It starts from the upper left in kind of a maple-leaf pattern: Strong down the middle, with a spike above and below, and then a weak spike down the left side and the top edge. It takes 11 reps for everything to stabilize.
So, all in all, this is my VBA for Doug's concept. Stephen B and Josh G have other approaches, and hopefully, they'll share. This code is the combination of two half-good ideas I had. Maybe Doug will chime in, too. He's the one who gave me the clue about the whole approach.
The usual angle bracket corrections are in the code. It's interesting that it's Cell(R,C) but Matrix (R)(C) for the syntax.
...mrt

