# Day 14 (Advent of Code 2020)

It's time for the Day 14 problem!

After the hassle that was Day 13, I hope this time we'll have a relatively chill time. And, at least for Part 1, that is true.

Our input looks something like this:

mask = XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
mem = 11
mem = 101
mem = 0


mem is our memory. Our addresses are 36-bit wide, but as you'll see, that doesn't matter much.

The mask that we set is in binary - well, sort of, because there's three possible values: X (which doesn't change the bit), 1 (which sets the bit to 1) and 0 (which clears the bit).

The mask is applied to the right-hand side of assignment operations like mem = 11, before it's written out to memory. Although the example confusingly only uses 1 and 0, the values in assignment instructions are in fact decimal.

Everything clear?

Uhhh can we just do a quick reminder of how binary works first?

Okay sure.

## How binary works

"Binary" is just "base two", and "bits" are just "digits".

When we write a number in "base 10", also known as "decimal", we usually write the most significant digit first, and the least significant digit last.

Take ${241}$ - to compute its value, each digit, ${2}$, ${4}$, and ${1}$, is multiplied by a corresponding power of ${10}$, and then added together: So far so good!

Uhhh

Well for binary it's the same thing, except it's powers of two, so for example, the binary number ${1101}$ has value... ...${13}$!

Good?

Uhhh okay sure

Moving on.

Bit masks are a super useful concept that have tons of use cases. Of course, none of them come to mind right now, but I swear I've run into it a bunch of times. Like uhh.. when manipulating images maybe? I don't remember.

Anyway, it's what the problem asks us to do, so.

Say we have a binary number:

$0010000101000$

And we want to make sure the last two bits are set. We can make a bitmask that looks like this:

$0000000000011$

And do a "binary or" or "bitwise or":

\begin{aligned} &0010000101000 \ \mathbin{or} \medspace &0000000000011 \ \hline &0010000101011 \ \end{aligned}

This translates directly to Rust:

Rust codefn main() {
println!("{:013b}", 0b0010000101000 | 0b0000000000011)
}

Shell sessioncargo run --quiet 0010000101011  On the contrary, if we want to make sure the last 6 bits are cleared (ie. zero), we can make a mask like that: $0000000111111$ And do a "bitwise and" with the bitwise negation of our mask: \begin{aligned} &0010000101000 \ \mathbin{and} \medspace (\mathbin{not} \medspace &0000000111111 ) \ \hline &0010000101000 \ \mathbin{and} \medspace &1111111000000\ \ \hline &0010000000000 \ \end{aligned} Now we know how to set bits, and how to clear bits! Since the mask in the input tells us to do both, we should probably separate it into two distinct masks: KaTeX error (block): failed to execute js (detail: String("ParseError: KaTeX parse error: \\hline valid only within array environment"))  Of course the problem states that everything is 36-bit numbers, but how about we completely disregard that and just use 64-bit numbers? It's weirdly insistent about 36-bit, but then at the very end it says: Execute the initialization program. What is the sum of all values left in memory after it completes? (Do not truncate the sum to 36 bits.) So, who knows, maybe it'll show up in Part 2. ## Let's get parsing Shell session cargo add peg


We'll need some types:

Rust codestruct Program {
instructions: Vec<Instruction>,
}

enum Instruction {
Assign { addr: u64, val: u64 },
}

#[derive(Clone, Copy, Default)]
set: u64,
clear: u64,
}


And I'd like a custom Debug implementation for Instruction and Mask, so we can see set and clear as binary:

Rust codeuse std::fmt;

impl fmt::Debug for Instruction {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Instruction::SetMask { set, clear } => {
}
Instruction::Assign { addr, val } => {
write!(f, "mem[{}] = {}", addr, val)
}
}
}
}

fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "set {:b}, clear {:b}", self.set, self.clear)
}
}


And then, our actual parser. It's nothing out of the ordinary, we've done a similar parser in Day 7. The interesting rule here is set_mask, because it splits the mask into two u64 values, as discussed in the previous section:

Rust codeimpl Program {
fn parse(input: &str) -> Self {
peg::parser! {
pub(crate) grammar parser() for str {
pub(crate) rule root(p: &mut Program)
= (line(p) whitespace()*)* ![_]

rule line(p: &mut Program)
= i:instruction() { p.instructions.push(i) }

rule instruction() -> Instruction
/ assign()

= "mask = " e:$(['X' | '0' | '1']+) { let mut mask: Mask = Default::default(); for (i, x) in e.as_bytes().iter().rev().enumerate() { match x { b'1' => mask.set |= 2_u64.pow(i as _), b'0' => mask.clear |= 2_u64.pow(i as _), _ => {}, } } Instruction::SetMask(mask) } rule assign() -> Instruction = "mem[" addr:number() "] = " val:number() { Instruction::Assign { addr, val } } rule number() -> u64 = e:$(['0'..='9']+) { e.parse().unwrap() }

rule whitespace()
= [' ' | '\t' | '\r' | '\n']
}
}

let mut program = Program {
instructions: Default::default(),
};

parser::root(input, &mut program).unwrap();
program
}
}


Let's see what we get out of that:

Rust codefn main() {
println!(
"{:#?}",
Program::parse(include_str!("input.txt")).instructions
);
}


Using the first sample input:

Shell session$cargo run --quiet [ mask: set 1000000, clear 10, mem = 11, mem = 101, mem = 0, ]  Not too bad! Now, to answer, we actually have to maintain a list of $addr \rArr value$ mappings, so that we can sum them all up in the end. We also, as we go, have to remember the value of the mask. I don't think it's necessarily wise to represent memory as an array, by the way. Every memory location can contain an u64 number, and we have ${2^{36}}$ possible addresses, so that would be... ${2^{36} \cdot 8}$ bytes, uhh, that's 512 GiB. Instead we'll use a HashMap, and that'll be that. What about the many readers that will write in saying we didn't strictly need a HashMap? Too bad! I'll take the heat! First, we'll need to know how to apply a Mask: Rust codeimpl Mask { fn apply(&self, x: u64) -> u64 { x | self.set & (!self.clear) } }  And then... you know what, I think we've seen enough iterators in the previous 13 days, let's be imperative for a second: Rust codeuse std::collection::HashMap; fn main() { let mut mask: Mask = Default::default(); let mut mem = HashMap::<u64, u64>::new(); let program = Program::parse(include_str!("input.txt")); for ins in &program.instructions { match *ins { Instruction::SetMask(new_mask) => mask = new_mask, Instruction::Assign { addr, val } => { mem.insert(addr, mask.apply(val)); } } } println!("Answer: {}", mem.values().sum::<u64>()); }  Shell session$ cargo run --quiet


Okay, this matches the example, but what about the real puzzle input?

As usual, it's much messier - mine is 555 lines, and starts with:

mask = 110000011XX0000X101000X10X01XX001011
mem = 468472
mem = 23224119
mem = 191252712
mem = 25669
mem = 238647542
mem = 1020
mem = 57996
mem = 1843
mem = 177500
mem = 5833292
mem = 25707732
(etc.)

Shell session$cargo run --quiet Answer: 14954914379452  Okay, that was easy! Moving on. I swear, if Part 2 ends up turning this into a two-hour adventure again... Now now bear, let's be optimistic... ## Part 2 In part 2, the mask doesn't affect values, it affects memory addresses. Ohhh here we go. And X doesn't mean "don't change the address", it means the bit is "floating", which means it'll take all possible values, potentially causing many memory addresses to be written all at once. Ah for fuck's sake. This is combinatorics all over again. Ah, I'm sure we can solve that fairly easily. Okay, so we don't actually need to change our parser at all, because the "floating" bits are simply the bits that are neither in set nor in clear. Let's set Part 2's example as our input for a bit: mask = 000000000000000000000000000000X1001X mem = 100 mask = 00000000000000000000000000000000X0XX mem = 1  Rust codefn main() { let program = Program::parse(include_str!("input.txt")); println!("{:#?}", program.instructions); }  Shell session$ cargo run --quiet
[
mem = 100,
mem = 1,
]


Let's take that first mask - how do we find out where the Xs are without making our representation any wider?

Without what now?

Without making the Mask struct any bigger.

Oh! ...just say that then.

So, what we could do is make a mask that's, in order:

\begin{aligned} 00000000000000001 \ 00000000000000010 \ 00000000000000100 \ 00000000000001000 \ 00000000000010000 \ \end{aligned} \ \dots

And then, we combine ${set}$ and ${clear}$ with a "bitwise or", so the result's bits are set if they're set in either. Then, we do a "bitwise and" with our mask, and if the result is 0 - then the bit was set in neither ${set}$ nor ${clear}$, therefore, it must be an ${X}$!

Something like that:

Rust codeimpl Mask {
fn x_positions(&self) -> impl Iterator<Item = u64> + '_ {
(0..36_u64).filter(move |i| ((1 << i) & (self.set | self.clear)) == 0)
}
}


Let's see what we get:

Rust codefn main() {
let program = Program::parse(include_str!("input.txt"));
println!("{:#?}", program.instructions);

}
}

Shell session$cargo run --quiet [ mask: set 10010, clear 111111111111111111111111111111001100, mem = 100, mask: set 0, clear 111111111111111111111111111111110100, mem = 1, ] X positions: [0, 5]  As a reminder, the first line was: mask = 000000000000000000000000000000X1001X  If the rightmost element is ${0}$, then we indeed have ${X}$ at positions ${0}$ and ${5}$. From there, we need to account for all possibilities. We can have: • neither set • ${0}$ set • ${5}$ set • ${0}$ and ${5}$ set (Note that an $X$ that isn't set is cleared.) What we're trying to enumerate is the power set of ${0, 5}$: $\mathcal{P}({0, 5}) = {{}, {0}, {5}, {0, 5}}$ And would you know it, itertools has just the thing for us! Shell session$ cargo add itertools

Rust codeuse itertools::Itertools;

fn main() {
let program = Program::parse(include_str!("input.txt"));
println!("{:#?}", program.instructions);

println!(
"X positions powerset: {:?}",
//                  👇👇👇
);
}
}

Shell session$cargo run --quiet [ mask: set 10010, clear 111111111111111111111111111111001100, mem = 100, mask: set 0, clear 111111111111111111111111111111110100, mem = 1, ] X positions powerset: [[], , , [0, 5]]  How cool. So, given that powerset... how do we compute the equivalent mask? Because clearly, for every input Mask, we have a set of outputs Mask for every combination of ${X}$ being set or cleared. First off, given a Vec<u64>, that indicates the positions of the ${X}$ which are set, we should be able to adjust the input Mask. Rust codeimpl Mask { fn apply_x(&self, positions: Vec<u64>) -> Self { // Mask is Copy, this is fine let mut res = *self; for pos in self.x_positions() { let mask = 1_u64 << pos; // In practice, positions is short, so it's not // worth constructing a HashSet if positions.contains(&pos) { // it's set, then! res.set |= mask; } else { // it not set, it's cleared res.clear |= mask; } } res } }  From there, we should be able to generate all the output Mask from an input Mask - let's make an Iterator out of it! Rust codeimpl Mask { fn each_combination(&self) -> impl Iterator<Item = Self> + '_ { self.x_positions() .powerset() .map(move |xes| self.apply_x(xes)) } }  Also, while we're at it - let's always output 36 bits, since that's the length of our masks. It'll make it easier to read the output: Rust codeimpl fmt::Debug for Mask { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { write!(f, "set {:036b}, clear {:036b}", self.set, self.clear) } }  No, you know what - let's do one better. When debug-printing, let's print it with ${0, 1, X}$ characters, just like the input. It's easy enough: Rust codeimpl fmt::Debug for Mask { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { for i in 0..36 { let mask = i << (36 - i); write!( f, "{}", if self.set & mask != 0 { '1' } else if self.clear & mask != 0 { '0' } else { 'X' } )?; } Ok(()) } }  Now we're ready to try it out: Rust codefn main() { let program = Program::parse(include_str!("input.txt")); println!("{:#?}", program.instructions); if let Instruction::SetMask(mask) = &program.instructions { println!("{:?} yields:", mask); for combo in mask.each_combination() { println!("{:?}", combo); } } }  Shell session$ cargo run --quiet
[
mem = 100,
mem = 1,
]
000000000000000000000000000000X1001X yields:
000000000000000000000000000000010010
000000000000000000000000000000010011
000000000000000000000000000000110010
000000000000000000000000000000110011


Seems alright?

Yeah, you think we're good to go?

Looks like it yeah. Let's keep it short and sweet, shall we?

So it's at this point in the puzzle that I realize I've read the problem statement all wrong. In fact, we don't "generate a list of masks", which we should all apply to addr to get different addresses to write to.

Nooo no no. Instead, we have to somehow combine the mask and the addr and the result is a trinary value, like so:

address: 000000000000000000000000000000101010  (decimal 42)
result:  000000000000000000000000000000X1101X


Well the only way we have of representing trinary values is our Mask struct, so, I guess okay let's implement that operation. From the looks of it (since it's not really clear outside of the example):

• If the mask has $X$, the resulting bit is $X$
• If the address has ${1}$, the resulting bit is ${0}$
• Otherwise, the bit remains unchanged

Sure, we can do that:

Rust codeimpl Mask {
fn or(&self, x: u64) -> Self {
let mut res = *self;
let set_or_clear = self.set | self.clear;

for i in 0..36 {
let mask = 1 << i;
if set_or_clear & mask == 0 {
// mask has X, it stays X.
} else if x & mask != 0 {
// x has 1, we set 1.
} else {
// otherwise, we leave whatever we had
}
}

res
}
}


Let's try it out:

Rust codefn main() {
let program = Program::parse(include_str!("input.txt"));
println!("{:#?}", program.instructions);

}
}

Shell session$cargo run --quiet [ mask: 000000000000000000000000000000X1001X, mem = 100, mask: 00000000000000000000000000000000X0XX, mem = 1, ] 000000000000000000000000000000X1001X (mask) 000000000000000000000000000000101010 (addr) 000000000000000000000000000000X1101X (combined)  That checks out! So now that we have that combined value, we still need to generate all possible addresses... we did that before, sort of, and I can't be arsed to do it again (surprise!), so we're just going to use that - only we'll just take the Mask::set field of the resulting masks. Rust codeimpl Mask { fn each_binary_value(&self) -> impl Iterator<Item = u64> + '_ { self.each_combination().map(|m| m.set) } }  Let's make super sure it matches the example now: Rust codefn main() { let program = Program::parse(include_str!("input.txt")); println!("{:#?}", program.instructions); if let Instruction::SetMask(mask) = &program.instructions { println!("{:?} (mask)", mask); let addr = 42; println!("{:036b} (addr)", addr); let mask = mask.or(addr); println!("{:?} (combined)", mask); println!("yields:"); for val in mask.each_binary_value() { println!("{:036b} ({})", val, val); } } }  Shell session$ cargo run --quiet
[
mem = 100,
mem = 1,
]
000000000000000000000000000000X1101X (combined)
yields:
000000000000000000000000000000011010 (26)
000000000000000000000000000000011011 (27)
000000000000000000000000000000111010 (58)
000000000000000000000000000000111011 (59)


It does! It does matches the example. Praise be.

With this, we can once again implement the logic to "interpret" our program, and get the example's result:

Rust codefn main() {
let mut mem = HashMap::<u64, u64>::new();

let program = Program::parse(include_str!("input.txt"));
for ins in &program.instructions {
match *ins {
Instruction::Assign { addr, val } => {
}
}
}
}

}

Shell session$cargo run --quiet Answer: 208  There. Wonderful. Now for the real puzzle input. What's wrong amos, you sound pissed? I'm not! I'm not. It's just, we have binary computers, you know? Not trinary computers. And I don't want to just have an array of enums, that would make no sens- What's the matter? You can't fit everything in your little typechecked world? Boo hoo. Cry me a river. But I could that's the thing, it just wouldn't be efficient, because something something computers. Uhhh.. and now for the real puzzle input: Shell session$ cargo run --quiet