@xavdid does Advent of Code

Docking Data

Published: 2020-12-15 Original Prompt

Part 1

I found this prompt very hard to parse, but the puzzle itself is straightforward. The prompt mentions a computer, but it’s not the one we wrote on day 8. In fact for our purposes, it’s a humble dict. We’re going to be writing numeric values at string keys.

Lines of input come in two forms. Either:

If we get a mask line, we store that value. If we get a mem line, we’re writing values into the aforementioned storage. The basic setup is simple:

mem = {}
mask = ""
for line in self.input:
if line.startswith("mask"):
mask = line.split(" = ")[1]

Let’s zoom in on that else block. The first thing to do is parse out the values from that line. While we could do some surgical splitting, but a regex will be fewer lines. I won’t go into all of regex here, but will callout a great Python-specific feature: named capture groups. While all regex engines can denote capture groups with (), Python lets you name them!

import re
s = 'mem[42] = 100'
# without named groups
noname = re.match(r'mem\[(\d+)\] = (\d+)', s)
address, value = noname.groups() # => ('42', '100')
# with names
named = re.match(r"mem\[(?P<address>\d+)\] = (?P<value>\d+)", s)
named.group('address') # '42'
named.group('value') # '100'

It’s not much on a regex this small, but it confers a lot of readability. Either way, we can extract out the address and value (as strings). Next, we’ve got to do some conversion.

First up is turning a number into a padded binary string. Sounds a little imposing, but Python’s bin(ary) and rjust functions make short work of it:

int_to_padded_binary = lambda i: bin(i)[2:].rjust(36, "0")

A couple of points of interest:

With that in hand, we’ve got both our padded binary and our mask, so we’re ready to tackle the example!

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

It’s exceedingly convenient that both strings are the same length; this allows us to take full advantage of Python’s zip function. It takes two iterables and gives us pairs:

list(zip('ABCD', '1234'))
# [('A', '1'), ('B', '2'), ('C', '3'), ('D', '4')]

We need to go through each matching character from the mask and value and sometimes replace the value character if the mask character isn’t an X:

def apply_mask_to_int(mask: str, i: int) -> str:
res = []
for mask_val, target_val in zip(mask, int_to_padded_binary(i)):
if mask_val != 'X':
return ''.join(res)

Not so bad! We can make it a list comprehension without losing much clarity:

def apply_mask_to_int(mask: str, i: int) -> str:
return "".join(
mask_val if mask_val != "X" else target_val
for mask_val, target_val in zip(mask, int_to_padded_binary(i))

Now we call that from our else block above:

data = re.match(r"mem\[(?P<address>\d+)\] = (?P<value>\d+)", line)
mem[data.group("address")] = int(
apply_mask_to_int(mask, int(data.group("value"))),

We call int twice:

To wrap up, we add up all the values stored in memory:

return sum(mem.values())

Part 2

Part 2 is mostly the same as part 1 - the big difference is that the bitmask is applied to the key instead of the value:

mem = {}
mask = ""
for line in self.input:
if line.startswith("mask"):
mask = line.split(" = ")[1]
data = re.match(r"mem\[(?P<raw_address>\d+)\] = (?P<value>\d+)", line)
return sum(mem.values())

Let’s fill in that ...! First, our mask application is slightly different. Now, we replace the value if anything but 0. Easy enough:

def apply_mask_to_int_v2(mask: str, i: int) -> str:
return "".join(
target_val if mask_val == "0" else mask_val
for mask_val, target_val in zip(mask, int_to_padded_binary(i))

And we’ll call it from that else:

floating_mask = apply_mask_to_int_v2(
mask, int(data.group("raw_address"))

Now the tricky part. We have to use this same mask repeatedly and replace the Xs differently each time. If we look at their examples, we see a pattern:

…X1101X becomes:

011010 => 00 …011011 => 01 …111010 => 10 …111011 => 11

Keen readers will clock that replacement as counting up in binary with leading zeroes! We replace X with padded binary representations of 0, then 1, 2, etc.

Because each X can have 2 values, a mask will write to 2 ^ num_x addresses (2 Xs is 4 addresses, 3 is 8, etc). The really sneaky thing is replacing the Xs one at a time. Luckily, Python’s string.replace function takes an argument to control the number of replacements. So if we iterate through the padded binary, we can replace one X at a time. This is doable with a small tweak to our padding function:

int_to_padded_binary = lambda i, l=36: bin(i)[2:].rjust(l, "0")

Very similar to before, but the length of the padding is now configurable (and defaults to 36, so no code changes in part 1 are necessary). Now, the good stuff:

def resolve_floaters(mask: str) -> int:
num_x = mask.count("X")
num_combos = 2 ** num_x
for i in range(num_combos):
res = mask
# only want to pad for the Xs we have
replacements = int_to_padded_binary(i, num_x)
for digit in replacements:
# each time we loop, another X disappears
res = res.replace("X", digit, 1)
# send back a regular number
yield int(res, 2)

The yield keys you into the fact that we’ll iterate over the results of this function, which we do in the else block:

for address in resolve_floaters(floating_mask):
mem[address] = int(data.group("value"))