Day 11 (Advent of Code 2022)
fasterthanlime
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:
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.
$ cargo add nom@7 (cut)
We'll need some types:
// 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:
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:
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:
$ 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:
$ 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:
// 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:
// 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:
$ 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:
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:
// new: no space combinator
let (i, _) = tuple((tag("Monkey "), cc::u64, tag(":\n")))(i)?;
I then get:
$ 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:
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:
$ 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:
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?
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:
$ 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:
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:
// 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:
$ 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:
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:
$ cargo run --quiet --release [src/main.rs:63] monkey_business = 2635878448
And a debug build notes that, our numbers are, like, overflowing:
$ 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?
$ 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.
#[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.
#[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():
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:
// 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:
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:
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:
$ 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:
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:
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:
$ 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.
If you liked what you saw, please support my work!
