Day 14: Chocolate Charts
For a while it looked to me like Racket was not up to the job on this one. My initial attempt using a list for the recipes passed all the example inputs/tests, but ran far too slowly even to complete part 1. I then rewrote the code to use the list in reverse order, eliminating any use of append in favor of cons; still too slow!
With company over and the house overrun with children, I had only a minute here and there to think this through. I then hit upon the idea of just starting with a 50,000,000-element vector and vector-set!ing the values as I go along. This approach ultimately got me over the finish line for both parts. (In case it’s not obvious, AoC 2018 is the first time I’ve really grappled with optimizing Racket code for speed.)
There were other small optimizations along the way as well; for example the append-recipes! function takes advantage of the fact that the maximum value it will ever encounter is 18, and so avoids number->string conversion in favor of simple math. For part 2, the found-yet? function takes advantage of for/and to compare sequences one element at a time and bail on the first mismatched element.
Speed results for day14.rkt as of 80485b:
❯ raco test day14.rkt
raco test: (submod "day14.rkt" test)
1
2
cpu time: 1 real time: 2 gc time: 0
cpu time: 0 real time: 0 gc time: 0
cpu time: 0 real time: 0 gc time: 0
cpu time: 0 real time: 0 gc time: 0
cpu time: 50 real time: 51 gc time: 0 <-- Part 1
cpu time: 4835 real time: 4892 gc time: 2135 <-- Part 2
6 tests passed