AoC 2020 D14: Docking Data

Python | Problem statement | Source code | Tags: Bitwise operations

← Previous Back to AoC Index Next →

Part 1

The mask can do one of three things to a bit: set to 0, set to 1, or leave unchanged. We know that "set to 0" is done with & 0 (whereas & 1 leaves unchanged), and "set to 1" is done with | 1 (whereas | 0 leaves unchanged). So we can maintain two bitmasks, one for setting to 0 and one for setting to 1; bits that are set by neither remain unchanged. I construct the masks by first reversing the mask string, so that the character index corresponds with the shift amount. ^ 1 is used to toggle bits in the masks.

mask = reversed(line[len("mask = ") :])
mask_1 = 0
mask_0 = -1 & 0xFFFFFFFFF
for i, ch in enumerate(mask):
    if ch == "0":
        mask_0 = mask_0 ^ (1 << i)
    elif ch == "1":
        mask_1 = mask_1 ^ (1 << i)
python

Memory update is straightforward:

mem[int(match.group(1))] = int(match.group(2)) & mask_0 | mask_1
python

Part 2

In part 2, we still have three possible actions on each bit: set to 0, unchanged, or floating. Floating is nothing more than enumerating all possible combinations of 0 and 1 for those bits. I made a little generator function to enumerate these combinations:

def generate_binaries(x_indices: list[int]):
    for comb in itertools.product((0, 1), repeat=len(x_indices)):
        mask_1 = 0
        mask_0 = -1 & 0xFFFFFFFFF
        for i, bit in zip(x_indices, comb):
            if bit == 0:
                mask_0 = mask_0 ^ (1 << i)
            elif bit == 1:
                mask_1 = mask_1 ^ (1 << i)
        yield (mask_0, mask_1)
python

Once we have concrete mask_0 and mask_1, the masking is done exactly like part 1, this time to memory addresses.

base_index = int(match.group(1)) | mask_1
val = int(match.group(2))
for x_mask_0, x_mask_1 in x_masks:
    mem[base_index & x_mask_0 | x_mask_1] = val
python

← Previous Back to AoC Index Next →