Day 14 Bitmasks

Bit masks are fun things, especially in this case.

We have a fairly simple concept here, create a sparse memory array, and then go through the instructions, writing to memory every instruction, and passing the memory blob through a bitmask modification function.

Python has some nice tools for bit arrays, so this shouldn't be too hard, but the modification needs to take the number in decimal, turn it into a bit array, and then go through the bit array replacing bits as needed. A ternary array would be more useful than a binary array here, but that would be horribly complex to implement, so instead we'll turn the bit array into a sequence of bits to toggle, and apply that to the binary form of the value to write.

import ipytest
ipytest.autoconfig()
import bitstring

def create_converter(bitarray):
    values = {}
    for i,b in enumerate(bitarray[::-1]):
        if b != "X":
            values[i] = int(b)
    return values

def convert(value, converter):
    bits = bitstring.BitArray(uint=value,length=36)
    for i,b in converter.items():
        bits[-i-1] = b
    return bits.uint

test_converter = create_converter("XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X")
assert 73 == convert(11, test_converter)
assert 101 == convert(101, test_converter)
assert 64 == convert(0, test_converter)

Grand, that seems to work sensibly.

Now looking at the data, it looks like we'll have to parse the instructions, and that there will be lots of mask= calls to change the mask, so I think we'll just step through line by line and then set the memory, and validate that it did the right thing

import re
mem_re = re.compile("mem\[(\d+)\] = (\d+)")
def process_lines(lines):
    mem = {}
    converter = None
    for line in lines:
        if line.startswith("mask = "):
            converter = create_converter(line[7:])
        if line.startswith("mem"):
            nums = [int(x) for x in mem_re.match(line).groups()]
            mem[nums[0]]=convert(nums[1], converter)
    return mem
        
test_lines="""mask = XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
mem[8] = 11
mem[7] = 101
mem[8] = 0""".split("\n")
test_mem = process_lines(test_lines)
assert test_mem[8] == 64
assert test_mem[7] == 101
assert sum(test_mem.values()) == 165

That works better than I thought.... Let's see if it works on real data

mem = process_lines([line.strip() for line in open("day14.txt")])
print(sum(mem.values()))

17028179706934

Part 2 - Floating addresses

Ok, so the part 2 is probably a complete rewrite. This time, when we apply a mask to a number, we want to generate a set of every possible number that it could be, and then write the value to all of those numbers.

That's going to make our dictionary much less sparse... I wonder if we could invert our storage, and store for each integer value, which memory locations are set to that value. Given that we have only around 500 lines of input, that's at most 500 values, but we're talking a lot more memory addresses this way.

It sounds stupid, because in this case, we don't actually care about which memory location is which, it doesn't matter that's it's a highly inefficient structure for real like, it'll be far more efficient for the set we want. Besides the convert code is the same, as we still need a set of numbers for a bitfield.

def convert(value, converter):
    nums = set()
    l = converter.count("X")
    for i in range(2**l):
        replacebits = bitstring.BitArray(uint=i,length=l)
        it = replacebits.cut(1)
        target = bitstring.BitArray(uint=value,length=36)
#         print(target.bin,replacebits.bin)
        for j,b in enumerate(converter):
            if b == "0":
                pass # unchanged
            if b == "1":
                target[j] = 1
            if b == "X":
                target[j] = it.__next__()
        nums.add(target.uint)    
    return nums

assert {26,27,58,59} == convert(40, "000000000000000000000000000000X1001X")
assert {16,17,18,19,24,25,26,27} == convert(26, "00000000000000000000000000000000X0XX")

Urgh, that's horrid, but it seems to work...

Let's work on the switched memory and the test data

import collections

def process_lines(lines):
    mem = collections.defaultdict(set)
    mask=None
    for line in lines:
        if line.startswith("mask = "):
            mask = line[7:]
        if line.startswith("mem"):
            nums = [int(x) for x in mem_re.match(line).groups()]
            mem[nums[1]] = convert(nums[0], mask)
    return mem
        
test_lines="""mask = 000000000000000000000000000000X1001X
mem[42] = 100
mask = 00000000000000000000000000000000X0XX
mem[26] = 1""".split("\n")
test_mem = process_lines(test_lines)
assert test_mem[100] == {26,27,58,59}
assert test_mem[1] ==  {16,17,18,19,24,25,26,27}

def sum_mem(mem):
    sum = 0
    for key in mem:
        sum += key * len(mem[key])
    return sum
# assert sum_mem(test_mem) == 208

---------------------------------------------------------------------------

AssertionError Traceback (most recent call last)

in 25 sum += key * len(mem[key]) 26 return sum ---> 27 assert sum_mem(test_mem) == 208

AssertionError: assert 408 == 208 + where 408 = <function sum_mem at 0x7ff8d00b08b0>(defaultdict(<class 'set'>, {100: {59, 26, 27, 58}, 1: {16, 17, 18, 19, 24, 25, 26, 27}}))

Oooh, that doesn't work. The idea is sound, but the sums gets awful complex, because lines can overwrite other memory locations (of course it can, why didn't I think of it). Back to the original idea

import collections

def process_lines(lines):
    mem = {}
    mask=None
    for line in lines:
        if line.startswith("mask = "):
            mask = line[7:]
        if line.startswith("mem"):
            nums = [int(x) for x in mem_re.match(line).groups()]
            for addr in  convert(nums[0], mask):
                mem[addr] = nums[1]
    return mem
        
test_lines="""mask = 000000000000000000000000000000X1001X
mem[42] = 100
mask = 00000000000000000000000000000000X0XX
mem[26] = 1""".split("\n")
test_mem = process_lines(test_lines)
assert test_mem[58] == 100
assert test_mem[59] == 100
assert test_mem[16] == 1 
assert test_mem[17] == 1 
assert test_mem[18] == 1 
assert test_mem[19] == 1 
assert test_mem[26] == 1
assert test_mem[27] == 1
assert sum(test_mem.values()) == 208

Let's do the real file

mem = process_lines([line.strip() for line in open("day14.txt")])
print(sum(mem.values()))

3683236147222

Slow, very slow, but it gave me the correct answer!