Day 11 (Advent of Code 2022)

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

It's a new day, it's a new advent of code puzzle.

In that one, we have to apparently cosplay as an IBM mainframe and just.. crunch them numbers. This doesn't look fun, and I can't think of a clever twist to make it fun, so let's try to make it short and sweet.

Parsing

Our input looks like this:

Rust code
Monkey 0:
  Starting items: 79, 98
  Operation: new = old * 19
  Test: divisible by 23
    If true: throw to monkey 2
    If false: throw to monkey 3

Monkey 1:
  Starting items: 54, 65, 75, 74
  Operation: new = old + 6
  Test: divisible by 19
    If true: throw to monkey 2
    If false: throw to monkey 0

(etc)

So, okay, at least we get to see multi-line parsers in nom or whatever.

Shell session
$ cargo add nom@7
(cut)

We'll need some types:

Rust code
// in `src/parse.rs`

#[derive(Debug, Clone)]
pub struct Monkey {
    pub items_inspected: u64,
    pub items: Vec<u64>,
    pub operation: Operation,
    pub divisor: u64,
    pub receiver_if_true: usize,
    pub receiver_if_false: usize,
}

#[derive(Clone, Copy, Debug)]
pub enum Operation {
    Add(Term, Term),
    Mul(Term, Term),
}

impl Operation {
    pub fn eval(self, old: u64) -> u64 {
        match self {
            Operation::Add(l, r) => l.eval(old) + r.eval(old),
            Operation::Mul(l, r) => l.eval(old) * r.eval(old),
        }
    }
}

#[derive(Clone, Copy, Debug)]
pub enum Term {
    Old,
    Constant(u64),
}

impl Term {
    pub fn eval(self, old: u64) -> u64 {
        match self {
            Term::Old => old,
            Term::Constant(c) => c,
        }
    }
}

And then, whoa here we go:

Rust code
use nom::{
    branch::alt,
    bytes::complete::tag,
    character::complete as cc,
    character::complete::{one_of, space1},
    combinator::{map, value},
    error::ParseError,
    multi::separated_list1,
    sequence::{preceded, tuple},
    IResult,
};

pub fn parse_term(i: &str) -> IResult<&str, Term> {
    alt((value(Term::Old, tag("old")), map(cc::u64, Term::Constant)))(i)
}

pub fn parse_operation(i: &str) -> IResult<&str, Operation> {
    let (i, (l, op, r)) =
        preceded(tag("new = "), tuple((parse_term, one_of("*+"), parse_term)))(i)?;
    let op = match op {
        '*' => Operation::Mul(l, r),
        '+' => Operation::Add(l, r),
        _ => unreachable!(),
    };
    Ok((i, op))
}

pub fn parse_monkey(i: &str) -> IResult<&str, Monkey> {
    // Sample input:
    // Monkey 0:
    //   Starting items: 79, 98
    //   Operation: new = old * 19
    //   Test: divisible by 23
    //     If true: throw to monkey 2
    //     If false: throw to monkey 3

    let (i, _) = tuple((space1, tag("Monkey "), cc::u64, tag(":\n")))(i)?;
    // we could use "preceded" but at this point the nesting gets a bit confusing
    let (i, (_, _, items, _)) = tuple((
        space1,
        tag("Starting items: "),
        separated_list1(tag(", "), cc::u64),
        tag("\n"),
    ))(i)?;
    let (i, (_, _, operation, _)) =
        tuple((space1, tag("Operation: "), parse_operation, tag("\n")))(i)?;
    let (i, (_, _, divisor, _)) =
        tuple((space1, tag("Test: divisible by "), cc::u64, tag("\n")))(i)?;
    let (i, (_, _, receiver_if_true, _)) = tuple((
        space1,
        tag("If true: throw to monkey "),
        map(cc::u64, |x| x as usize),
        tag("\n"),
    ))(i)?;
    let (i, (_, _, receiver_if_false, _)) = tuple((
        space1,
        tag("If false: throw to monkey "),
        map(cc::u64, |x| x as usize),
        tag("\n"),
    ))(i)?;

    Ok((
        i,
        Monkey {
            items_inspected: 0,
            items,
            operation,
            divisor,
            receiver_if_true,
            receiver_if_false,
        },
    ))
}

pub fn parse_all_monkeys(i: &str) -> IResult<&str, Vec<Monkey>> {
    separated_list1(tag("\n"), parse_monkey)(i)
}

Then, from the main file:

Rust code
use nom::{combinator::all_consuming, Finish};
use parse::parse_all_monkeys;

mod parse;

fn main() {
    let monkeys = all_consuming(parse_all_monkeys)(include_str!("sample-input.txt"))
        .finish()
        .unwrap()
        .1;
    for monkey in &monkeys {
        println!("{monkey:?}");
    }
}

This, unfortunately, does not work with the sample input:

Shell session
$ cargo run
(cut)
thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: Error { input: "Monkey 0:\n  Starting items: 79, 98\n  Operation: new = old * 19\n  Test: divisible by 23\n    If true: throw to monkey 2\n    If false: throw to monkey 3\n\nMonkey 1:\n  Starting items: 54, 65, 75, 74\n  Operation: new = old + 6\n  Test: divisible by 19\n    If true: throw to monkey 2\n    If false: throw to monkey 0\n\nMonkey 2:\n  Starting items: 79, 60, 97\n  Operation: new = old * old\n  Test: divisible by 13\n    If true: throw to monkey 1\n    If false: throw to monkey 3\n\nMonkey 3:\n  Starting items: 74\n  Operation: new = old + 3\n  Test: divisible by 17\n    If true: throw to monkey 0\n    If false: throw to monkey 1", code: Space }', src/main.rs:9:10
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

But the good news is this problem is good for something, because I can talk about how to make nom errors be, how can I put it politely... more palatable.

Nice parser errors

Now's as good a time as any to try this:

Shell session
$ cargo add nom-supreme@0.8
(cut)

$ cargo add nom_locate@4
(cut)

$ cargo add miette@5 -F fancy
(cut)

$ cargo add thiserror
(cut)

So, we make a Span type alias, and then we make our parsers generic over the error type:

Rust code
// in `src/parse.rs`

use nom::error::ParseError; // omitted: a gazillion other `nom` imports
use nom_locate::LocatedSpan;

pub type Span<'a> = LocatedSpan<&'a str>;

// omitted: types, and all other parsers: they look just like that
// now. used to take `&str` and now they take `Span<'a>`.

pub fn parse_all_monkeys<'a, E: ParseError<Span<'a>>>(
    i: Span<'a>,
) -> IResult<Span<'a>, Vec<Monkey>, E> {
    separated_list1(tag("\n"), parse_monkey)(i)
}

And then, well, then we kinda just glue everything together:

Rust code
// in `src/main.rs`

use miette::GraphicalReportHandler;
use nom_supreme::{
    error::{BaseErrorKind, ErrorTree, GenericErrorTree},
    final_parser::final_parser,
};

mod parse;
use parse::{parse_all_monkeys, Span};

#[derive(thiserror::Error, Debug, miette::Diagnostic)]
#[error("bad input")]
struct BadInput {
    #[source_code]
    src: &'static str,

    #[label("{kind}")]
    bad_bit: miette::SourceSpan,

    kind: BaseErrorKind<&'static str, Box<dyn std::error::Error + Send + Sync>>,
}

fn main() {
    let input_static = include_str!("sample-input.txt");
    let input = Span::new(input_static);

    let monkeys_res: Result<_, ErrorTree<Span>> =
        final_parser(parse_all_monkeys::<ErrorTree<Span>>)(input);
    let monkeys = match monkeys_res {
        Ok(monkeys) => monkeys,
        Err(e) => {
            match e {
                GenericErrorTree::Base { location, kind } => {
                    let offset = location.location_offset().into();
                    let err = BadInput {
                        src: input_static,
                        bad_bit: miette::SourceSpan::new(offset, 0.into()),
                        kind,
                    };
                    let mut s = String::new();
                    GraphicalReportHandler::new()
                        .render_report(&mut s, &err)
                        .unwrap();
                    println!("{s}");
                }
                GenericErrorTree::Stack { .. } => todo!("stack"),
                GenericErrorTree::Alt(_) => todo!("alt"),
            }
            return;
        }
    };

    for monkey in &monkeys {
        println!("{monkey:?}");
    }
}

Is this the proper way to join all that together? Maybe not! But it gets me this:

Shell session
$ cargo run --quiet

  × bad input
   ╭─[1:1]
 1 │ Monkey 0:
   · ▲
   · ╰── expected a space or tab
 2 │   Starting items: 79, 98
   ╰────

And that's pretty good. Even better with colors:

The same error as above, except with colors. The arrow with 'expected a space or tab' message is purple, the line numbers are a tasteful dark grey, and the cross before 'bad input' is red

So I messed it up, of course! There's no spacing before Monkey 0, whereas I used space1. I could use space0, just for safety, or be strict and just not add a "space" combinator at all:

Rust code
    // new: no space combinator
    let (i, _) = tuple((tag("Monkey "), cc::u64, tag(":\n")))(i)?;

I then get:

Shell session
$ cargo run --quiet

  × bad input
   ╭─[2:1]
 2 │   Starting items: 79, 98
 3 │   Operation: new = old * 19
   ·                       ▲
   ·                       ╰── error in OneOf
 4 │   Test: divisible by 23
   ╰────

And that's helpful too! For maximum helpfulness, we could use a context combinator (nom-supreme provides a better one) and improve our nom-to-miette mapper, but I think I know what's wrong here:

Rust code
pub fn parse_operation<'a, E: ParseError<Span<'a>>>(
    i: Span<'a>,
) -> IResult<Span<'a>, Operation, E> {
    let (i, (l, op, r)) = preceded(
        tag("new = "),
        tuple((
            parse_term,
            // these are new: we didn't allow for whitespace here:
            preceded(space1, one_of("*+")),
            preceded(space1, parse_term),
        )),
    )(i)?;
    let op = match op {
        '*' => Operation::Mul(l, r),
        '+' => Operation::Add(l, r),
        _ => unreachable!(),
    };
    Ok((i, op))
}

I'm now getting:

Shell session
$ cargo run --quiet

  × bad input
    ╭─[20:1]
 20 │     If false: throw to monkey 3
 21 │
    · ▲
    · ╰── expected eof
 22 │ Monkey 3:
    ╰────

And this is a fun one! In the last thing we parse from parse_monkey, we require a trailing \n. But the file doesn't end with a \n! So, there's several ways to fix it.

One is to remove that tag("\n") from parse_monkey, and have parse_all_monkeys be:

Rust code
pub fn parse_all_monkeys<'a, E: ParseError<Span<'a>>>(
    i: Span<'a>,
) -> IResult<Span<'a>, Vec<Monkey>, E> {
    separated_list1(cc::multispace1, parse_monkey)(i)
}

That works. But you know what's a much dirtier way to fix it?

Rust code
    let input_static = concat!(include_str!("sample-input.txt"), "\n");

That's right. It's pretending the output had a trailing linefeed all along.

And finally we're done with parsing:

Rust code
$ cargo run --quiet
Monkey { items_inspected: 0, items: [79, 98], operation: Mul(Old, Constant(19)), divisor: 23, receiver_if_true: 2, receiver_if_false: 3 }
Monkey { items_inspected: 0, items: [54, 65, 75, 74], operation: Add(Old, Constant(6)), divisor: 19, receiver_if_true: 2, receiver_if_false: 0 }
Monkey { items_inspected: 0, items: [79, 60, 97], operation: Mul(Old, Old), divisor: 13, receiver_if_true: 1, receiver_if_false: 3 }
Monkey { items_inspected: 0, items: [74], operation: Add(Old, Constant(3)), divisor: 17, receiver_if_true: 0, receiver_if_false: 1 }

Part 1 solution

Here's a function to apply the rules:

Rust code
fn do_round(monkeys: &mut [Monkey]) {
    let num_monkeys = monkeys.len();

    #[allow(clippy::needless_range_loop)]
    for i in 0..num_monkeys {
        // for "monkey copy"
        let mc;

        {
            let monkey = &mut monkeys[i];
            mc = monkey.clone();
            monkey.items_inspected += mc.items.len() as u64;
        }

        for mut item in mc.items.iter().copied() {
            item = mc.operation.eval(item);
            item /= 3;
            if item % mc.divisor == 0 {
                monkeys[mc.receiver_if_true].items.push(item);
            } else {
                monkeys[mc.receiver_if_false].items.push(item);
            }
        }
        monkeys[i].items.clear();
    }
}

You'll notice it uses a clone of the Monkey struct so it can still mutate monkeys by index: this is slightly overkill, but not by much. I'm okay with it.

looks at paper This just says: "I can do what I want".

Exactly.

And then the bottom half of main becomes:

Rust code
    // our initial `monkeys` binding was immutable, but we can just shadow
    // it with another one that's mutable! pro-tip right there.
    let mut monkeys = monkeys;
    for i in 0..20 {
        println!("Round {}", i + 1);
        do_round(&mut monkeys);
        for monkey in &monkeys {
            println!("{monkey:?}");
        }
    }

    // could do better with `itertools` but we've blown through our third-party
    // crate budget already.
    let mut all_inspect_counts = monkeys
        .iter()
        .map(|m| m.items_inspected)
        .collect::<Vec<_>>();
    all_inspect_counts.sort_by_key(|&c| std::cmp::Reverse(c));
    let monkey_business = all_inspect_counts.into_iter().take(2).product::<u64>();
    dbg!(monkey_business);

And we get:

Shell session
$ cargo run --quiet --release
(cut)
Round 20
Monkey { items_inspected: 101, items: [10, 12, 14, 26, 34], operation: Mul(Old, Constant(19)), divisor: 23, receiver_if_true: 2, receiver_if_false: 3 }
Monkey { items_inspected: 95, items: [245, 93, 53, 199, 115], operation: Add(Old, Constant(6)), divisor: 19, receiver_if_true: 2, receiver_if_false: 0 }
Monkey { items_inspected: 7, items: [], operation: Mul(Old, Old), divisor: 13, receiver_if_true: 1, receiver_if_false: 3 }
Monkey { items_inspected: 105, items: [], operation: Add(Old, Constant(3)), divisor: 17, receiver_if_true: 0, receiver_if_false: 1 }
[src/main.rs:67] monkey_business = 10605

Which is correct for the sample and... also works for my input!

Part 2

In Part 2, we have to remove the /= 3, and also do ten thousand (10_000) rounds, which I imagine is designed to make the numbers explode.

In fact, let's try that:

Rust code
    let mut monkeys = monkeys;
    for _ in 0..10_000 {
        do_round(&mut monkeys);
    }

(Don't forget to remove the /= 3)

A release build happily gives us the wrong answer:

Shell session
$ cargo run --quiet --release
[src/main.rs:63] monkey_business = 2635878448

And a debug build notes that, our numbers are, like, overflowing:

Shell session
$ cargo run --quiet
thread 'main' panicked at 'attempt to multiply with overflow', src/parse.rs:37:37
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

The Advent of Code problem says "you'll need to find another way to keep your worry levels manageable" which is code for "ahAH! this is the part of the event that's for shape rotators only".

So even though I have an idea on how to proceed, let's try something else first, because I resent it for trying to make me do maths.

Can we bigints?

Shell session
$ cargo add num-bigint
(cut)

My guess is that it'll just get slower and slower and they picked 10K rounds specifically to fuck with me (and anyone who's using Python/Ruby/etc. for this)

So, I'm gonna do that in a branch and roll everything back when it inevitably doesn't work.

Rust code
#[derive(Debug, Clone)]
pub struct Monkey {
    pub items_inspected: u64,
    pub items: Vec<BigUint>,
    pub operation: Operation,
    pub divisor: BigUint,
    pub receiver_if_true: usize,
    pub receiver_if_false: usize,
}

Similarly, the Term constant can now be a BigUint for convenience. This means we can no longer derive Copy - but we can still derive Clone.

Rust code
#[derive(Clone, Debug)]
pub enum Operation {
    Add(Term, Term),
    Mul(Term, Term),
}

#[derive(Clone, Debug)]
pub enum Term {
    Old,
    Constant(BigUint),
}

The u64 in the eval methods needs to change to a BigUint as well, and we no longer have Copy semantics, so we need to be more purposeful about when to pass by reference / when to .clone():

Rust code
impl Operation {
    pub fn eval(&self, old: &BigUint) -> BigUint {
        match self {
            Operation::Add(l, r) => l.eval(old) + r.eval(old),
            Operation::Mul(l, r) => l.eval(old) * r.eval(old),
        }
    }
}

impl Term {
    pub fn eval(&self, old: &BigUint) -> BigUint {
        match self {
            Term::Old => old.clone(),
            Term::Constant(c) => c.clone(),
        }
    }
}

We can sprinkle some conversion routines in our parsers: the input fits as u64 anyway:

Rust code
    // somewhere in `parse_monkey`
    let (i, (_, _, items, _)) = tuple((
        space1,
        tag("Starting items: "),
        //                                           👇
        separated_list1(tag(", "), map(cc::u64, BigUint::from)),
        tag("\n"),
    ))(i)?;

    // rinse/repeat for `divisor`

The do_round function survives relatively unscathed:

Rust code
fn do_round(monkeys: &mut [Monkey]) {
    let num_monkeys = monkeys.len();
    // we need a zero constant to compare against:
    let zero: BigUint = 0_u64.into();

    #[allow(clippy::needless_range_loop)]
    for i in 0..num_monkeys {
        // for "monkey copy"
        let mc;

        {
            let monkey = &mut monkeys[i];
            mc = monkey.clone();
            monkey.items_inspected += mc.items.len() as u64;
        }

        // no longer using `.copied()`, `item` is now a reference
        for item in mc.items.iter() {
            let item = mc.operation.eval(item);
            // must clone `item` and `divisor` to calculate the modulo here,
            // that's unfortunate:
            if item.clone() % mc.divisor.clone() == zero {
                monkeys[mc.receiver_if_true].items.push(item);
            } else {
                monkeys[mc.receiver_if_false].items.push(item);
            }
        }
        monkeys[i].items.clear();
    }
}

And just to keep track of where we are, let's print every hundred rounds:

Rust code
    let mut monkeys = monkeys;
    for i in 0..10_000 {
        if i % 100 == 0 {
            println!("Round {i:?}")
        }
        do_round(&mut monkeys);
    }

As expected, things get really slow after 600 rounds or so:

Shell session
$ cargo run --release
   Compiling day11 v0.1.0 (/home/amos/bearcove/aoc2022/day11)
    Finished release [optimized] target(s) in 0.88s
     Running `target/release/day11`
Round 0
Round 100
Round 200
Round 300
Round 400
Round 500
Round 600
Round 700
Round 800
(cut)

So here we are. Called it! The problem is working exactly as intended: we have to use maths.

Math check

So I'm entirely too tired for this, but I have the feeling that, because all the tests are merely "is this divisible by X"? We should be able to reduce numbers by reducing them to the remainder of integer division (modulo) by the product of all the divisors.

In main:

Rust code
    let divisor_product = monkeys.iter().map(|m| m.divisor).product::<u64>();
    dbg!(divisor_product);

    let mut monkeys = monkeys;
    for _ in 0..10_000 {
        do_round(&mut monkeys, divisor_product);
    }

And then:

Rust code
fn do_round(monkeys: &mut [Monkey], divisor_product: u64) {
    let num_monkeys = monkeys.len();

    #[allow(clippy::needless_range_loop)]
    for i in 0..num_monkeys {
        // for "monkey copy"
        let mc;

        {
            let monkey = &mut monkeys[i];
            mc = monkey.clone();
            monkey.items_inspected += mc.items.len() as u64;
        }

        for mut item in mc.items.iter().copied() {
            // 👇
            item %= divisor_product;
            item = mc.operation.eval(item);
            if item % mc.divisor == 0 {
                monkeys[mc.receiver_if_true].items.push(item);
            } else {
                monkeys[mc.receiver_if_false].items.push(item);
            }
        }
        monkeys[i].items.clear();
    }
}

That works for the sample input:

Shell session
$ cargo run
   Compiling day11 v0.1.0 (/home/amos/bearcove/aoc2022/day11)
    Finished dev [unoptimized + debuginfo] target(s) in 0.46s
     Running `target/debug/day11`
[src/main.rs:53] divisor_product = 96577
[src/main.rs:66] monkey_business = 2713310158

And my real input.

I must admit I don't love the day 11 puzzle. It's a kind of "have you already seen this once" tax, and yes, I've been to university, so I have. I haven't had to use it since, so, yay for uni credits I guess.

I don't love it because Advent of Code doesn't come with a maths course. So someone going at it alone has a good chance of getting stuck there — there's no way to arrive at that solution other than knowing certain properties, you can't arrive at it incrementally.

In 2020 I gave up after day 14, let's see how long this one keeps being fun.

This article is part 11 of the Advent of Code 2022 series.

Read the next part

If you liked what you saw, please support my work!

Github logo Donate on GitHub Patreon logo Donate on Patreon

Latest video View all

video cover image
C++ vs Rust: which is faster?

I ported some Advent of Code solutions from C/C++ to Rust, and used the opportunity to compare performance. When I couldn't explain why they performed differently, I had no choice but to disassemble both and look at what the codegen was like!

Watch now
Looking for the homepage?
Another article: I won free load testing