Thanks to my sponsors: Matt Jackson, Dennis Henderson, Blake Johnson, Vincent, Dylan Anthony, Romain Ruetschi, Paige Ruten, Alex Krantz, Gorazd Brumen, belzael, Dom, Chris Thackrey, Adam Gutglick, David E Disch, budrick, jer, anichno, WeblWabl, compwhizii, Cass and 243 more

Dec 30, 2020

12 min #rust · #advent-of-code

Day 14 (Advent of Code 2020)

From the series Advent of Code 2020

1

2

3

4

5

6

7

8

9

10

11

12

13

14

👋 This page was last updated ~4 years ago. Just so you know.

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}$ - 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

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:

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

$ 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$

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:

$\begin{aligned} mask \quad \enspace\enspace\enspace1\enspace\enspace\enspace\enspace0\enspace \\ set \quad 0001000000 \\ clear \quad 0000000010 \\ \end{aligned}$

$\begin{matrix} \text{mask} & X & X & X & 1 & X & X & X & X & 0 & X \cr \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

$ cargo add peg
      Adding peg v0.6.3 to dependencies

We'll need some types:

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:

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:

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:

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

Using the first sample input:

$ 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 $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:

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:

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>());
}

$ 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.)

$ 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

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

$ 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:

$\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:

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:

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<_>>());
    }
}

$ 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}$ , 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!

$ cargo add itertools
      Adding itertools v0.10.0 to dependencies

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<_>>()
        );
    }
}

$ 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}$ 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.

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!

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:

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}$ characters, just like the input.

It's easy enough:

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:

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);
        }
    }
}

$ 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):

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:

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:

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);
    }
}

$ 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.

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:

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);
        }
    }
}

$ 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:

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>());
}

$ 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:

$ cargo run --quiet
Answer: 3415488160714

Woo, correct!

Only eleven puzzles left. Phew.

You've somehow finished reading Advent of Code 2020.

Here's another article just for you:

Aiming for correctness with types

Dec 12, 2020

1 hour 30 min #javascript · #typescript · #golang · #rust

The Nature weekly journal of science was first published in 1869. And after one and a half century, it has finally completed one cycle of carcinization, by publishing an article about the Rust programming language.

It's a really good article.

What I liked about this article is that it didn't just talk about performance, or even just memory safety - it also talked about correctness.