• Advent of Code 2019 in 110 ms: optimizing Intcode

    I realize that throughout the previous posts I promised to get back to performance optimization for the Intcode engine, but never did. This is mostly due to how these optimizations are very language- and implementation specific, which didn’t fit well with the algorithmic focus of the rest of the series. But in the interest of completeness, I’ll go through that here.

    Read more
  • Advent of Code 2019 in 110 ms: day 3 revisited

    After I posted this series to the Advent of Code subreddit, Reddit user askalski - who has previously posted optimized solutions in C and C++, and was one of my inspirations for doing the same - suggested a better solution for day 3: processing the wires as line segments instead of point sets. This reduces runtime by 99.9%, down to 28 μs.

    Read more
  • Advent of Code 2019 in 130 ms: closing thoughts

    And so this series of posts comes to a close. I hope I was able to help you learn something - I certainly did while developing these solutions. Even writing these posts, as I went through the solutions again I found an additional 34 ms of time save even after I’d decided that 164 ms was a good enough time to settle on.

    Read more
  • Advent of Code 2019 in 130 ms: day 25

    Day 25: Cryostasis

    The final challenge is a text-based adventure game in Intcode, and much like previous Intcode challenges benefits a lot from minimizing the amount of Intcode you need to run. My solution runs in 5.7 ms, using an initial depth-first search phase and then making use of Gray code to minimize the number of inventory changes while cracking the combination for the lock.

    Read more
  • Advent of Code 2019 in 130 ms: day 24

    Day 24: Planet of Discord

    Day 24 is a variant of Conway’s game of life. My solution runs in 2.6 ms and gains its performance from efficient data structures, including a custom bit field representation of Boolean matrices similar to the key sets in day 18.

    Read more
  • Advent of Code 2019 in 130 ms: days 20 - 23

    Day 20: Donut Maze

    Day 20 is a maze problem similar to day 18. My solution runs in 11 ms and uses the same performance tricks. The only real difference is in the rules for generating new states, and that this solution doesn’t use custom duplication keys since the keys for the hash set of visited locations are already quite small.

    Read more
  • Advent of Code 2019 in 130 ms: day 19

    Day 19: Tractor Beam

    Day 19 is another Intcode challenge, and in terms of performance optimization it is much like day 15 in that the focus is on minimizing the number of calls to the Intcode program. My solution uses linear approximation followed by binary search, and runs in 1.3 ms.

    Read more
  • Advent of Code 2019 in 130 ms: day 18

    Day 18: Many-Worlds Interpretation

    Challenge 18 also took quite a bit of effort to optimize. Basically, it’s a maze optimization problem, but with the added twist that you need to collect keys to open doors, and in part 2 you’re exploring 4 partitions of the map in parallel.

    Read more
  • Advent of Code 2019 in 130 ms: day 17

    Day 17: Set and Forget

    Day 17 is an interesting exercise in sequence compression, but the runtime optimization of my solution, running in 1.9 ms, is more about implementation efficiency and a fast Intcode engine than about algorithmic sophistication.

    Read more
  • Advent of Code 2019 in 130 ms: day 16

    Day 16: Flawed Frequency Transmission

    Challenge 16 is probably the one I’ve spent the most time on optimizing, but my solution still takes 8.6 ms to run. There’s quite a lot to unpack here, so this one gets a whole post of its own!

    Read more

All posts