Day 11: Chronal Charge
Another one of those days where my initial attempt was good enough to solve part 1, but not fast enough to compute the part 2 solution in a reasonable time.
So I turned to the Internet, and I learned a little something new. Namely that by building a summed-area table you can easily compute the sum of values over any arbitrarily large rectangular area with only four lookups. So I gave it a shot and it was fast enough to be useable:
❯ raco test day11.rkt
raco test: (submod "day11.rkt" test)
cpu time: 272 real time: 273 gc time: 15
(time (day11-part1 (summed-area-grid))) = '(28 243 72 3)
cpu time: 14230 real time: 14246 gc time: 948
(time (day11-part2)) = '(74 229 192 11)
10 tests passed
Compare this to the claimed 20–70 msec times in C and Rust, and you can see why, despite claims to the contrary, I maintain that Racket has a performance ceiling that is about an order of magnitude lower than that of other languages.
Anyway, I learned a new math trick: summed-area tables! Fun problem.