Advent of Code 2020 - Day 14

This is a running series of posts on the Advent of Code 2020. The introductory post has the details, including the accompanying GitHub repo, in case you reached this directly.

This exercise is another software emulator. The input is a sequence of commands either specifying a mask or a write instruction consisting of address and value. The parsing is pretty simple as the format is very strict. We can easily write a generator to loop over the (parsed) instructions, prepending a command identifier to indicate if it's a mask or memory instruction.

Part 1

Since the writing will be rather sparse, we will use a dictionary to represent the memory, keeping track only of accessed addresses (the keys).

Whenever a memory instruction indicates to write a value into an address, the mask must be applied to the value first. The mask overwrites bits with 0 or 1 as indicated in the mask, leaving the positions marked with X unaltered.

Since Python treats ints with exactly the binary representation required for this, we can just transform the mask to do the work with a couple of bitwise logical operations. To set the ones, we can consider all Xs as zero and apply a bitwise or to the value. To set the zeros, we can consider all Xs as one and apply a bitwise and to the value.

If we call these the or-mask and the and-mask, respectively, we can update them with each mask command (using the built-in string.translate, then reading that as a binary int), and simply apply them in the memory commands transforming the value into (value & and_mask) | or_mask.

After processing all commands we just add up the values in the memory to get the requested answer.

Part 2

This part changes the behaviour. Now values are not modified, instead the mask is applied to the address. The application also changes: zeros leave the bit unchanged, ones set the bit to one (up to here is the bitwise or with the Xs as zeros), and the X bits take both possible values, resulting in multiple addresses (all potential combinations).

This means that we can take the original address and apply the or-mask. Then we apply a modified version of the and-mask: in this case we set the Xs to zeros as before, but also the zeros in the mask to ones (to avoid setting those zeros, that no longer applies). This gives us our base address, where every X bit is zero, and the rest are set to the proper values.

Now we need to efficiently generate all combinations of zeros and ones for the X bits. We start by building a list of switches, the corresponding integer value of each X bit. Adding zero, one, or more of the switches to the base address (as integers) will work exactly as flipping the corresponding bits. So we just need to return the base address with all combinations of zero switches (that's the base address), then adding each one-switch combination, then adding each two-switch combination, and so on until we return the base address plus the last, all-switches combination. Instead of manually building all the combinations, we take advantage of the combinations function in the itertools module to do it: very efficient, zero mistakes. Don't reinvent the wheel.

Now it's just a matter of updating the memory, writing the value to each of this addresses, and adding up the memory at the end.

I almost expected that this would not be quite efficient enough and that some smarter approach to register the patterns of Xs would be needed, but the masks are not too X-heavy, so it works out. I'm guessing that's intentional.