C Day\s11\sthoughts\sand\scomments
D 2018-12-17T04:57:15.745
E 2018-12-17T03:16:03 6df9dffadcf92ecb6e163adae43ffd3262b59594
N text/x-markdown
T +bgcolor * #c0f0ff
U joel
W 1398
Day 11: [Chronal Charge][1]

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][2] 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][3] in C and Rust, and you can see why, despite [claims to the contrary][4], 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.

[`day11.rkt`](file/day11.rkt)

[1]: https://adventofcode.com/2018/day/11
[2]: https://en.wikipedia.org/wiki/Summed-area_table
[3]: https://www.reddit.com/r/adventofcode/comments/a53r6i/2018_day_11_solutions/ebjogd7/
[4]: https://www.reddit.com/r/Racket/comments/9td40m/why_not_use_racket/e8voap5/
Z 5ad28963e33378a79c28bb40b88b9c36