Day 11 of the 2018 Advent of Code required you to generate a 300 x 300 matrix and then find
the 3 x 3 sub-matrix that had the largest value. Then part 2 required you to find the largest sub-matrix
of any size that had the maximum value. My first solution used a hash to map every entry in the
matrix. The keys were an [x,y]
array and the value was the value at that coordinate. Then by iterating over all rows
and columns I could check every 3 x 3 area and find the maximum value. This worked but wasn’t particularly fast (I believe the
complexity was O(N³)
).
But then I got to part 2 and I had to check more than just 3 x 3 areas and my implementation was too slow. So I implemented a new
solution using the Matrix
class and the minor
method so get the sub-matrix. You can see this implementation here.
In hindsight this wasn’t much faster then my first version I just guessed that the maximum area would be less than 20 x 20. One
thing I should have done was to track the maximum value for each square size and exit if it ever went down.
After solving it with a Matrix
I wanted to speed up mu implementation so I read some of the tips on reddit which led to
to the wikipedia article for
the summed-area table.
This is exactly what I needed!
A summed-area table is a data structure and algorithm for quickly and efficiently generating the sum of values in a rectangular subset of a grid.
I didn’t find a Ruby implementation so I decided to implement one for myself. First, here’s a visualization of what the summed-area table (SAT) looks like:
4x4 matrix SAT 1 0 6 5 1 1 7 12 4 8 6 7 --> 5 13 25 37 5 3 0 9 10 21 33 54 8 3 4 1 18 32 48 70
The formula for find the sum of the sub-matrix from (1, 1) to (2, 2) is then
sat[2, 2] + sat[0, 0] - sat[2, 0] - sat[0, 2]
which is
33 + 1 - 7 - 10 == 17
.
Since we are starting from the top left in this example, the value for any cell in the SAT is the sum of all the cells above and the left of the cell.
Since I’m working with matrices I opted to extend (monkey-patch) Matrix
with two methods: one for generating the summed-area table, the other to calculate an area.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
|
With this new class I was able to optimize my AOC solution and even though I knew that the size of the square in the answer for my input was 16 I still searched every possible size and it still performed faster than my original implementation. The code above for the summed-area calculation is also on github (with some optimizations that shave some time off SAT generation).
Usage example:
1 2 3 4 5 6 7 8 9 10 |
|