By Eric Burden | December 25, 2022
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 21 - Monkey Math
Find the problem description HERE.
The Input - Weird Expressions
Input parsing is the real heavy lift of today’s puzzle. Now, if we were running
Python or Julia or some such, we could use eval() or similar on the inputs
until we get an answer, but where’s the fun in that? Instead, let’s simulate
a context-free grammar and parse these monkey math expressions into something
that looks a bit like an R environment. Could probably have actually gone all
the way to an abstract syntax tree, but nesting structs is a bit of a pain in
Rust. Instead, we’ll store each expression in a HashMap under the name of
the monkey left of the assignment operator, with an Expression as the value.
It’s not so much that there’s an excessive amount of parsing today as the
data structures we’re using are pretty specific.
use anyhow::{bail, Error};
use std::collections::HashMap;
/// Represents the names of each monkey. I originally wanted to use
/// string references as the monkey labels, but that causes borrow
/// checker issues with mutating the Environment (defined below),
/// so I'm using a small, cheap array of characters instead.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
struct Label([char; 4]);
/// Try to convert a string slice to a Label. Only works for string
/// slices with exactly four characters.
impl TryFrom<&str> for Label {
type Error = Error;
fn try_from(value: &str) -> Result<Self, Self::Error> {
if value.len() != 4 {
bail!("Can only convert a 4-character string to Label")
}
let mut out = ['\0'; 4];
for (idx, ch) in value.chars().enumerate() {
out[idx] = ch;
}
Ok(Label(out))
}
}
/// Represents a Value being passed from monkey to monkey. Either a reference
/// to another monkey, or a raw number.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Value {
Ref(Label), // reference
Raw(i128), // raw number
}
/// Converts a string slice into a Value::Ref. Just convenient to have.
impl TryFrom<&str> for Value {
type Error = Error;
fn try_from(value: &str) -> Result<Self, Self::Error> {
Ok(Value::Ref(Label::try_from(value)?))
}
}
/// Represents one of the mathematical expressions being evaluated by a
/// monkey. Every monkey is evaluating an expression, even if it's just
/// to report a value.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Expression {
Add(Value, Value),
Sub(Value, Value),
Mul(Value, Value),
Div(Value, Value),
Val(Value),
}
/// Represents the environment in which monkey math is being evaluated. Keeps
/// track of each variable (monkey) and their current assigned Expression.
#[derive(Debug, Clone)]
struct Environment(HashMap<Label, Expression>);
/// Wraps the parsing functions for today's input.
mod parser {
use super::*;
use anyhow::{anyhow, Result};
use nom::{
branch::alt,
bytes::complete::tag,
character::complete::{alpha1, i128, newline},
combinator::{map, map_res, verify},
multi::separated_list0,
sequence::separated_pair,
Finish, IResult,
};
/// Nom parser for "humn" -> Label(['h', 'u', 'm', 'n'])
fn label(s: &str) -> IResult<&str, Label> {
map_res(alpha1, Label::try_from)(s)
}
/// Nom parser for "humn" -> Value::Ref(Label(['h', 'u', 'm', 'n']))
fn value_ref(s: &str) -> IResult<&str, Value> {
map(label, Value::Ref)(s)
}
/// Nom parser for "15" -> Value::Raw(15)
fn value_raw(s: &str) -> IResult<&str, Value> {
map(i128, Value::Raw)(s)
}
/// Nom parser for monkey addition expressions
fn expr_add(s: &str) -> IResult<&str, (Label, Expression)> {
let (s, lbl) = label(s)?;
let (s, _) = tag(": ")(s)?;
let (s, (v1, v2)) = separated_pair(value_ref, tag(" + "), value_ref)(s)?;
Ok((s, (lbl, Expression::Add(v1, v2))))
}
/// Nom parser for monkey subtraction expressions
fn expr_sub(s: &str) -> IResult<&str, (Label, Expression)> {
let (s, lbl) = label(s)?;
let (s, _) = tag(": ")(s)?;
let (s, (v1, v2)) = separated_pair(value_ref, tag(" - "), value_ref)(s)?;
Ok((s, (lbl, Expression::Sub(v1, v2))))
}
/// Nom parser for monkey multiplication expressions
fn expr_mul(s: &str) -> IResult<&str, (Label, Expression)> {
let (s, lbl) = label(s)?;
let (s, _) = tag(": ")(s)?;
let (s, (v1, v2)) = separated_pair(value_ref, tag(" * "), value_ref)(s)?;
Ok((s, (lbl, Expression::Mul(v1, v2))))
}
/// Nom parser for monkey division expressions
fn div_expr(s: &str) -> IResult<&str, (Label, Expression)> {
let (s, lbl) = label(s)?;
let (s, _) = tag(": ")(s)?;
let (s, (v1, v2)) = separated_pair(value_ref, tag(" / "), value_ref)(s)?;
Ok((s, (lbl, Expression::Div(v1, v2))))
}
/// Nom parser for monkey value expressions
fn val_expr(s: &str) -> IResult<&str, (Label, Expression)> {
let (s, lbl) = label(s)?;
let (s, _) = tag(": ")(s)?;
let (s, value) = value_raw(s)?;
Ok((s, (lbl, Expression::Val(value))))
}
/// Nom parser for all variants of an Expression
fn expression(s: &str) -> IResult<&str, (Label, Expression)> {
alt((val_expr, expr_add, expr_sub, expr_mul, div_expr))(s)
}
/// Nom parser for a newline-separated list of Expressions
fn expressions(s: &str) -> IResult<&str, HashMap<Label, Expression>> {
let (s, exprs) = separated_list0(newline, expression)(s)?;
let exprs = exprs.into_iter().collect::<HashMap<_, _>>();
Ok((s, exprs))
}
/// Parses the input file into an Environment
fn parse(s: &str) -> Result<Environment> {
let (_, result) = expressions(s).finish().map_err(|e| anyhow!("{e}"))?;
Ok(Environment(result))
}
}
const INPUT: &str = include_str!("../../input/21/input.txt");
/// Parse that input!
fn read() -> Environment {
parser::parse(INPUT).unwrap()
}
My first pass through today’s puzzle kept string slices that referred to the
input as the Environment keys, which worked fine for part one. In part two
(spoiler alert), I ended up wanting to modify the Environment, which created
a bunch of lifetime pain. I probably could have gotten around that with
a Cow<&str>, but the little array labels worked just as well.
Part One - King Kalculus
Oh, goodness, it’s the monkeys again! Well, at least this time we have elephants to translate for us so we can communicate with the monkeys instead of simply screaming at them in frustration until we black out. Ah, good times… Anyway, looks like this time the monkeys are trying to be helpful. Well, really, more like “trying”, since it’s entirely possible they could just point us in the right direction without this riddle-solving business. Good thing we like riddles…
/// Solve Day 21, Part 1
fn solve(input: &Environment) -> i128 {
let root = Value::try_from("root").unwrap();
root.eval(input).unwrap()
}
/// Fetch an Expression from the Environment by Label
impl Environment {
fn resolve(&self, var: &Label) -> Option<Expression> {
self.0.get(var).copied()
}
}
/// Trait for evaluating an Expression in an Environment
trait Eval {
fn eval(&self, env: &Environment) -> Option<i128>;
}
impl Eval for Value {
/// Recursively evaluate the Value until a Value::Raw can be returned
fn eval(&self, env: &Environment) -> Option<i128> {
match self {
Value::Ref(var) => env.resolve(var).and_then(|v| v.eval(env)),
Value::Raw(val) => Some(*val),
}
}
}
impl Eval for Expression {
/// Recursively evaluate the Value until a Value::Raw can be returned
fn eval(&self, env: &Environment) -> Option<i128> {
// Perform operations based on the type of Expression
match self {
Expression::Add(v1, v2) => Some(v1.eval(env)? + v2.eval(env)?),
Expression::Sub(v1, v2) => Some(v1.eval(env)? - v2.eval(env)?),
Expression::Mul(v1, v2) => Some(v1.eval(env)? * v2.eval(env)?),
Expression::Div(v1, v2) => Some(v1.eval(env)? / v2.eval(env)?),
Expression::Val(value) => value.eval(env),
}
}
}
Ok, that was a really big number that “root” monkey just added up entirely in his head. I’m starting to wonder whether this whole “translation” thing is entirely necessary. I bet that monkey can speak English, too. They’re probably just humoring the elephants: “Oh, yes, your pronunciation is just fine.” they say.
Part Two - Mass Communication Mishap
Except, as it turns out, the elephants’ pronunciation of monkey isn’t actually all that good. Or maybe it’s our ability to understand elephant. Either way, it looks like we’re participating in this game. We’ll need to figure out what number to shout to get the “root” monkey to have two equal numbers to compare. The good news is that the number of monkeys waiting with bated breath to hear our number is actually pretty small, so only one side of the comparison changes depending on what we shout. This cuts down on the potential complexity a lot.
fn solve(input: &Environment) -> i128 {
use Expression::*;
use Value::*;
// Eject the assignment to the "humn" variable from the environment.
// We'll be calculating that.
let mut env = input.clone();
let humn_lbl = Label::try_from("humn").unwrap();
env.remove(&humn_lbl);
// Since the "root" monkey is supposed to check two numbers for equality,
// let's get the two variables that the boss monkey will be checking and
// determine what we get if we try to evaluate them.
let root_lbl = Label::try_from("root").unwrap();
let Add(left, right) = env.resolve(&root_lbl).unwrap() else { panic!("No root monkey!"); };
// The PartialEval trait attempts to evaluate the calling expression and
// updates each variable in the environment that can be evalutated along
// the way. From this point forward, every variable in the environment
// that doesn't depend on "humn" will be a raw value instead of an expression
// containing references.
let left_val = left.partial_eval(&mut env);
let right_val = right.partial_eval(&mut env);
// Turns out, from examining the input, there's only one path that depends
// on the "humn" variable. This means that one of the two variables being
// checked will be constant and the other will depend on the value of
// "humn". So. let's check what we got from evaluating the left and right
// variables and see which one returned an actual value. That will be the
// value we start adjusting moving forward. The other variable value will
// represent the formula we need to solve.
let (mut carry, mut next_op) = match (left_val, right_val) {
(lhs, Val(Raw(val))) => (val, Some(lhs)),
(Val(Raw(val)), rhs) => (val, Some(rhs)),
_ => unreachable!(),
};
// Since we know that both values checked by the "root" monkey must be equal,
// then we know enough to start solving each expression from `next_op` all
// the way to the value of "humn". For example, say we had the following
// set of relationships:
//
// - root = 5 == abcd (5)
// - abcd = 10 - efgh -> 5 = 10 - efgh -> efgh = 10 - 5 -> efgh = 5
// - efgh = 60 / ijkl -> 5 = 60 / ijkl -> ijkl = 60 / 5 -> ijkl = 12
// - ijkl = 3 * humn -> 12 = 3 * humn -> humn = 12 / 3 -> humn = 4
//
// Thus, we can calculate the value of "humn" by substituting values into
// formulae and solving by rearrangement one formula at a time until we
// find the value of "humn".
while let Some(expr) = next_op {
// Rearrange the expressions based on the value we're carrying forward and
// the type of operation being performed. There's a lot of "unreachable"
// points along the way that are possible because we know that every
// variable that doesn't depend on "humn" has already been fully evaluated.
(carry, next_op) = match expr {
Add(lhs, rhs) => match (lhs, rhs) {
(Ref(lhs), Raw(val)) => (carry - val, env.resolve(&lhs)),
(Raw(val), Ref(rhs)) => (carry - val, env.resolve(&rhs)),
(_, _) => unreachable!(),
},
Sub(lhs, rhs) => match (lhs, rhs) {
(Ref(lhs), Raw(val)) => (val + carry, env.resolve(&lhs)),
(Raw(val), Ref(rhs)) => (val - carry, env.resolve(&rhs)),
(_, _) => unreachable!(),
},
Mul(lhs, rhs) => match (lhs, rhs) {
(Ref(lhs), Raw(val)) => (carry / val, env.resolve(&lhs)),
(Raw(val), Ref(rhs)) => (carry / val, env.resolve(&rhs)),
(_, _) => unreachable!(),
},
Div(lhs, rhs) => match (lhs, rhs) {
(Ref(lhs), Raw(val)) => (val * carry, env.resolve(&lhs)),
(Raw(val), Ref(rhs)) => (val / carry, env.resolve(&rhs)),
(_, _) => unreachable!(),
},
Val(_) => unreachable!(),
};
}
carry.into()
}
/// Remove an expression from the Environment based on Label
impl Environment {
fn remove(&mut self, label: &Label) -> Option<Expression> {
self.0.remove(label)
}
}
/// This trait is used to evaluate Expressions in an Environment, updating
/// the Environment whenever a variable is evaluated. Going forward, the
/// Environment will have variables as fully evaluated as possible upon
/// which the expression that calls PartialEval depends.
trait PartialEval {
fn partial_eval(&self, env: &mut Environment) -> Expression;
}
impl PartialEval for Value {
fn partial_eval(&self, env: &mut Environment) -> Expression {
use Expression::*;
use Value::*;
match self {
// This is where the magic happens. Every time a reference is
// successfully evaluated, update the Environment with its new
// value.
Ref(var) => {
let Some(expr) = env.resolve(var) else { return Val(*self); };
let eval = expr.partial_eval(env);
env.0.insert(*var, eval);
eval
}
_ => Val(*self),
}
}
}
impl PartialEval for Expression {
fn partial_eval(&self, env: &mut Environment) -> Expression {
use Expression::*;
use Value::*;
// For each type of expression, if it can be fully evaluated, do so. If
// only one side can be evaluated, evaluate that one and retain the other
// as-is.
match self {
Add(v1, v2) => match (v1.partial_eval(env), v2.partial_eval(env)) {
(Val(Raw(lhs)), Val(Raw(rhs))) => Val(Raw(lhs + rhs)),
(_, Val(Raw(rhs))) => Add(*v1, Raw(rhs)),
(Val(Raw(lhs)), _) => Add(Raw(lhs), *v2),
(_, _) => *self,
},
Sub(v1, v2) => match (v1.partial_eval(env), v2.partial_eval(env)) {
(Val(Raw(lhs)), Val(Raw(rhs))) => Val(Raw(lhs - rhs)),
(_, Val(Raw(rhs))) => Sub(*v1, Raw(rhs)),
(Val(Raw(lhs)), _) => Sub(Raw(lhs), *v2),
(_, _) => *self,
},
Mul(v1, v2) => match (v1.partial_eval(env), v2.partial_eval(env)) {
(Val(Raw(lhs)), Val(Raw(rhs))) => Val(Raw(lhs * rhs)),
(_, Val(Raw(rhs))) => Mul(*v1, Raw(rhs)),
(Val(Raw(lhs)), _) => Mul(Raw(lhs), *v2),
(_, _) => *self,
},
Div(v1, v2) => match (v1.partial_eval(env), v2.partial_eval(env)) {
(Val(Raw(lhs)), Val(Raw(rhs))) => Val(Raw(lhs / rhs)),
(_, Val(Raw(rhs))) => Div(*v1, Raw(rhs)),
(Val(Raw(lhs)), _) => Div(Raw(lhs), *v2),
(_, _) => *self,
},
// Obviously, a value has fewer options
Expression::Val(value) => value.partial_eval(env),
}
}
}
Lots of match statements in that, but it all boils down to relatively simple
math. I won’t reveal how long it took me to realize it was relatively simple
math, but once I got that part, the rest sort of fell into place.
Wrap Up
Today was an incredibly fun puzzle. I really enjoyed working out how to represent today’s problem space. The recursive evaluation for part one was really straightforward, and so was the step-wise “solve for x” approach to part two once I realized that that would work. I suspect this was actually the intended solution for today, because once you realize it, it’s just so “obvious” that it should work this way. Implementing it in code brought a whole host of considerations, but in the end, it was figuring out how to translate a logical, understandable process into code. Something about that just scratches an itch for me, and I honestly found today’s puzzle to be pretty calming, overall.