Advent of Code 2020: Day 14

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:

1

mask = XXX01XX0..

or,

1

mem[XXX] = YYY

Since we can express the pattern of these lines so simply, we can very conveniently turn these into regex patterns,

1
2

const std::regex reg1("mask = ([X0-1]+)");
const std::regex reg2("mem\\[([0-9]+)] = ([0-9]+)");

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

if (line[1] == 'a') {
    // Reload the mask
    std::regex_search(line, pieces_match, reg1);
    std::string mask = pieces_match[1];
    // Make or + and components
    or_mask = 0;
    and_mask = ~or_mask;
    for (size_t i = 0; i < mask.size(); i++) {
        if (mask[mask.size() - 1 - i] == '1')
            or_mask += (one << i);
        else if (mask[mask.size() - 1 - i] == '0')
            and_mask -= (one << i);
    }
}

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:

1
2
3

mask = XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
or   = 000000000000000000000000000001000000
and  = 111111111111111111111111111111111101

This means we can take a number, and apply the mask using (num | or_mask) & (and_mask). This does the following:

1

num = 000000000000000000000000000000001011

first we do the or,

1
2
3

num = 000000000000000000000000000000001011
or  = 000000000000000000000000000001000000
    = 000000000000000000000000000001001011

and then the and,

1
2
3

      000000000000000000000000000001001011
and = 111111111111111111111111111111111101
    = 000000000000000000000000000001001001

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.

1
2
3
4
5
6

const std::regex reg2("mem\\[([0-9]+)] = ([0-9]+)");
std::regex_search(line, pieces_match, reg2);
unsigned long int num1 = std::stoull(pieces_match[1]);
unsigned long int num2 = std::stoull(pieces_match[2]);
// Put masked value into first answer map
memory_ans1[num1] = ((num2 & and_mask) | or_mask);

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.

1
2
3

ans1 = 0;
for (auto kv : memory_ans1)
    ans1 += kv.second;

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:

1
2
3
4
5
6

    If the bitmask bit is 0, the corresponding memory
        address bit is unchanged.
    If the bitmask bit is 1, the corresponding memory
        address bit is overwritten with 1.
    If the bitmask bit is X, the corresponding memory
        address bit is floating.

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,

1
2

else if (mask[mask.size() - 1 - i] == 'X')
    either_mask += (one << i);

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:

1
2
3
4
5

address: 000000000000000000000000000000101010  (decimal 42)

mask:    000000000000000000000000000000X1001X
or:      000000000000000000000000000000010010
either:  000000000000000000000000000000100001

We first apply the or_mask as before,

1
2
3
4

address: 000000000000000000000000000000101010  (decimal 42)
or:      000000000000000000000000000000010010
         000000000000000000000000000000110010

but then we need to take into account the either mask, e.g.,

1
2

either:  000000000000000000000000000000100001
         000000000000000000000000000000X1001X

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,

1

 (num1 | or_mask) & (~either_mask)

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,

1

~either: 111111111111111111111111111111011110

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,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

std::vector<long unsigned int> addresses;
addresses.push_back(((num1 | or_mask) & (~either_mask)));
for (unsigned long int i = 0; i < 36; i++) {
    if (((either_mask >> i) & one) > 0) {
        size_t maxj = addresses.size();
        for (size_t j = 0; j < maxj; j++) {
            addresses.push_back(addresses[j] + (one << i));
        }
    }
}

Now we have all the possible addresses stored, we can then store the value in map, e.g. our sparse memory block,

1
2
3

// Put value into possible addresses
for (auto v : addresses)
    memory_ans2[v] = num2;

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

Comments