Day11.js

# advent-of-codej

joelpedraza

12/11/2018, 11:41 AMj

Joris PZ

12/11/2018, 12:08 PMI 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?)

j

joelpedraza

12/11/2018, 12:58 PMThe relation of partial sums in the comment is the key to understanding

t

tarek

12/11/2018, 1:06 PMThe gist of the idea is explained by this data structure
https://en.wikipedia.org/wiki/Summed-area_table

👍 3

j

joelpedraza

12/11/2018, 1:14 PMConsider a 4x4 grid of all 1s

`gridOfPartialSums(4, 4) { _, _ -> 1 }`

joelpedraza

12/11/2018, 1:14 PMPartial sum table looks like:

Copy code

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

joelpedraza

12/11/2018, 1:21 PMMy implementation has a leading row/col of zeros, to keep from having to do heroics with indices

Copy code

```
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

12/11/2018, 1:24 PMSuppose you wanted the sum for the cell at 3,3 of size 1
9-6-6+4 = 1

joelpedraza

12/11/2018, 1:25 PM3,3 of size 2
9-3-3+1 = 4

joelpedraza

12/11/2018, 1:25 PMAnd so on

joelpedraza

12/11/2018, 1:31 PMAs for perf, between 8 and 9 ms on my hardware

j

Joris PZ

12/11/2018, 2:13 PMThanks, that is perfect

l

littlelightcz

12/11/2018, 2:27 PMNice algorithm ... if my "home-made" solution doesn't end within 20minutes, I am going to try it out 😄

3 Views