Day11.js

# advent-of-code

[joelpedraza]

Day11.js

Day11.js

[Joris PZ]

I have brute-forced part 2, knowing that there has to be a better way. I am positive you found it, but I just can't grasp the essence of your algorithm. Can you elaborate a bit about how you do it? (And how fast is your part 2?)

[joelpedraza]

The relation of partial sums in the comment is the key to understanding

[tarek]

The gist of the idea is explained by this data structure
https://en.wikipedia.org/wiki/Summed-area_table

[joelpedraza]

Consider a 4x4 grid of all 1s
gridOfPartialSums(4, 4) { _, _ -> 1 }

[joelpedraza]

Partial sum table looks like:

1, 2, 3, 4
 2, 4, 6, 8
 3, 6, 9,12
 4, 8,12,16

[joelpedraza]

My implementation has a leading row/col of zeros, to keep from having to do heroics with indices

0, 0, 0, 0, 0
 0, 1, 2, 3, 4
 0, 2, 4, 6, 8
 0, 3, 6, 9,12
 0, 4, 8,12,16

[joelpedraza]

Suppose you wanted the sum for the cell at 3,3 of size 1
9-6-6+4 = 1

[joelpedraza]

3,3 of size 2
9-3-3+1 = 4

[joelpedraza]

And so on

[joelpedraza]

As for perf, between 8 and 9 ms on my hardware

[Joris PZ]

Thanks, that is perfect

[littlelightcz]

Nice algorithm ... if my "home-made" solution doesn't end within 20minutes, I am going to try it out 😄