# Advent of Code 2020 day 14

I thought day 14 would be a load of bit-twiddling. Part 1 was, but part 2 went in other directions so I moved a bit away from just bits and Int64 values.

## Data and data structures

In a vast oversight of computer designers everywhere, 36-bit unsigned integers aren't a widely-used machine word. Luckily, the high 28 bits are never used, so I can get away with using Int64 (from Data.Int) for the machine's memory.

But I can't use Int64 for everything. The bit-twiddling functions in Data.Bits use Int values to address the locations within a word. And the masks are three-valued objects, so I created a new algebraic type to represent them.

Finally, I create a record for the Machine. Not that this contains the two mask types needed for both parts 1 and 2.

data MaskValue = Zero | One | Wild deriving (Show, Eq)
deriving (Show, Eq)

type Memory = M.Map Int64 Int64
data Machine = Machine { mMemory :: Memory
} deriving (Show, Eq)

emtpyMachine = Machine M.empty M.empty (complement 0) 0


Parsing the input is a bit more complex than before, due to the need to create the Maps to hold the mask. I create them with the utility functions maskify and readMaskChar. The rest of the parser should be readable, but note the need to have brackets around the rules that read the text.

programP = (maskP <|> assignmentP) sepBy endOfLine

maskP = maskify <$> ("mask = " *> (many (digit <|> letter))) assignmentP = Assignment <$> ("mem[" *> decimal) <* "] = " <*> decimal

where zeroes = M.keys $M.filter (== Zero) mask  ## Part 2 Things got more complex here. The main task is to convert one address into a set of addresses, so the value can be applied to all addresses in that set. First, a couple of functions to convert between MaskMaps and Int64s. Note that encodeMask will throw an error if it's asked to convert something containing a Wild value. In production code, I'd do something more robust than this. encodeMask :: MaskMap -> Int64 encodeMask mask = M.foldrWithKey' setBitValue zeroBits mask where setBitValue _ Zero n = n setBitValue i One n = setBit n i decodeMask :: Int64 -> MaskMap decodeMask val = M.fromList [ (i, decodeBit$ testBit val i)
| i <- [0..(finiteBitSize val)]
]
where decodeBit True = One
decodeBit False = Zero


There are a bunch of different ways to convert a single item into a list of possibles. I thought about using a List monad to represent the non-deterministic nature of the address, but ended up doing the simpler equivalent of using list comprehensions.

Given a mask value and a list of masks, applyBit will create a new list of masks. If the bit is Zero, the masks stay the same. If the bit is One, it replaces the corresponding value in each of the masks. If the bit is Wild, it creates two new masks for each one present, for the two different bit values.

applyAddressMask :: MaskMap -> MaskMap -> [MaskMap]

applyBit _ Zero ms = ms
applyBit k One  ms = [ M.insert k One m | m <- ms ]
applyBit k Wild ms = [ M.insert k b m | m <- ms, b <- [Zero, One] ]


With the ability to create lists of masks, the instruction execution is updating the memory in every location in that list.

executeInstruction2 :: Machine -> Instruction -> Machine
where locs = map encodeMask $applyAddressMask (mMask machine)$ decodeMask loc