Advent of Code 2022 Day 21

Day 21: Monkey Math

https://adventofcode.com/2022/day/21

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:

input.txt

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:
1. A number
Or it’s Calculated, and knows 3 things:
1. The name of the left-hand side monkey
2. An operator
3. The name of the right-hand 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").

day_21.rs

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 in lhs as name parameter.
Calculate the rhs number using that same helper function, this time passing in rhs as name parameter.
return the result of applying the Operation to lhs_num and rhs_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

day_21.rs

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 of 10.
"aaa" is a Calculated 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

day_21.rs

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

day_21.rs

1use std::collections::HashMap;
2
3#[derive(Debug)]
4enum Monkey<'a> {
5    Num(i64),
6    // (operator, lhs, rhs)
7    Calculated(Operator, &'a str, &'a str),
8}
9
10#[derive(Debug)]
11enum Operator {
12    Add,
13    Sub,
14    Mul,
15    Div,
16}
17
18fn parse(input: &str) -> HashMap<&str, Monkey> {
19    input
20        .lines()
21        .map(|line| {
22            let (name, right) = line.split_once(": ").unwrap();
23            let monkey = match right.parse() {
24                Ok(n) => Monkey::Num(n),
25                Err(_) => {
26                    let mut iter = right.split_ascii_whitespace();
27                    let lhs = iter.next().unwrap();
28                    let operator = match iter.next().unwrap() {
29                        "+" => Operator::Add,
30                        "-" => Operator::Sub,
31                        "*" => Operator::Mul,
32                        "/" => Operator::Div,
33                        _ => panic!("Invalid math operator"),
34                    };
35                    let rhs = iter.next().unwrap();
36                    Monkey::Calculated(operator, lhs, rhs)
37                }
38            };
39
40            (name, monkey)
41        })
42        .collect()
43}
44
45fn calc_name(name: &str, monkeys: &HashMap<&str, Monkey>) -> i64 {
46    match &monkeys[name] {
47        Monkey::Num(n) => *n,
48        Monkey::Calculated(operator, lhs, rhs) => {
49            let lhs_num = calc_name(lhs, monkeys);
50            let rhs_num = calc_name(rhs, monkeys);
51            match operator {
52                Operator::Add => lhs_num + rhs_num,
53                Operator::Sub => lhs_num - rhs_num,
54                Operator::Mul => lhs_num * rhs_num,
55                Operator::Div => lhs_num / rhs_num,
56            }
57        }
58    }
59}
60
61fn depends_on_human(name: &str, monkeys: &HashMap<&str, Monkey>) -> bool {
62    if name == "humn" {
63        return true;
64    }
65    match &monkeys[name] {
66        Monkey::Num(_) => false,
67        Monkey::Calculated(_, lhs, rhs) => {
68            depends_on_human(lhs, monkeys) || depends_on_human(rhs, monkeys)
69        }
70    }
71}
72
73/// calc human assuming the evaluated name and the passed value are equal
74fn calc_human(name: &str, value: i64, monkeys: &HashMap<&str, Monkey>) -> i64 {
75    if name == "humn" {
76        return value;
77    }
78
79    match &monkeys[name] {
80        // never gets hit
81        Monkey::Num(n) => *n,
82        // reorder all operations to solve for unknown side
83        Monkey::Calculated(operator, lhs, rhs) => {
84            // lhs + rhs = value
85            // lhs - rhs = value
86            // lhs * rhs = value
87            // lhs / rhs = value
88            let (new_name, new_value) = if depends_on_human(lhs, monkeys) {
89                let rhs_num = calc_name(rhs, monkeys);
90                let new_value = match operator {
91                    // lhs = value - rhs
92                    Operator::Add => value - rhs_num,
93                    // lhs = value + rhs
94                    Operator::Sub => value + rhs_num,
95                    // lhs = value / rhs
96                    Operator::Mul => value / rhs_num,
97                    // lhs = value * rhs
98                    Operator::Div => value * rhs_num,
99                };
100                (lhs, new_value)
101            } else {
102                let lhs_num = calc_name(lhs, monkeys);
103                let new_value = match operator {
104                    // rhs = value - lhs
105                    Operator::Add => value - lhs_num,
106                    // rhs = lhs - value
107                    Operator::Sub => lhs_num - value,
108                    // rhs = value / lhs
109                    Operator::Mul => value / lhs_num,
110                    // rhs = lhs / value
111                    Operator::Div => lhs_num / value,
112                };
113                (rhs, new_value)
114            };
115
116            calc_human(new_name, new_value, monkeys)
117        }
118    }
119}
120
121pub fn part_1() -> i64 {
122    let input = std::fs::read_to_string("src/day21_sample.txt").unwrap();
123    let monkeys = parse(&input);
124
125    calc_name("root", &monkeys)
126}
127
128pub fn part_2() -> i64 {
129    let input = std::fs::read_to_string("src/day21.txt").unwrap();
130    let monkeys = parse(&input);
131    // which side of the "tree" (hehe, a monkey tree) is "humn" in
132    let Monkey::Calculated(_, lhs, rhs) = &monkeys["root"] else {
133        panic!("root has to be a calculated monkey");
134    };
135
136    let (name, value) = if depends_on_human(lhs, &monkeys) {
137        let rhs_num = calc_name(rhs, &monkeys);
138        (lhs, rhs_num)
139    } else {
140        let lhs_num = calc_name(lhs, &monkeys);
141        (rhs, lhs_num)
142    };
143
144    calc_human(name, value, &monkeys)
145}

Date

By

Tagged

Part of series

Older post

Newer post

Advent of Code 2022 Day 21

Day 21: Monkey Math

Parsing

Part 1

Helpers

Final code

Part 2

Helpers

Final code

Final code