-
Advent of Code 2019 in 110 ms: optimizing Intcode
Read moreI 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.
-
Advent of Code 2019 in 110 ms: day 3 revisited
Read moreAfter 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.
-
Advent of Code 2019 in 130 ms: closing thoughts
Read moreAnd 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.
-
Advent of Code 2019 in 130 ms: day 25
Read moreDay 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.
-
Advent of Code 2019 in 130 ms: day 24
Read moreDay 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.
-
Advent of Code 2019 in 130 ms: days 20 - 23
Read moreDay 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.
-
Advent of Code 2019 in 130 ms: day 19
Read moreDay 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.
-
Advent of Code 2019 in 130 ms: day 18
Read moreDay 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.
-
Advent of Code 2019 in 130 ms: day 17
Read moreDay 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.
-
Advent of Code 2019 in 130 ms: day 16
Read moreDay 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!