This is part of a series of posts, starting with Advent of Code 2019 in 130 ms: introduction.

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.

The program runs in three phases: collect all the items, navigate to the security room, and then crack the item combination.

The collection phase is done using a depth-first search, keeping track of unexplored rooms in a stack. Whenever we find an item, we pick it up unless it’s on a hardcoded list of “bad items”. I haven’t thought of a good way to detect the bad items automatically, since they have several different effects - it seems like you’d need special-purpose code for some of them anyway, so it’s easier to just hardcode them. Anyway, when we encounter the security room, we start tracking the path to get back there using a second stack of moves. Once there are no more unexplored rooms, we move to the navigation state.

In the navigation state, we simply follow the security room move stack to get back to the security room in the minimum number of moves. Once there, we move to the unlock state.

In the unlock state, we try item combinations until we win the game. We start by holding all items, and then drop and pick up items in different combinations. Since each attempt requires one call to the Intcode program, we can save a lot of time with a good strategy. One way we can do this is by minimizing the number of times we need to drop or pick up an item. We can encode the items we’re holding as a binary number, where each digit represents whether we’re holding one item. We can then repeatedly increment this number to iterate through all combinations of items.

To reduce the number of attempts we need, we can make use of the fact that the game tells us if we’re holding too much or too little weight. We don’t know how much each item weighs, but we can still keep track of the combinations we’ve tried. If the next combination contains all items of a combination we know was too heavy, we can just skip it because we know it will definitely also be too heavy. Likewise, if the next combination is a subset of a combination we know was too light, we can skip that too. This saves about 75% runtime for my puzzle input.

Lastly, we can be a bit smarter with how we iterate through attempts. To minimize the number of items we need to drop or pick up, we want to change as few bits of our combination number as possible between attempts. To do that, we can represent the held items as Gray code. This is a binary code where successive numbers differ only by one bit, which is exactly what we want. This benefit is diminished a bit by skipping redundant attempts, but still helps. If we also start by holding half the items instead of all of them - so we can make better use of both the “too light” and “too heavy” information - this saves an additional 44% runtime. All in all, these optimizations bring us down to 5.7 ms total.