Day 14 (Advent of Code 2020)

This article is part of the Advent of Code 2020 series.

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[8] = 11 mem[7] = 101 mem[8] = 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[8] = 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{241} - to compute its value, each digit, 2{2}, 4{4}, and 1{1}, is multiplied by a corresponding power of 10{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{1101} has value...

...13{13}!

Good?

Uhhh okay sure

Moving on.

Bit masks

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 0010000101000

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

0000000000011 0000000000011

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

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

This translates directly to Rust:

Rust code
fn main() { println!("{:013b}", 0b0010000101000 | 0b0000000000011) }
Shell session
$ cargo 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 0000000111111

And do a "bitwise and" with the bitwise negation of our mask:

0010000101000and(not0000000111111)0010000101000and1111111000000 0010000000000 \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:

maskXXX1XXXX0Xset0001000000clear0000000010 \begin{matrix} \text{mask} & X & X & X & 1 & X & X & X & X & 0 & X \cr \hline \text{set} & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \cr \text{clear} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{matrix}

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 Adding peg v0.6.3 to dependencies

We'll need some types:

Rust code
struct Program { instructions: Vec<Instruction>, } enum Instruction { SetMask(Mask), Assign { addr: u64, val: u64 }, } #[derive(Clone, Copy, Default)] struct Mask { 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 code
use std::fmt; impl fmt::Debug for Instruction { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { match self { Instruction::SetMask { set, clear } => { write!(f, "mask: {:?}", mask) } Instruction::Assign { addr, val } => { write!(f, "mem[{}] = {}", addr, val) } } } } impl fmt::Debug for Mask { 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 code
impl 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 = set_mask() / assign() rule set_mask() -> Instruction = "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 code
fn 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[8] = 11, mem[7] = 101, mem[8] = 0, ]

Not too bad!

Now, to answer, we actually have to maintain a list of addrvalueaddr \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 236{2^{36}} possible addresses, so that would be... 2368{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 code
impl 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 code
use 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 Answer: 165

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[49397] = 468472 mem[50029] = 23224119 mem[39033] = 191252712 mem[37738] = 25669 mem[45831] = 238647542 mem[55749] = 1020 mem[29592] = 57996 mask = 100X10XXX101011X10X0110111X01X0X0010 mem[10526] = 1843 mem[2144] = 177500 mem[33967] = 5833292 mem[58979] = 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[42] = 100 mask = 00000000000000000000000000000000X0XX mem[26] = 1
Rust code
fn main() { let program = Program::parse(include_str!("input.txt")); println!("{:#?}", program.instructions); }
Shell session
$ cargo run --quiet [ mask: set 10010, clear 111111111111111111111111111111001100, mem[42] = 100, mask: set 0, clear 111111111111111111111111111111110100, mem[26] = 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:

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

And then, we combine set{set} and clear{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{set} nor clear{clear}, therefore, it must be an X{X}!

Something like that:

Rust code
impl 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 code
fn main() { let program = Program::parse(include_str!("input.txt")); println!("{:#?}", program.instructions); if let Instruction::SetMask(mask) = &program.instructions[0] { println!("X positions: {:?}", mask.x_positions().collect::<Vec<_>>()); } }
Shell session
$ cargo run --quiet [ mask: set 10010, clear 111111111111111111111111111111001100, mem[42] = 100, mask: set 0, clear 111111111111111111111111111111110100, mem[26] = 1, ] X positions: [0, 5]

As a reminder, the first line was:

mask = 000000000000000000000000000000X1001X

If the rightmost element is 0{0}, then we indeed have X{X} at positions 0{0} and 5{5}.

From there, we need to account for all possibilities. We can have:

(Note that an XX that isn't set is cleared.)

What we're trying to enumerate is the power set of {0,5}{0, 5}:

P({0,5})={{},{0},{5},{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 Adding itertools v0.10.0 to dependencies
Rust code
use itertools::Itertools; fn main() { let program = Program::parse(include_str!("input.txt")); println!("{:#?}", program.instructions); if let Instruction::SetMask(mask) = &program.instructions[0] { println!( "X positions powerset: {:?}", // 👇👇👇 mask.x_positions().powerset().collect::<Vec<_>>() ); } }
Shell session
$ cargo run --quiet [ mask: set 10010, clear 111111111111111111111111111111001100, mem[42] = 100, mask: set 0, clear 111111111111111111111111111111110100, mem[26] = 1, ] X positions powerset: [[], [0], [5], [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{X} being set or cleared.

First off, given a Vec<u64>, that indicates the positions of the X{X} which are set, we should be able to adjust the input Mask.

Rust code
impl 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 code
impl 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 code
impl 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{0, 1, X} characters, just like the input.

It's easy enough:

Rust code
impl 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 code
fn main() { let program = Program::parse(include_str!("input.txt")); println!("{:#?}", program.instructions); if let Instruction::SetMask(mask) = &program.instructions[0] { println!("{:?} yields:", mask); for combo in mask.each_combination() { println!("{:?}", combo); } } }
Shell session
$ cargo run --quiet [ mask: 000000000000000000000000000000X1001X, mem[42] = 100, mask: 00000000000000000000000000000000X0XX, mem[26] = 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) mask: 000000000000000000000000000000X1001X 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):

Sure, we can do that:

Rust code
impl 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. res.set |= mask; res.clear &= !mask; } else { // otherwise, we leave whatever we had } } res } }

Let's try it out:

Rust code
fn main() { let program = Program::parse(include_str!("input.txt")); println!("{:#?}", program.instructions); if let Instruction::SetMask(mask) = &program.instructions[0] { println!("{:?} (mask)", mask); let addr = 42; println!("{:036b} (addr)", addr); let mask = mask.or(addr); println!("{:?} (combined)", mask); } }
Shell session
$ cargo run --quiet [ mask: 000000000000000000000000000000X1001X, mem[42] = 100, mask: 00000000000000000000000000000000X0XX, mem[26] = 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 code
impl 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 code
fn main() { let program = Program::parse(include_str!("input.txt")); println!("{:#?}", program.instructions); if let Instruction::SetMask(mask) = &program.instructions[0] { 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 [ mask: 000000000000000000000000000000X1001X, mem[42] = 100, mask: 00000000000000000000000000000000X0XX, mem[26] = 1, ] 000000000000000000000000000000X1001X (mask) 000000000000000000000000000000101010 (addr) 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 code
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 } => { for addr in mask.or(addr).each_binary_value() { mem.insert(addr, val); } } } } println!("Answer: {}", mem.values().sum::<u64>()); }
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 Answer: 3415488160714

Woo, correct!

Only eleven puzzles left. Phew.

This article was made possible thanks to my patrons: Christian Oudard, Ronen Cohen, Matt Welke, Ivan Towlson, Nathan Lincoln, Daniel Wagner-Hall, Felix Weis, Henrik Sylvester Pedersen, Thor Kamphefner, VALENTIN MARIETTE, Kamran Khan, Cole Kurkowski, Arjen Laarhoven, Jeremy Kaplan, Jon Reynolds, Vicente Bosch, Chirag Jain, Ville Mattila, Marie Janssen, Vladyslav Batyrenko, Cameron Clausen, Pierre Guillaume Herveou, Agam Brahma, spike grobstein, Daniel Franklin, Jon Gjengset, Tex, Nick Thomas, Blaž Tomažič, Johan, Paul Marques Mota, Jakub Fijałkowski, Mitchell Hamilton, Ruben Duque, Brad Luyster, Max von Forell, Jake S, Justin, Dimitri Merejkowsky, Chris Biscardi, mrcowsy, René Ribaud, Alex Doroshenko, Julian, Vincent, Steven McGuire, Jack DeNeut, Chad Birch, Martin-Louis Bright, Chris Emery, Bob Ippolito, Jomer, John Van Enk, metabaron, Isak Sunde Singh, DaVince, Philipp Gniewosz, Richard Hill, Simon Rüegg, Roman Levin, V, Max Fermor, Mads Johansen, lukvol, Ives van Hoorne, Greg Stoll, Jan De Landtsheer, Scott Munro, Михаил Захаркин, Daniel Strittmatter, Evgeniy Dubovskoy, Sandro, Alex Rudy, Jake Rodkin, Shane Lillie, Romet Tagobert, Geekingfrog, Douglas Creager, Corey Alexander, Molly Howell, Jeff Crocker, knutwalker, Zachary Dremann, Olivier Peyrusse, Sebastian Ziebell, Julien Roncaglia, eigentourist, Amber Kowalski, Charlton Eivind Rodda, Jan Schiefer, Edil Kratskih, Chris Emerson, Matthew Campbell, Krasimir Slavkov, Juniper Wilde, Paul Kline, Pascal Hartig, Samir Talwar, TD, Kristoffer Ström, Henning Schmick, Ryan Levick, Antoine Boegli, Astrid Bek, Ryan, Yoh Deadfall, Justin Ossevoort, Jeremy, Tomáš Duda, playest, Meghana Gupta, Sebastian Dröge, Adam, Nick Gerace, Jeremy Banks, Rasmus Larsen, exelotl, Ramnivas Laddad, Yury Mikhaylov, Torben Clasen, Sam Rose, Nickolas Fotopoulos, C J Silverio, Walther, Pete Bevin, Shane Sveller, Marcel Jackwerth, Brian Dawn, Clara Schultz, Robert Cobb, jer, Wonwoo Choi, Hawken Rives, João Veiga, Dave Gauer, David Cornu, Richard Pringle, Adam Perry, Yann Schwartz, Jaseem Abid, Zinahe Asnake, Ryan Blecher, Benjamin Röjder Delnavaz, Grégoire Hubert, Matt Jadczak, Nazar Mokrynskyi, Julian Hofer, Mara Bos, Brandon, Jonathan Knapp, Maximilian, Seth Stadick, brianloveswords, Sean Bryant, Ember, Sebastian Zimmer, Makoto Nakashima, Geert Depuydt, Geoff Cant, Geoffroy Couprie, Michael Alyn Miller, Vengarioth, o0Ignition0o, Zaki, Raphael Gaschignard, Romain Ruetschi, Ignacio Vergara, Pascal, Cassie Jones, Pat Monaghan, Jane Lusby, Nicolas Goy, Suhib Sam Kiswani, Henry Goffin, Ted Mielczarek, Random832, Ryszard Sommefeldt, Jesús Higueras, Aurora.

This article is part 14 of the Advent of Code 2020 series.

View all series

If you liked this article, please support my work on Patreon!

Become a Patron

Looking for the homepage?
Another article: Working with strings in Rust