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

mask = XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
mem[8] = 11
mem[7] = 101
mem[8] = 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)
mask:   XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
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 = {}
    cur_mask = prog[0]
    for inst in prog:
        if inst.startswith("mask"):
            cur_mask = np.array([c for c in inst.split(" = ")[1]])
        else:
            loc, val = parse_prog_line(inst)
            masked_val = val.copy()
            masked_val[cur_mask == "1"] = "1"
            masked_val[cur_mask == "0"] = "0"
            mem[loc] = int("".join(masked_val.tolist()), 2)
        if visualize:
            states.append(
                MachineState(
                    memory=deepcopy(mem),
                    inputs=deepcopy(prog),
                    cur_inst=inst,
                    cur_mask=cur_mask,
                )
            )
    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(" = ")[1]])

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)[0])
    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()
masked_val[cur_mask == "1"] = "1"
masked_val[cur_mask == "0"] = "0"

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 = []
    cur_mask = prog[0]
    mem = {}
    for inst in prog:
        if inst.startswith("mask"):
            cur_mask = np.array([c for c in inst.split(" = ")[1]])
        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")[0]
            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,
                    cur_mask=cur_mask,
                )
            )

    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: