Discussion on: AoC Day 11: Chronal Charge

[Anant Jain]

A speed up I can suggest: pre-compute another grid, say sumGrid where sumGrid[x][y] = sum(grid[i][j] where i is in range(x, N) and j in range(y, N)

So, each element in this new sumGrid is the sum of all elements below and right to it, including itself.

Then sum(x,y,size) is now just:

sum(x,y,size) = 
  sumGrid[x][y] 
  - sumGrid[x][y+size] 
  - sumGrid[x+size][y] 
  + sumGrid[x+size][y+size]

As an example, sum(3,2,5) would look like this:

We need to add that 4th last term sumGrid[x+size][y+size] since we have subtracted it twice as part of terms 2 and 3. The solution now avoids two inner for loops — making it much faster :)