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

require 'matrix'

class Matrix
  def summed_area_table
    return @sat if @sat
    rows = row_count
    cols = column_count

    sat = Matrix.zero(rows, cols).to_a

    rows.times do |x|
      cols.times do |y|
        a = self[x, y]

        b = sat.fetch(x - 1, []).fetch(y, 0)
        c = sat[x].fetch(y - 1, 0)

        d = x.zero? || y.zero? ? 0 : sat[x - 1][y - 1]

        sat[x][y] = a + b + c - d
      end
    end

    @sat = Matrix[*sat]
  end

  def summed_area(x0, y0, x1, y1)
    x0 = x0.zero? ? 0 : x0 - 1
    y0 = y0.zero? ? 0 : y0 - 1
    summed_area_table[x1, y1] +
      summed_area_table[x0, y0] -
      summed_area_table[x1, y0] -
      summed_area_table[x0, y1]
  end
end

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

[1] pry(main)> require './summed_area'
=> true

[2] pry(main)> m = Matrix.build(10000) { rand };    # It takes a several seconds to seed the 10,000 x 10,000 matrix

[3] pry(main)> m.summed_area(100, 100, 5555, 4444)  # The first time this takes some time as the SAT is built
=> 11852796.933710525

[4] pry(main)> m.summed_area(1020, 666, 8341, 9900) # And now the calculation is instant!
=> 33806690.016706355