For Day 14, the problem is based on bitmasking. Input consists of a bitmask and memory access instructions:

mask = XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
mem = 11
mem = 101
mem = 0


Mask values have the following effects on values being written to memory:

• X - nothing
• 1 - value is replaced by 1
• 0 - value is replaced by 0

One of the examples from the puzzle:

value:  000000000000000000000000000000001011  (decimal 11)
result: 000000000000000000000000000001001001  (decimal 73)


Part 1 asks for the sum of all memory locations after the masked values are written to memory.

To run the Part 1 program:

def run_prog(prog, visualize):
states = []
mem = {}
for inst in prog:
cur_mask = np.array([c for c in inst.split(" = ")])
else:
loc, val = parse_prog_line(inst)
mem[loc] = int("".join(masked_val.tolist()), 2)
if visualize:
states.append(
MachineState(
memory=deepcopy(mem),
inputs=deepcopy(prog),
cur_inst=inst,
)
)
return mem, states


First, memory is initialized as an empty dictionay, which will be accessed using the locations in the instructions:

mem = {}


Then the instructions are parsed, with the mask instruction loading a new mask:

if inst.startswith("mask"):
cur_mask = np.array([c for c in inst.split(" = ")])


Building a NumPy array is a key part of this solution, as NumPy has excellent masking functionality.

For normal memory access instructions, access instruction is parsed:

loc, val = parse_prog_line(inst)


Using this regular expression and function:

loc_rgx = re.compile("mem$([0-9]+)$")

def parse_prog_line(line):
loc_str, val_str = line.split(" = ")
loc = int(re.findall(loc_rgx, loc_str))
val = f"{int(val_str):036b}"

return loc, np.array([c for c in val])


Python has some nice padding capabilities in the formatting of strings, which are used to pad the numbers to the correct 36-bit value.

val = f"{int(val_str):036b}"


NumPy masking is used to set the masked bits in the number:

masked_val = val.copy()


The masked value is then written to memory:

mem[loc] = int("".join(masked_val.tolist()), 2)


The answer to the puzzle is then the sum of the values in the mem dictionary:

mem_p1, states_p1 = run_prog(prog, args.visualize and args.vis_part == 1)
p1 = sum(mem_p1.values())


Visualization of Part 1:

For Part 2, the puzzle changes the rules on how the masks work. Instead of masking the value, the masks now “float” and cover multiple memory locations. Each X in the mask now becomes both a 0 and a 1 in turn, producing many, many mask values for each memory location.

The overall structure of the problem remains the same:

def run_prog_floating(prog, visualize):
states = []
mem = {}
for inst in prog:
cur_mask = np.array([c for c in inst.split(" = ")])
else:
loc, val = parse_prog_line(inst)
val = int("".join(val.tolist()), 2)
loc = np.array([c for c in f"{loc:036b}"])
loc[cur_mask == "X"] = "X"
loc[cur_mask == "1"] = "1"
indices = np.where(loc == "X")
for m in itertools.product(*(range(2) for _ in range(len(indices)))):
new_loc = loc.copy()
idx = np.array(m) == 1
new_loc[indices[idx]] = "1"
new_loc[indices[~idx]] = "0"
new_loc = int("".join(new_loc.tolist()), 2)
mem[new_loc] = val

if visualize:
states.append(
MachineState(
memory=deepcopy(mem),
inputs=deepcopy(prog),
cur_inst=inst,
)
)

return mem, states


The key difference is how the memory location is modified. The itertools module is used to iterate over all combinations of modified masks:

for m in itertools.product(*(range(2) for _ in range(len(indices)))):
new_loc = loc.copy()
idx = np.array(m) == 1
new_loc[indices[idx]] = "1"
new_loc[indices[~idx]] = "0"
new_loc = int("".join(new_loc.tolist()), 2)
mem[new_loc] = val


Calculating the answer is then the same as in Part 1:

mem_p2, states_p2 = run_prog_floating(prog, args.visualize and args.vis_part == 2)
p2 = sum(mem_p2.values())


Visualization of Part 2: