I recently encountered a difficult programming challenge which deals with getting the largest or smallest sum within a matrix. There are several variations of this type of problem, but the challenges are similar in each. Take for example the following triangle:
Some of these problems involve a grid, rather than a triangle, but the concept is similar. In the above example, moving from the top (3) to the bottom, what is the largest path sum? The reason that this problem can be so challenging is because with larger matrices or triangles, the brute force approach is impossible. The natural instinct, at least for me, is to start at the top, and work my way down. Basically you would be solving it, by choosing the best path from the top to the bottom, like this:
However, this approach would require not only choosing the largest number at each intersection, but also comparing this choice to choices below your current position. For example, if the current largest choice is a 7, but going this path to the bottom eliminates higher numbers in an adjacent path, I would need to compare both paths to see which has a greater value. With a small triangle like this, of course that’s possible, but with a much larger one, it’s not so easy. For instance, let’s imagine that instead of four rows, the triangle had 100 rows. It would not be possible to try every route to solve this problem, as there would be 2⁹⁹ altogether! If you could check one trillion (10¹²) routes every second it would take over twenty billion years to check them all. So what I set out to do was solve the triangle problem in a way that would work for any size of triangle. Even with a good algorithm, hard coding a function for 100 rows would be quite time consuming. But let’s not get ahead of ourselves.
Dynamic Programming:
The basic concept for this method of solving similar problems is to start at the bottom and work your way up.
Step 1:
We’ll start by taking the bottom row, and adding each number to the row above it, as follows:
Step 2:
Now, we’ll replace the second to last row with the largest sums from the previous step, as follows:
Step 3:
Now, we repeat step 1, adding the bottom row to the row above it.
Step 4:
We’ll repeat step 2, replacing the second row with the largest sums from the last row.
Step 5:
Now we’re left with only three numbers, and we simply take the largest sum from rows 1 and 2, which in this case leaves us with 23.
Now, as I mentioned earlier, I wanted to write a function that would solve this problem, regardless of the triangle size. Here’s my thought process on how to do that:
If my triangle is an array of numbers, I only want to deal with the very last number, the second to last number, and then the number on the row above it. I’ll figure out the greatest sum of that group, and then delete the last two numbers off the end of each row. But the largest sum, I’ll push into a temporary array, as well as deleting it from the current array. Now, I can repeat the same step with a new group of three numbers, since the previous numbers have been deleted and now the ending array numbers are new. If at any point, my last row has a length of 0, I’ll substitute the last row for the temporary array I created. This way, The function will always cycle through, regardless of the size of the triangle. Visually, here’s how that might look:
At this point, after I get the sum of 2 and 8, as well as 2 and 5, I no longer need this group. My last row would have a length of zero, so step 4 would be to substitute the last row for the tempArr:
My thinking is that to get started, I’ll usually have an array, but in order to make it simpler, I want each row to be it’s own array inside a larger array container. In order to do this, I create a function first that takes whatever triangle size I’m given, and breaks it up into separate arrays. In this case, I know I’ll need four rows. So with larger arrays I can change the rows needed if I’m given a larger triangle to start with:
arr = [3, 7, 4, 2, 4, 6, 8, 5, 9, 3]arr2 = []start = 0endVar = 1end = 1while len(arr2) is not 4:arr2.append(arr[start:end])start = endendVar = endVar + 1end = end + endVar
Basically, as long as my array doesn’t have 4 rows (sub arrays), it continues to execute the while loop. It starts at zero, and ends with 1, then I push that group into the array. Then, the new starting group becomes the end of the last group. To determine the end of the second group, I have an endVar which I increment at every loop. The ending of each group will just be the end variable plus the endVar variable.
After executing, I should end up with a structure that looks like the following:
[[3], [7, 4], [2, 4, 6], [8, 5, 9, 3]]
Now, I’ll loop over these and do some magic. First off:
tempArr = []while len(arr2) is not 1:# --- Do stuff -----
The condition to break my while loop will be that the array length is not 1. If it is 1, then obviously, I’ve found my answer, and the loop will stop, as that number should be the maximum sum path. And the tempArr will store the maximum sum of each row.
The first order of business is just to figure out which of the two ending array element sums is greatest. Here’s how I’ll do that:
tempArr = []while len(arr2) is not 1:if arr2[-2][-1] + arr2[-1][-1] > arr2[-2][-1] + arr2[-1][-2]:arr2[-2][-1] = arr2[-2][-1] + arr2[-1][-1]else:arr2[-2][-1] = arr2[-2][-1] + arr2[-1][-2]
At this point, I’ve set the value of the array element on the next to last row at the end. Now, I can delete both elements from the end of each array, and push the sum into the tempArr.
tempArr = []while len(arr2) is not 1:if arr2[-2][-1] + arr2[-1][-1] > arr2[-2][-1] + arr2[-1][-2]:arr2[-2][-1] = arr2[-2][-1] + arr2[-1][-1]else:arr2[-2][-1] = arr2[-2][-1] + arr2[-1][-2]tempArr.insert(0, arr2[-2][-1])del arr2[-1][-1]del arr2[-2][-1]
Now, we will end up with a problem here, where eventually the next to last row will be an empty array and will break our function. We’re only deleting the values in the array, and not the array itself. So, I want to add a condition that will delete the array altogether if the length of the array ever reaches zero.
tempArr = []while len(arr2) is not 1:if arr2[-2][-1] + arr2[-1][-1] > arr2[-2][-1] + arr2[-1][-2]:arr2[-2][-1] = arr2[-2][-1] + arr2[-1][-1]else:arr2[-2][-1] = arr2[-2][-1] + arr2[-1][-2]tempArr.insert(0, arr2[-2][-1])del arr2[-1][-1]del arr2[-2][-1]if len(arr2[-2]) == 0:arr2[-1] = tempArrdel arr2[-2]
This works pretty good. But due to my lack of math skills, I ran into a problem. Once the array becomes a length of 2, it stops working. I could spend another 30 minutes trying to finesse it. But I’m lazy. So I added an if statement at the beginning that catches the error. If the length of the container array is ever a length of 2, it just takes the max value of the bottom array, and adds it to the top array. And I save it as a new variable I created called ‘total’. And this should be my maximum sum path.
total = 0tempArr = []
print arr2while len(arr2) is not 1:if len(arr2) == 2:print max(arr2[-1])print arr2[0][0]total = max(arr2[-1]) + arr2[0][0]if arr2[-2][-1] + arr2[-1][-1] > arr2[-2][-1] + arr2[-1][-2]:arr2[-2][-1] = arr2[-2][-1] + arr2[-1][-1]else:arr2[-2][-1] = arr2[-2][-1] + arr2[-1][-2]tempArr.insert(0, arr2[-2][-1])del arr2[-1][-1]del arr2[-2][-1]if len(arr2[-2]) == 0:arr2[-1] = tempArrdel arr2[-2]print arr2print tempArrprint total
Below is how python executes the while loop, and what is contained in each array through each iteration of the loop:
arr2 (starting): [[3], [7, 4], [2, 4, 6], [8, 5, 9, 3]]arr2 (after first pass): [[3], [7, 4], [2, 4], [8, 5, 9]]tempArr: [15]arr2 (after second pass): [[3], [7, 4], [2], [8, 5]]tempArr: [13, 15]arr2 (after third pass): [[3], [7, 4], [10, 13, 15]]tempArr: [10, 13, 15]arr2 (after fourth pass): [[3], [7], [19, 10, 13]]tempArr: [19, 10, 13]arr2 (after fifth pass): [[3], [20, 19, 10]]tempArr: [20, 19, 10]max value : 20remaining array value: 3total: 23
Anyway, I hope this has been helpful. Let me know if you have any feedback. Thanks!