Advent of Code 2024: Day 03

Code for solutions available on GitHub.

Mull It Over

Today we start getting into parsing instructions for some sort of virtual machine. The input looks something like this:

xmul(2,4)%&mul[3,7]!@^do_not_mul(5,5)+mul(32,64]then(mul(11,8)mul(8,5))

and the task is to parse everything that looks like a multiplication instruction, execute the multiplication, and sum up all results. That is, parse and execute anything on the form mul(x,y), where x and y are 1-3 digit numbers. Anything not adhering to this format is not a valid instruction and should be ignored. Even if you just put whitespaces in.

This limited grammar makes it pretty easy to write a parser with the excellent nom crate. My nom-parser for multiplication instructions looks like this:

let mul_parser = map(
        preceded(
            tag("mul"),
            delimited(
                char('('),
                separated_pair(
                    nom::character::complete::u32,
                    char(','),
                    nom::character::complete::u32,
                ),
                char(')'),
            ),
        ),
        |(a, b)| Instruction::Mul(a, b),
    );

Just dumping it like that is pretty unreadable, but reading it from the inside out, it’s pretty simple. A multiplication instruction consists of a separated_pair of u32s with commas between. These pairs are delimited by parentheses. All of that is preceded by "mul". Finally the result is mapped into an Instruction enum, which is defined like this:

enum Instruction {
    Mul(u32, u32),
    <SPOILER>,
    <SPOILER>,
}

Why an enum? And why spoilers? Well, any time Advent of Code asks you to parse something that seems like a computer instruction, they tend to in part 2 want you to parse more instructions and build up a little virtual machine. Thus we put it all in an enum from the start.

And how to build up the scanning parser that throws away characters until the mul_parser can successfully parse an instruction? That’s where the combinators from nom come into play. We want to many times match anychar, until mul_parser succeeds. And we want to do that many times.

let parser = many0(
    map(many_till(anychar, mul_parser), |(_, x)| x)
);

The map here just throws away the collected input characters that didn’t match the mul_parser.

Now we can just iterate over the result from parsing the input, execute the multiplications, and sum up the answer. The shape of it looks something like this:

let multiplications: Vec<Instruction> = parser(input).unwrap().1.into();

let result = multiplications
    .into_iter()
    // Throw away anything that isn't a Mul instruction
    // I haven't shown anything like that yet, but it's
    // relevant in part 2.
    .filter_map(|x| match x {
        Instruction::Mul(a, b) => Some((a, b)),
        _ => None,
    })
    .map(|(a, b)| a * b)
    .sum();

Part 2

And now it’s time for more instructions. The do() and don't() instructions either enable or disable multiplication in our little virtual machine. Multiplication starts enabled. So any mul(x,y) instructions between a don't() and a do() should be skipped.

The Instruction enum now gets updated to

enum Instruction {
    Mul(u32, u32),
    Do,
    Dont,
}

And we should build a little virtual machine struct that has a list of instructions and a flag to represent whether multiplication is enabled:

struct Machine {
    instructions: VecDeque<Instruction>,
    mul_enabled: bool,
}

Writing the specific parsers for do() and don't() is trivial and left as an exercise to the reader¹. We can then take our three parsers and combine them using the alt combinator:

let instruction_parser = alt((
    do_parser,
    mul_parser,
    dont_parser
));

which will try them all in sequence until one matches or none matches. Then we simply put the parsed instructions into a VecDeque, since we have to execute from the start of it and I chose to do that by .pop_front(). It can also be done with simple iterators, but hey sometimes I like to over-engineer things.

By simply toggling the mul_enabled flag appropriately every time we hit a do() or don't() instruction and skipping the mul(x,y) instructions if the flag is set, it’s pretty simple to implement the machine. Since it’s a little bit over-engineered for no reason, I won’t reproduce the entire thing in this post. You can see the whole thing here if you want to. Implementation is pretty straightforward. :)