Day 21: Monkey Math
https://adventofcode.com/2022/day/21
TL;DR: my solution in Rust
The monkeys are back.
Loud bunch. They do one of two things:
 Yell a number
 Yell the result of a math operation
The number monkeys know their number from the start
The operation monkeys know their operator and names of 2 other monkeys whose number they should operate on.
Once they can do their operation, they yell the result.
An example input looks like this:
root: pppw + sjmn
dbpl: 5
cczh: sllz + lgvd
zczc: 2
ptdq: humn  dvpt
dvpt: 3
lfqf: 4
humn: 5
ljgn: 2
sjmn: drzm * dbpl
sllz: 4
pppw: cczh / lfqf
lgvd: ljgn * ptdq
drzm: hmdt  zczc
hmdt: 32
Before the colon is the name of the monkey.
After the colon is either a number, or an operation that depends on the results of 2 other monkeys.
Parsing
I chose to parse every monkey as a variant of a Monkey
enum.
 It's either
Num
, and knows 1 thing: A number
 Or it's
Calculated
, and knows 3 things: The name of the lefthand side monkey
 An operator
 The name of the righthand side monkey.
enum Monkey<'a> {
Num(i64),
// (operator, lhs, rhs)
Calculated(Operator, &'a str, &'a str),
}
#[derive(Debug)]
enum Operator {
Add,
Sub,
Mul,
Div,
}
The parsing function takes a parameter this time, a reference to the input string.
The reasons are unimportant (for this post), and Rust specific (yay, lifetimes).
It turns every line into a Monkey
, and collects them all into a map that maps names to monkeys.
So for the example if I look up "root"
, that maps returns Monkey::Calculated(Operator::Add, "pppw", "sjmn")
.
fn parse(input: &str) > HashMap<&str, Monkey> {
input
.lines()
.map(line {
let (name, right) = line.split_once(": ").unwrap();
let monkey = match right.parse() {
Ok(n) => Monkey::Num(n),
Err(_) => {
let mut iter = right.split_ascii_whitespace();
let lhs = iter.next().unwrap();
let operator = match iter.next().unwrap() {
"+" => Operator::Add,
"" => Operator::Sub,
"*" => Operator::Mul,
"/" => Operator::Div,
_ => panic!("Invalid math operator"),
};
let rhs = iter.next().unwrap();
Monkey::Calculated(operator, lhs, rhs)
}
};
(name, monkey)
})
.collect()
}
Part 1
The question asks what number the monkey named "root" will yell?
Funny name for a monkey, but alright.
(it's a hint we're dealing with a graph problem here, it's the root node of a tree)
The answer: RECURSION!
Recursion is a bit mindbendy to get your head around at first.
Computerphile did a gread video on it with an explanation:
Helpers
So a recursive helper function that evaluates a Monkey
's number given a name.
If the monkey with name
is a Monkey::Num
, return the num it holds.
If the monkey with name
is a Monkey::Calculated
:
 Calculate the
lhs
number using that same helper function, this time passing inlhs
asname
parameter.  Calculate the
rhs
number using that same helper function, this time passing inrhs
asname
parameter.  return the result of applying the
Operation
tolhs_num
andrhs_num
.
fn calc_name(name: &str, monkeys: &HashMap<&str, Monkey>) > i64 {
match &monkeys[name] {
Monkey::Num(n) => *n,
Monkey::Calculated(operator, lhs, rhs) => {
let lhs_num = calc_name(lhs, monkeys);
let rhs_num = calc_name(rhs, monkeys);
match operator {
Operator::Add => lhs_num + rhs_num,
Operator::Sub => lhs_num  rhs_num,
Operator::Mul => lhs_num * rhs_num,
Operator::Div => lhs_num / rhs_num,
}
}
}
}
With that, part1 boils down to calling calc_name
with "root"
as name
.
Final code
pub fn part_1() > i64 {
let input = std::fs::read_to_string("src/day21.txt").unwrap();
let monkeys = parse(&input);
calc_name("root", &monkeys)
}
Part 2
Woopsie! The job for the monkey named "root"
was wrong.
It's actually checking for equality between the 2 monkeys it has as lhs
and rhs
.
Also, the monkey named humn
isn't a monkey at all, it's you!
The input has humn
as shouting a number, but it's wrong.
The question asks what number "humn"
needs to yell to make "root"
's equality check pass.
The "root" monkey depends on 2 other monkeys.
Only one of those 2 can ever depend on "humn".
The other one can be calculated using the helper from part1.
Helpers
A function that determines if a monkey needs to know the "humn" number to calculate their number.
Again, recurse if the monkey is a Calculated
one.
If either its lhs
or rhs
depend on "humn", it depends on "humn" too.
fn depends_on_human(name: &str, monkeys: &HashMap<&str, Monkey>) > bool {
if name == "humn" {
return true;
}
match &monkeys[name] {
Monkey::Num(_) => false,
Monkey::Calculated(_, lhs, rhs) => {
depends_on_human(lhs, monkeys)  depends_on_human(rhs, monkeys)
}
}
}
The next helper is a function that calculates the value a monkey should say, if the calculated name
and the passed value
should be equal.
For example.
If you pass in "root"
and 10
.
It will return the value "humn"
should say in order for "root"
to evaluate to 10
.
This is done by first calculating the monkey (lhs
or rhs
) that doesn't depends on "humn"
and evaluating it.
Then reordering the equation the passed in (name
) monkey does to solve for the only remaining unknown (the side that depends on "humn"
).
A different example:
 Monkey with name
"aaa"
should have a value of10
. 
"aaa"
is aCalculated
monkey that adds"bbb"
and"ccc"
. 
"bbb"
evaluates to 4 "ccc"
depends on"humn"
and remains unknown."aaa"
=10
"aaa"
="bbb"
+"ccc"
Plugging in the calculated number for "aaa"
:

10
="bbb"
+"ccc
Plugging in the calculated number for "bbb"
:

10
=4
+"ccc
That means we can calculate what "ccc"
has to be.

"ccc"
=10
4
=6
fn calc_human(name: &str, value: i64, monkeys: &HashMap<&str, Monkey>) > i64 {
if name == "humn" {
return value;
}
match &monkeys[name] {
// never gets hit
Monkey::Num(n) => *n,
// reorder all operations to solve for unknown side
Monkey::Calculated(operator, lhs, rhs) => {
// lhs + rhs = value
// lhs  rhs = value
// lhs * rhs = value
// lhs / rhs = value
let (new_name, new_value) = if depends_on_human(lhs, monkeys) {
let rhs_num = calc_name(rhs, monkeys);
let new_value = match operator {
// lhs = value  rhs
Operator::Add => value  rhs_num,
// lhs = value + rhs
Operator::Sub => value + rhs_num,
// lhs = value / rhs
Operator::Mul => value / rhs_num,
// lhs = value * rhs
Operator::Div => value * rhs_num,
};
(lhs, new_value)
} else {
let lhs_num = calc_name(lhs, monkeys);
let new_value = match operator {
// rhs = value  lhs
Operator::Add => value  lhs_num,
// rhs = lhs  value
Operator::Sub => lhs_num  value,
// rhs = value / lhs
Operator::Mul => value / lhs_num,
// rhs = lhs / value
Operator::Div => lhs_num / value,
};
(rhs, new_value)
};
calc_human(new_name, new_value, monkeys)
}
}
}
Final code
pub fn part_2() > i64 {
let input = std::fs::read_to_string("src/day21.txt").unwrap();
let monkeys = parse(&input);
// which side of the "tree" (hehe, a monkey tree) is "humn" in
let Monkey::Calculated(_, lhs, rhs) = &monkeys["root"] else {
panic!("root has to be a calculated monkey");
};
let (name, value) = if depends_on_human(lhs, &monkeys) {
let rhs_num = calc_name(rhs, &monkeys);
(lhs, rhs_num)
} else {
let lhs_num = calc_name(lhs, &monkeys);
(rhs, lhs_num)
};
calc_human(name, value, &monkeys)
}
Final code
use std::collections::HashMap;
#[derive(Debug)]
enum Monkey<'a> {
Num(i64),
// (operator, lhs, rhs)
Calculated(Operator, &'a str, &'a str),
}
#[derive(Debug)]
enum Operator {
Add,
Sub,
Mul,
Div,
}
fn parse(input: &str) > HashMap<&str, Monkey> {
input
.lines()
.map(line {
let (name, right) = line.split_once(": ").unwrap();
let monkey = match right.parse() {
Ok(n) => Monkey::Num(n),
Err(_) => {
let mut iter = right.split_ascii_whitespace();
let lhs = iter.next().unwrap();
let operator = match iter.next().unwrap() {
"+" => Operator::Add,
"" => Operator::Sub,
"*" => Operator::Mul,
"/" => Operator::Div,
_ => panic!("Invalid math operator"),
};
let rhs = iter.next().unwrap();
Monkey::Calculated(operator, lhs, rhs)
}
};
(name, monkey)
})
.collect()
}
fn calc_name(name: &str, monkeys: &HashMap<&str, Monkey>) > i64 {
match &monkeys[name] {
Monkey::Num(n) => *n,
Monkey::Calculated(operator, lhs, rhs) => {
let lhs_num = calc_name(lhs, monkeys);
let rhs_num = calc_name(rhs, monkeys);
match operator {
Operator::Add => lhs_num + rhs_num,
Operator::Sub => lhs_num  rhs_num,
Operator::Mul => lhs_num * rhs_num,
Operator::Div => lhs_num / rhs_num,
}
}
}
}
fn depends_on_human(name: &str, monkeys: &HashMap<&str, Monkey>) > bool {
if name == "humn" {
return true;
}
match &monkeys[name] {
Monkey::Num(_) => false,
Monkey::Calculated(_, lhs, rhs) => {
depends_on_human(lhs, monkeys)  depends_on_human(rhs, monkeys)
}
}
}
/// calc human assuming the evaluated name and the passed value are equal
fn calc_human(name: &str, value: i64, monkeys: &HashMap<&str, Monkey>) > i64 {
if name == "humn" {
return value;
}
match &monkeys[name] {
// never gets hit
Monkey::Num(n) => *n,
// reorder all operations to solve for unknown side
Monkey::Calculated(operator, lhs, rhs) => {
// lhs + rhs = value
// lhs  rhs = value
// lhs * rhs = value
// lhs / rhs = value
let (new_name, new_value) = if depends_on_human(lhs, monkeys) {
let rhs_num = calc_name(rhs, monkeys);
let new_value = match operator {
// lhs = value  rhs
Operator::Add => value  rhs_num,
// lhs = value + rhs
Operator::Sub => value + rhs_num,
// lhs = value / rhs
Operator::Mul => value / rhs_num,
// lhs = value * rhs
Operator::Div => value * rhs_num,
};
(lhs, new_value)
} else {
let lhs_num = calc_name(lhs, monkeys);
let new_value = match operator {
// rhs = value  lhs
Operator::Add => value  lhs_num,
// rhs = lhs  value
Operator::Sub => lhs_num  value,
// rhs = value / lhs
Operator::Mul => value / lhs_num,
// rhs = lhs / value
Operator::Div => lhs_num / value,
};
(rhs, new_value)
};
calc_human(new_name, new_value, monkeys)
}
}
}
pub fn part_1() > i64 {
let input = std::fs::read_to_string("src/day21_sample.txt").unwrap();
let monkeys = parse(&input);
calc_name("root", &monkeys)
}
pub fn part_2() > i64 {
let input = std::fs::read_to_string("src/day21.txt").unwrap();
let monkeys = parse(&input);
// which side of the "tree" (hehe, a monkey tree) is "humn" in
let Monkey::Calculated(_, lhs, rhs) = &monkeys["root"] else {
panic!("root has to be a calculated monkey");
};
let (name, value) = if depends_on_human(lhs, &monkeys) {
let rhs_num = calc_name(rhs, &monkeys);
(lhs, rhs_num)
} else {
let lhs_num = calc_name(lhs, &monkeys);
(rhs, lhs_num)
};
calc_human(name, value, &monkeys)
}
Top comments (0)