2020-12-14 - Docking Data
(original .ipynb)
Day 14 puzzle input is a sequence of assembly-like instructions (mine is here) which can be either writes to memory locations or adjustments of a "mask" register. Part 1 involves interpreting the mask as modifying the values being written to memory (0 and 1 set the bits in those positions, X is ignored). Part 2 involves interpreting the mask as modifying the memory address being written, with "X"s being wildcards meaning both 0 and 1 (so one write instruction can result in multiple addresses being modified).
from collections import defaultdict
test_input_str = """mask = XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
mem[8] = 11
mem[7] = 101
mem[8] = 0"""
puzzle_input_str = open("puzzle_input/day14.txt", "r").read()
def parse_mask(mask):
fixed_bits = []
floating_bits = []
for i, digit in enumerate(mask):
if digit == "X":
floating_bits.append(i)
elif digit == "1":
fixed_bits.append((int(i), digit))
else:
# do nothing for digit == "0"
pass
return fixed_bits, floating_bits
def pad_value(value_str):
padding = (36 - len(value_str)) * "0"
return padding + value_str
def apply_mask(value_str, mask_str):
value_bin_str = bin(int(value_str))[2:]
value_lst = [v for v in pad_value(value_bin_str)]
fixed_bits, _ = parse_mask(mask_str)
for position, digit in fixed_bits:
value_lst[position] = digit
return "".join(value_lst)
def execute_instruction_v1(instruction, mask, mem):
lhs, rhs = instruction.split(" = ")
if lhs == "mask":
return rhs
location = int(lhs.removeprefix("mem[")[:-1])
value = apply_mask(rhs, mask)
mem[location] = int(value, 2)
return mask
def solve(input_str, execute_func):
mask = ()
mem = defaultdict(lambda:0)
for instruction in input_str.split("\n"):
mask = execute_func(instruction, mask, mem)
total = 0
for addr in mem:
total += mem[addr]
return total
assert 165 == solve(test_input_str, execute_instruction_v1)
print(solve(puzzle_input_str, execute_instruction_v1))
15407292426155
%%time
def apply_fixed_bits(fixed_bits, address_lst):
addr_lst_copy = [v for v in address_lst]
for position, digit in fixed_bits:
addr_lst_copy[position] = digit
return addr_lst_copy
def apply_floating_bit(address_lst, index, val):
addr_lst_copy = [v for v in address_lst]
addr_lst_copy[index] = val
return addr_lst_copy
def apply_mask_v2(original_address, mask_str):
fixed_bits, floating_bits = parse_mask(mask_str)
original_address_str = bin(original_address)[2:]
original_address_lst = [v for v in pad_value(original_address_str)]
addresses = [
apply_fixed_bits(fixed_bits, original_address_lst)
]
for position in floating_bits:
new_addresses = []
for address in addresses:
new_addresses.append(apply_floating_bit(address, position, "0"))
new_addresses.append(apply_floating_bit(address, position, "1"))
addresses = new_addresses
return [int("".join(address), 2) for address in addresses]
def execute_instruction_v2(instruction, mask, mem):
lhs, rhs = instruction.split(" = ")
if lhs == "mask":
return rhs
addresses = apply_mask_v2(int(lhs.removeprefix("mem[")[:-1]), mask)
value = int(rhs)
for address in addresses:
mem[address] = value
return mask
test_input_str_2 = """mask = 000000000000000000000000000000X1001X
mem[42] = 100
mask = 00000000000000000000000000000000X0XX
mem[26] = 1"""
# fun fact, because my solution is horrifically inefficient
# and test_input_str has huge amount of floating bits, trying
# to calculate part2(test_input_str) takes rather a long time
# to finish. this cost me quite a lot of time - I didn't realise
# they changed the example input they used :-/
assert 208 == solve(test_input_str_2, execute_instruction_v2)
print(solve(puzzle_input_str, execute_instruction_v2))
3260587250457 CPU times: user 384 ms, sys: 3.5 ms, total: 388 ms Wall time: 398 ms