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)
type MaskMap = M.Map Int MaskValue
data Instruction = Mask MaskMap | Assignment Int64 Int64
deriving (Show, Eq)
type Memory = M.Map Int64 Int64
data Machine = Machine { mMemory :: Memory
, mMask :: MaskMap
, mMask0 :: Int64
, mMask1 :: Int64
} 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
maskify :: String -> Instruction
maskify chars = Mask (M.fromList locValues)
where mValues = map readMaskChar chars
locValues = zip [0..] $ reverse mValues
readMaskChar '0' = Zero
readMaskChar '1' = One
readMaskChar 'X' = Wild
Part 1
The overall processing of the program is straightforward: create an empty machine, apply the instructions one at a time to get to the final state. That's folding the instructions into the machine, with a function to apply a single instruction.
part1 program = sum $ M.elems $ mMemory finalMachine
where finalMachine = executeInstructions1 program
executeInstructions1 instructions =
foldl' executeInstruction1 emtpyMachine instructions
executeInstruction1 :: Machine -> Instruction -> Machine
executeInstruction1 machine (Mask mask) = makeMask machine mask
executeInstruction1 machine (Assignment loc value) =
assignValue machine loc value
(I did think about using a State monad to hold the machine, but decided that the extra setup and teardown for it wasn't worth the benefit, given that the contents of the State would be almost immediately unpacked.)
Executing the instructions revolves around the masking operation. For bits, we have the identities
x OR 0 = x;x OR 1 = 1x AND 0 = 0;x AND 1 = x
I can apply the 1s in the mask by having a 36-bit word that's all 0s except for the mask's 1s, and ORing it with the value.Similarly, I can apply the 0s in the mask by having a 36-bit word that's all 1s except for the mask's 0s, and ANDing it with the value. The gives the maskValue function:
maskValue machine value =
(value .|. (mMask1 machine)) .&. (mMask0 machine)
(where .|. and .&. are bitwise OR and AND respectively).
Given maskValue, writing assignValue is simple.
assignValue machine loc value =
machine {mMemory = M.insert loc value' mem}
where value' = maskValue machine value
mem = mMemory machine
All that's left is to create the two masks.
To create the mask of 1s, I start with a word of all zeros (zeroBits) and setBit where there's a One in the mask. I cover all the mask with a fold. Creating the mask of 0s is the same, but using complement zeroBits as there isn't a built-in oneBits.
maskOnes :: MaskMap -> Int64
maskOnes mask = foldl' setBit zeroBits ones
where ones = M.keys $ M.filter (== One) mask
maskZeroes :: MaskMap -> Int64
maskZeroes mask = foldl' clearBit (complement zeroBits) zeroes
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]
applyAddressMask mask address = M.foldrWithKey' applyBit [address] mask
applyBit :: Int -> MaskValue -> [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
executeInstruction2 machine (Mask mask) = machine {mMask = mask}
executeInstruction2 machine (Assignment loc value) = machine {mMemory = mem'}
where locs = map encodeMask $ applyAddressMask (mMask machine) $ decodeMask loc
mem = mMemory machine
mem' = foldl' (\m l -> M.insert l value m) mem locs
Code
You can find the code here or on Gitlab.