Advent of Code 2020: Day 14
, 9 min readadvent of code 2020
Part 1
As your ferry approaches the seaport, the captain asks for your help again. The computer system that runs this port isn’t compatible with the docking program on the ferry, so the docking parameters aren’t being correctly initialized in the docking program’s memory.
After a brief inspection, you discover that the sea port’s computer system uses a strange bitmask system in its initialization program. Although you don’t have the correct decoder chip handy, you can emulate it in software!
The initialization program (your puzzle input) can either update the bitmask or write a value to memory. Values and memory addresses are both 36-bit unsigned integers. For example, ignoring bitmasks for a moment, a line like mem[8] = 11 would write the value 11 to memory address 8.
The bitmask is always given as a string of 36 bits, written with the most significant bit (representing 2^35) on the left and the least significant bit (2^0, that is, the 1s bit) on the right. The current bitmask is applied to values immediately before they are written to memory: a 0 or 1 overwrites the corresponding bit in the value. At the same time, an X leaves the bit in the value unchanged.
Execute the initialization program. What is the sum of all values left in memory after it completes?
You can read the full text here. Phew, this looks a little easier than yesterdays puzzle. As always, we need to start by processing the input. The input is made up of many lines, but they are in the form of one of the following:
|
|
or,
|
|
Since we can express the pattern of these lines so simply, we can very conveniently turn these into regex patterns,
|
|
Where we are just saying line one is “mask = " followed by a sequence of X’s, 0’s and 1’s. Then the other possible line is similar, except the tokens we want are both numbers. We don’t specify how many digits are in the numbers; instead, we use the “+” symbol to tell the pattern to expand and include all of the digits.
For part 1 we need to use the mask to vary the bits in the numbers we read in before we store them. For this I’m separating the input mask into two numbers, which I’m calling or_mask
and and_mask
for reasons that should become clear.
|
|
We load up each line, if the second character is an ‘a’ then we know that the line is a mask. We start by setting all the bits in the or_mask
to zero, and all the bits to 1 in the and_mask
. We then loop over the mask setting or_mask
bits to 1 if the string mask is 1, and 0 for the and_mask
.
For the example mask below outputs:
|
|
This means we can take a number, and apply the mask using (num | or_mask) & (and_mask)
. This does the following:
|
|
first we do the or
,
|
|
and then the and
,
|
|
This may take some time to digest, but this process ensures that any bit that is 1 in the mask, or 1 in the number will be 1 at the end, hence the name. However, the second part ensures that a bit must set in both the number and the mask. I hope that I have explained this is semi-useful way, if not, please get in touch and I can attempt to improve this section.
Now that we have a process to read in the mask, and store it into a useable format, we just need to loop over all the numbers and store them in memory. As the input file shows the memory is quite sparse, i.e. very few of the indices are filled, we’re using a map
in the emulator.
|
|
We use the regex pattern from before to extract the two numbers from the input line, then apply the mask to the number and store it at index num1
. Well not quite, as the input is sparse we store the data with a key, num1
inside a map
thus saving a lot of wasted memory.
Finally, all we need to do is loop over the map
and sum all of the masked values.
|
|
There we go, the first ⭐!
Part 2
For some reason, the sea port’s computer system still can’t communicate with your ferry’s docking program. It must be using version 2 of the decoder chip!
A version 2 decoder chip doesn’t modify the values being written at all. Instead, it acts as a memory address decoder. Immediately before a value is written to memory, each bit in the bitmask modifies the corresponding bit of the destination memory address in the following way:
|
|
A floating bit is not connected to anything and instead fluctuates unpredictably. In practice, this means the floating bits will take on all possible values, potentially causing many memory addresses to be written all at once!
You can read the full text here. Argh! Now instead of applying the mask to the number we are storing we must apply the mask to the address. Ok - that is very easy, but
now the X’s mean that a bit can take any value. Thus, instead of 1 address, each mask will produce 2^M
addresses, where M
is the number of X’s in the mask.
We’re going to slightly modify the input code from before to keep track of which bits in the mask are Xs, e.g. add the following,
|
|
This time we can ignore the 0s in the mask as the puzzle input states that they do not change the address. Consider the following example:
|
|
We first apply the or_mask
as before,
|
|
but then we need to take into account the either mask, e.g.,
|
|
where each X
can be 0 or 1. To consider every possibility I start with both X’s as zero, which is achieved with the following,
|
|
Feel free to take some time to understand why that works. I’m using the ~
operator to get the compliment of the either_mask
which would be,
|
|
then I store it in a vector
. Then we loop through the X’s and turn them on, one a time, generating every possible combination and storing them,
|
|
Now we have all the possible addresses stored, we can then store the value in map
, e.g. our sparse memory block,
|
|
As with part 1, we just loop through and sum the value of the sparse memory at the end, and there we go, ⭐⭐! If you aren’t familiar with bit manipulation then this may be confusing, so please feel free to reach out and ask for help. I generally benefit from messing around with bit operations in an interactive python terminal.
Reflections
Today’s problem was a fun one, I’ve been intending to work on my bit manipulation problem-solving. I’m generally able to solve these types of puzzles. Still, I don’t always feel comfortable, and I rarely find the optimal solution. I’ll be looking through other peoples code to see what I could have improved today. I think my code is quite readable today, and I think I chose good variable names which reduced confusion.
The complexity of the first part of the problem is O(N)
-time and space. The space complexity would be a lot worse had we not used a map
. Using an array would have caused the memory to scale with the maximum value, which is a lot larger than N
.
For the second part my solution is again O(N)
-time and space complexity. However, for inputs with small N
, each with lots X
the memory would be dominated by 2^M
where M
is the number of X
’s in an input.
I’m assuming my map
lookup is O(1)
, which is not currently true but can be achieved with an unordered_map
.
I have no affiliation with AoC. I’m just a fan of the programming puzzles. If you enjoy them too, please feel free to join in and support the creators