Day 11 thoughts and comments

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]:
[2]:
[3]:
[4]: