It’s that time of year again! Just like last year, I’ll be posting my solutions to the Advent of Code puzzles. This year, I’ll be solving the puzzles in Rust. I’ll post my solutions and code to GitHub as well. After finishing last year (and 2015-2019) in Julia, I needed to spend some time with Rust again! If you haven’t given AoC a try, I encourage you to do so along with me!
Day 11 - Monkey in the Middle
Find the problem description HERE.
The Input - N Little Monkeys Swinging in a Tree
Today’s input has us pulling a relatively few numbers out of a good amount of filler text. For a change, nom feels like it made this task easier today. Either I’m getting better, this was exactly the sort of task nom was made for, or a little bit of both. Either way, I’ll take it!
/// Represents one of those mischeivous monkies! Contains fields
/// for the items the monkey is currently holding, the operation
/// performed when the monkey inspects an item, the rule the monkey
/// uses to decide who to throw the item to, and the number of
/// items the monkey has inspected so far.
#[derive(Debug, Clone)]
struct Monkey {
id: usize,
items: Vec<u64>,
operation: Operation,
rule: Rule,
inspected: u32,
}
/// Represents the operation performed to determine what happens to your
/// worry level over a particular item inspected by a monkey.
#[derive(Debug, Clone, Copy)]
enum Operation {
Add(u64),
Mult(u64),
Square,
}
/// Represents the rule used by a monkey to determine which other monkey to
/// throw your item to, based on your worry level.
#[derive(Debug, Clone, Copy)]
struct Rule {
divisor: u64,
success: usize,
fail: usize,
}
/// Wraps the parser combinators for parsing our input into a list of pesky monkies.
mod parser {
use super::*;
use anyhow::{anyhow, Result};
use nom::{
branch::alt,
bytes::complete::tag,
character::complete::{multispace1, newline, one_of, space1, u64},
combinator::{map, value},
multi::separated_list1,
sequence::{delimited, preceded, separated_pair, terminated, tuple},
Finish, IResult,
};
/// Nom parser for "Monkey 3:" -> 3usize
fn id(s: &str) -> IResult<&str, usize> {
map(delimited(tag("Monkey "), u64, tag(":")), |n| n as usize)(s)
}
/// Nom parser for "Starting items: 1, 2, 3" -> VecDeque<[1, 2, 3]>
fn items(s: &str) -> IResult<&str, Vec<u64>> {
let prefix = preceded(space1, tag("Starting items: "));
let list = separated_list1(tag(", "), u64);
map(preceded(prefix, list), Vec::from)(s)
}
/// Nom parser for "+ 5" -> Operation::Add(5)
fn add_op(s: &str) -> IResult<&str, Operation> {
map(preceded(tag("+ "), u64), Operation::Add)(s)
}
/// Nom parser for "* 5" -> Operation::Mult(5)
fn mult_op(s: &str) -> IResult<&str, Operation> {
map(preceded(tag("* "), u64), Operation::Mult)(s)
}
/// Nom parser for "* old" -> Operation::Square
fn square_op(s: &str) -> IResult<&str, Operation> {
value(Operation::Square, tag("* old"))(s)
}
/// Nom parser to detect the string that comes before the operator
/// when parsing an operation.
fn op_prefix(s: &str) -> IResult<&str, &str> {
preceded(space1, tag("Operation: new = old "))(s)
}
/// Nom parser for:
/// - "Operation: new = old + 5" -> Operation::Add(5)
/// - "Operation: new = old * 5" -> Operation::Mult(5)
/// - "Operation: new = old * old" -> Operation::Square
fn op(s: &str) -> IResult<&str, Operation> {
let add = preceded(op_prefix, add_op);
let mult = preceded(op_prefix, mult_op);
let square = preceded(op_prefix, square_op);
alt((add, mult, square))(s)
}
/// Nom parser for extracting the relevant values from the three
/// lines that describe the rules the monkey uses to determine where
/// to throw your item, used ton construct a `Rule`. For example:
///
/// Test: divisible by 17
/// If true: throw to monkey 0
/// If false: throw to monkey 5
///
/// becomes
///
/// Rule { divisor: 17, success: 0, fail: 5 }
fn test_rule(s: &str) -> IResult<&str, Rule> {
let (s, divisor) = preceded(space1, preceded(tag("Test: divisible by "), u64))(s)?;
let (s, success) =
preceded(multispace1, preceded(tag("If true: throw to monkey "), u64))(s)?;
let (s, fail) = preceded(
multispace1,
preceded(tag("If false: throw to monkey "), u64),
)(s)?;
let rule = Rule {
divisor,
success: success as usize,
fail: fail as usize,
};
Ok((s, rule))
}
/// Nom parser for converting a chunk of the input into a `Monkey`.
fn monkey(s: &str) -> IResult<&str, Monkey> {
let (s, id) = terminated(id, newline)(s)?;
let (s, items) = terminated(items, newline)(s)?;
let (s, operation) = terminated(op, newline)(s)?;
let (s, rule) = test_rule(s)?;
let monkey = Monkey {
id,
items,
operation,
rule,
inspected: 0,
};
Ok((s, monkey))
}
/// Splits the input file into chunks based on empty lines and parses
/// each chunk into a `Monkey`. Returns the list of `Monkey`s if
/// successful or the relevant nom Error if not.
pub fn parse(s: &str) -> Result<Vec<Monkey>> {
let result = separated_list1(tag("\n\n"), monkey)(s);
let (s, monkeys) = result
.finish()
.map_err(|e| anyhow!("Failed to parse monkeys with error {e}"))?;
Ok(monkeys)
}
}
const INPUT: &str = include_str!("../../input/11/input.txt");
/// Parse that input!
fn read() -> Vec<Monkey> {
parser::parse(INPUT).unwrap()
}
And now, let’s relive some childhood trauma!
Part One - Baboon Bullies
It’s middle school, all over again! Except this time, there are actual _monkeys_involved. Thankfully, we have the power of computation on our side, so we can easily retrieve our items! What’s that, you say? Our pale, out-of-shape body doesn’t stand a chance catching all the monkeys and we need to settle on just two? Figures.
use itertools::Itertools;
/// Solve Day 11, Part 1
fn solve(input: &[Monkey]) -> u64 {
// Initiate a cruel, cruel game played by monkeys
let mut monkey_game: CruelGame = CruelGame::from(input);
// "Play" the game for 20 rounds
(0..20).for_each(|_| monkey_game.play());
// Return the maximum monkey business, AKA the product of the
// number of items handled by the two most rambunctious monkeys.
monkey_game.max_monkey_business()
}
/// Represents the cruel and insensitive game being played by the monkeys,
/// at your expense. Includes fields for the list of monkeys where their index
/// also indicates their ID and for the items currently flying through the
/// air from one monkey to another.
struct CruelGame {
items_in_flight: Vec<(u64, usize)>,
monkeys: Vec<Monkey>,
}
impl CruelGame {
/// Produce a `CruelGame` from a list of monkeys
fn from(monkeys: &[Monkey]) -> Self {
let monkeys = monkeys.to_vec();
let items_in_flight = Vec::new();
CruelGame { items_in_flight, monkeys }
}
/// "Play" one round of the "game".
fn play(&mut self) {
// For each monkey...
for id in 0..self.monkeys.len() {
// Have the monkey handle each item it's currently holding, adding
// items to the list of items in flight after handling each.
self.monkeys[id].handle_items(&mut self.items_in_flight);
// For each item in flight, have the monkey it was tossed to deftly
// snatch it, along with your hopes and dreams, from the air.
while let Some((item, target)) = self.items_in_flight.pop() {
self.monkeys[target].catch(item);
}
}
}
/// Calculate and return the maximum monkey business. Identifies the number
/// of items handled by each monkey and returns the product of the two
/// largest totals.
fn max_monkey_business(&self) -> u64 {
let monkey_business: Vec<_> = self.monkeys
.iter()
.map(|m| m.inspected)
.sorted_unstable()
.rev()
.take(2)
.collect();
(monkey_business[0] * monkey_business[1]).into()
}
}
impl Monkey {
/// Have a monkey handle your precious items with callous disregard
/// for your concerns.
fn handle_items(&mut self, items_in_flight: &mut Vec<(u64, usize)>) {
// For each item the monkey has...
while let Some(mut item) = self.items.pop() {
// Increase your worry over that item according to the puzzle rules.
item = self.operation.apply(item);
// Calm down a bit since the monkey didn't break it (this time).
item /= 3;
// Have the monkey decide on a target with a mischievous gleam in
// its beady monkey eyes.
let target = self.rule.check(item);
// Toss the item to its intended target.
items_in_flight.push((item, target));
// Increment the number of items this monkey has inspected
self.inspected += 1;
}
}
/// Catch an item thrown from another monkey. Probably pretend to fumble it
/// or something just to get that human even more riled up.
pub fn catch(&mut self, item: u64) {
self.items.push(item);
}
}
impl Operation {
/// Apply an operation to an item's worry score.
pub fn apply(&self, item: u64) -> u64 {
match self {
Operation::Add(n) => item + n,
Operation::Mult(n) => item * n,
Operation::Square => item * item,
}
}
}
impl Rule {
/// Check an item's worry score and return which monkey ID to throw
/// the item to.
pub fn check(&self, item: u64) -> usize {
if item % self.divisor == 0 {
self.success
} else {
self.fail
}
}
}
Ok, we’ve figured out which two monkeys to chase, and it doesn’t look like they’ve broken anything yet. That’s a silver lining, at least. Good thing it wasn’t any worse.
Part Two - Just Jinxed It
Of course it got worse! The monkeys are apparently offended that we thought we stood a chance against these agile little devil-spawn. Now they’re handling our items so roughly that we can’t even console ourselves that they don’t seem to be trying to destroy our stuff. There has to be a better way to cope with the stress of this awful situation. And now they’re going 500x faster!
use itertools::Itertools;
/// Solve Day 11, Part 2
pub fn solve(input: &Input) -> Output {
// Similar to last time, but somehow worse...
let mut monkey_game = WorseGame::from(input);
// One of the ways it's worse is that it goes on for 500x longer
(0..10_000).for_each(|_| monkey_game.play_rough());
// Calculate and return the extreme level of monkey business
monkey_game.max_monkey_business().into()
}
/// Represents the more intense version of the cruel, cruel game being played by
/// these dastardly monkeys. Includes the same fields as the original `CruelGame`,
/// plus the limit where your stress levels become overwhelming and you black out,
/// experiencing short-term memory loss.
pub struct WorseGame {
items_in_flight: Vec<(u64, usize)>,
monkeys: Vec<Monkey>,
absolute_limit: u64,
}
impl WorseGame {
// Start up a much worse version of the monkey game
fn from(monkeys: &[Monkey]) -> Self {
let monkeys = monkeys.to_vec();
let items_in_flight = Vec::new();
// In order to keep the computer from blowing its stack, too, we need to
// identify the periodicity of the item worry values. This turns out to
// be the least common multiple of all the monkey rule divisors by which
// the monkeys check where to fling your things. Since all these divisors
// are prime, this is the product of all the divisors.
let absolute_limit = monkeys.iter().map(|m| m.rule.divisor).product();
WorseGame { items_in_flight, monkeys, absolute_limit }
}
// The monkeys have upped their level of maliciousness and now pretend to drop
// and break your items on each turn. You're pretty sure they've broken a few
// things already, but they're throwing them so fast you can't tell for sure.
fn play_rough(&mut self) {
// For each monkey...
for id in 0..self.monkeys.len() {
// Have the monkey handle each item it's currently holding with obnoxious
// roughness and glee, adding items to the list of items in flight after
// handling each.
self.monkeys[id].handle_items_roughly(self.absolute_limit, &mut self.items_in_flight);
// For each item in flight, have the monkey it was tossed to deftly
// snatch it, along with your hopes and dreams, from the air.
while let Some((item, target)) = self.items_in_flight.pop() {
self.monkeys[target].catch(item);
}
}
}
/// Calculate and return the maximum monkey business. Identifies the number
/// of items handled by each monkey and returns the product of the two
/// largest totals.
fn max_monkey_business(&self) -> u64 {
let monkey_business: Vec<_> = self.monkeys
.iter()
.map(|m| m.inspected)
.sorted_unstable()
.rev()
.take(2)
.collect();
(monkey_business[0] as u64 * monkey_business[1] as u64)
}
}
impl Monkey {
/// Have a monkey handle your precious items with exuberant malice, purposely
/// stoking your alarm.
fn handle_items_roughly(
&mut self,
absolute_limit: u64,
items_in_flight: &mut Vec<(u64, usize)>,
) {
while let Some(mut item) = self.items.pop() {
// Increase your worry over that item according to the puzzle rules.
item = self.operation.apply(item);
// Black out for a moment from the stress caused by these monkeys
// tossing your precious things about, experiencing an odd form of
// amnesia and "resetting" your stress levels a bit.
item %= absolute_limit;
// Have the monkey decide on a target with a malicious glint in
// its beady monkey eyes.
let target = self.rule.check(item);
// Toss the item to its intended target.
items_in_flight.push((item, target));
// Increment the number of items this monkey has inspected
self.inspected += 1;
}
}
}
A bit of explanation is in order, here. See, we no longer get to reduce our worry level per item by two-thirds each time a monkey inspects it without causing utter destruction. We still need to reduce the worry level per item, though, otherwise we’ll quickly outgrow reasonable integer sizes and start wrapping values. Actually, wrapping values would work if we could do it in such a way as not to interfere with the monkey rules for determining where to toss the items. Let’s consider the simplest case: One monkey who makes a decision about where to throw an item based on whether or not the worry level is divisble by 2 (simple, right?) and who adds one to worry each time.
worry
0 % 2 (0) == 0 > true
1 % 2 (1) == 0 > false
2 % 2 (0) == 0 > true
3 % 2 (1) == 0 > false
4 % 2 (0) == 0 > true
5 % 2 (1) == 0 > false
6 % 2 (0) == 0 > true
7 % 2 (1) == 0 > false
8 % 2 (0) == 0 > true
Ok, there’s an obvious pattern here. Does it work with two monkeys with rule divisors of 2 and 3?
worry monkey 2 monkey 3 combo
0 % 2 (0) == 0 > true % 3 (0) == 0 > true true & true = pattern
1 % 2 (1) == 0 > false % 3 (1) == 0 > false false & false |
2 % 2 (0) == 0 > true % 3 (2) == 0 > false true & false |
3 % 2 (1) == 0 > false % 3 (0) == 0 > true false & true |
4 % 2 (0) == 0 > true % 3 (1) == 0 > false true & false |
5 % 2 (1) == 0 > false % 3 (2) == 0 > false false & false |
6 % 2 (0) == 0 > true % 3 (0) == 0 > true true & true = pattern
7 % 2 (1) == 0 > false % 3 (1) == 0 > false false & false |
8 % 2 (0) == 0 > true % 3 (2) == 0 > false true & false |
9 % 2 (1) == 0 > false % 3 (0) == 0 > true false & true |
10 % 2 (0) == 0 > true % 3 (1) == 0 > false true & false |
11 % 2 (1) == 0 > false % 3 (2) == 0 > false false & false |
12 % 2 (0) == 0 > true % 3 (0) == 0 > true true & true =
There, see, there’s a pattern! And notice where the pattern starts to repeat itself, a the least common multiple of 2 and 3 (6). If you keep adding numbers, the pattern continues. For “fun”, try it yourself with the numbers 2, 3, and 5. You’ll notice a repeating pattern every multiple of 30, I bet. So, what does this mean? It means that every time a monkey handles an item, we can take the item’s worry level modulo the least common multiple of all the monkey divisors as the new worry level without impacting any monkey decisions! And, since all the monkey divisors are prime numbers, the least common multiple is just the product of all the monkey divisors. Something simple, at least!
Wrap Up
This was a fun one! The “one weird trick” to go from part one to part two was cool. I definitely ended up facepalming a bit when I realized during part one that all the monkey rule divisors were primes, and then spaced on exactly how that helped me in part two for the better part of an hour. After a bit of time away from keyboard, though, it came to me. Anecdotally, I do find that I solve more thorny problems with code on a walk or in the shower than I do just staring at a screen. Plus, it’s a nicer experience, overall. It seems like we’re starting to get into the phase of Advent of Code where the difficulty is starting to climb a bit. Let’s see what the rest of the year brings!
Top comments (0)