NickyMeulemanNime

• ### By

• Nicky Meuleman

• ### Older post

Advent of Code 2022 Day 10

Advent of Code 2022 Day 12

1. Day 11: Monkey in the Middle
2. Parsing
3. Part 1
4. Part 2
1. Final code
5. Final code

# Advent of Code 2022 Day 11

## Day 11: Monkey in the Middle

Monkeys have your belongings and are throwing them to each other!

Each monkey follows a few rules that determine to which other monkey they throw an item.
The monkeys are numbered, and they take turns throwing all their items.
When a monkey throws items, it throws them in order, from oldest to newest.

A determining factor in those rules is how worried you are about an item (expressed as a number, the worry level).

Todayâ€™s input is a list of monkeys with the rules that each one follows.

An example input looks like this:

input.txt
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.css-13aqjzy{display:inline-block;}
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
Monkey 2:  Starting items: 79, 60, 97  Operation: new = old * old  Test: divisible by 13    If true: throw to monkey 1    If false: throw to monkey 3
Monkey 3:  Starting items: 74  Operation: new = old + 3  Test: divisible by 17    If true: throw to monkey 0    If false: throw to monkey 1

Monkey 0 starts with 2 items.

1. the first has worry level 79
2. the second has worry level 98

Whenever a monkey inspects an item, they apply their operation.
This operation changes an itemâ€™s worry level.

Monkey 0 multiplies the worry level of the inspected item by 19.

Before a monkey thows an item, it applies a test to the current worry level.

Monkey 0 checks if the worry level is divisible by 23.

• if it is, it throws the item to monkey 2
• if it is not, it throws the item to monkey 3

## Parsing

I decided to parse the input into a list of Monkeys.

A Monkey directly maps to a monkey in the input.

struct Monkey {    items: Vec<u64>,    operation: Operation,    test: Test,}

An operation is always either a multiplication or an addition.

1. The first operand is always the old worry level.
2. The second operand is either the old worry level or a literal number.

Since the second one is the only one that ever changes, thatâ€™s the one I store.

enum Operation {    Mul(Value),    Add(Value),}
enum Value {    Old,    Num(u64),}

The test has three parts, the divisibility check, which monkey to throw to if it succeeds, and which to throw to if it fails.

struct Test {    divisible: u64,    true_recipient: usize,    false_recipient: usize,}

The parsing code is quite boring, I turn the input into blocks for each monkey.

Every block, I parse into a Monkey and add it to the monkeys list.

To do this I turn each string block into lines, and per line consumed, I extract the wanted info from it.

day_11.rs
fn parse() -> Option<Vec<Monkey>> {    let input = std::fs::read_to_string("src/day11.txt").ok()?;
let mut monkeys = Vec::new();    for block in input.split("\n\n") {        let mut lines = block.lines().skip(1);
let (_, items) = lines.next()?.split_once(": ")?;        let items = items            .split_terminator(", ")            .filter_map(|s| s.parse().ok())            .collect();
let (_, operation) = lines.next()?.split_once("= old ")?;        let (operator, operand) = operation.split_once(" ")?;        let operand = match operand {            "old" => Value::Old,            _ => {                let n = operand.parse().ok()?;                Value::Num(n)            }        };
let (_, divisible) = lines.next()?.rsplit_once(" ")?;        let divisible = divisible.parse().ok()?;        let (_, true_recipient) = lines.next()?.rsplit_once(" ")?;        let true_recipient = true_recipient.parse().ok()?;        let (_, false_recipient) = lines.next()?.rsplit_once(" ")?;        let false_recipient = false_recipient.parse().ok()?;
let operation = match operator {            "+" => Operation::Add(operand),            "*" => Operation::Mul(operand),            _ => panic!("Inalid input"),        };
let test = Test {            divisible,            true_recipient,            false_recipient,        };
let monkey = Monkey {            items,            operation,            test,        };
monkeys.push(monkey);    }
Some(monkeys)}

## Part 1

After each monkey inspects an item but before it tests your worry level, your relief that the monkeyâ€™s inspection didnâ€™t damage the item causes your worry level to be divided by three and rounded down to the nearest integer.

You track the amount of times a monkey inspects any item. The product of the 2 largest amounts is called the monkey business.

The question asks what the level of monkey business is after 20 rounds.

Starting skeleton code for part1:

pseudocode.rs
let mut monkeys = parse().unwrap();let mut inspections = vec![0; monkeys.len()];
for _ in 0..20 {    for idx in 0..monkeys.len() {        let monkey = monkeys[idx];        for item in monkey.items {            // remove item from inventory            // monkey inspects item            // monkey does operation            // you are relieved            // monkey tests worry level            // monkey throws item to other monkey        }    }}

### Helper functions

To make write out those steps a bit clearer, I created a few helpers.

A method on Value gets a number for one whenever you give it the old worry level.

impl Value {    fn number(&self, old: u64) -> u64 {        match self {            Value::Num(n) => *n,            Value::Old => old,        }    }}

A method on Operation does a monkeyâ€™s operation.
It calculated the new worry level if you give it the old worry level.

impl Operation {    fn apply(&self, old: u64) -> u64 {        match &self {            Operation::Add(val) => old + val.number(old),            Operation::Mul(val) => old * val.number(old),        }    }}

Filling in the code from before (and catching the borrow checker issue):

day_11.rs
let mut monkeys = parse().unwrap();let mut inspections = vec![0; monkeys.len()];
for _ in 0..20 {    for idx in 0..monkeys.len() {        // clear the monkey's inventory        let items: Vec<u64> = monkeys[idx].items.drain(..).collect();        let monkey = monkeys[idx].clone();        for old in items {            // inspect            inspections[idx] += 1;            // operation            let new = monkey.operation.apply(old);            // relieved            let new = new / 3;            // test            let idx = if new % monkey.test.divisible == 0 {                monkey.test.true_recipient            } else {                monkey.test.false_recipient            };            let receiver = &mut monkeys[idx];            // throw            receiver.items.push(new);        }    }}
// calculate monkey businessinspections.sort_unstable();inspections.iter().rev().take(2).product()

It works, thatâ€™s part1 done!

### Final code

day_11.rs
pub fn part_1() -> usize {    let mut monkeys = parse().unwrap();    let mut inspections = vec![0; monkeys.len()];
for _ in 0..20 {        for idx in 0..monkeys.len() {            let items: Vec<u64> = monkeys[idx].items.drain(..).collect();            let monkey = monkeys[idx].clone();            for old in items {                // inspect                inspections[idx] += 1;                // operation                let new = monkey.operation.apply(old);                // relieved                let new = new / 3;                // test                let idx = if new % monkey.test.divisible == 0 {                    monkey.test.true_recipient                } else {                    monkey.test.false_recipient                };                let receiver = &mut monkeys[idx];                // throw                receiver.items.push(new);            }        }    }
inspections.sort_unstable();    inspections.iter().rev().take(2).product()}

## Part 2

You are no longer relieved after a monkey inspects an item.

The question asks what the level of monkey business is after 10000 rounds.

Ah, this will be easy, change the 20 to 10000 and remove the / 3 part

me

Well, I was right, but thereâ€™s one very minor, serious problem of needing a supercomputer for this to finish in a reasonable timeframe.

The worry levels get huge.
Absolutely massive.
Gigantic.
Iâ€™m in awe of the size of these numbers.

I took a common multiple of all divisibility checks, and took the modulus of the new worry level with that common multiple before I throw the item. This will not affect any future divisibility checks.

Why doesnâ€™t it matter?:

The future checked item was %ed with a multiple of its divisibility check, this doesnâ€™t affect the result of such a check.

in code:

let common_multiple: u64 = monkeys.iter().map(|monkey| monkey.test.divisible).product();// bla, bla, bla// operationlet new = monkey.operation.apply(old);// not relievedlet new = new % common_multiple;// bla, bla, blareceiver.items.push(new);

And with those changes, part2 is solved!

### Final code

day_11.rs
pub fn part_2() -> usize {    let mut monkeys = parse().unwrap();    let mut inspections = vec![0; monkeys.len()];    let common_multiple: u64 = monkeys.iter().map(|monkey| monkey.test.divisible).product();
for _ in 0..10_000 {        for idx in 0..monkeys.len() {            let items: Vec<u64> = monkeys[idx].items.drain(..).collect();            let monkey = monkeys[idx].clone();            for old in items {                // inspect                inspections[idx] += 1;                // operation                let new = monkey.operation.apply(old);                // not relieved                let new = new % common_multiple;                // test                let idx = if new % monkey.test.divisible == 0 {                    monkey.test.true_recipient                } else {                    monkey.test.false_recipient                };                let receiver = &mut monkeys[idx];                // throw                receiver.items.push(new);            }        }    }
inspections.sort_unstable();    inspections.iter().rev().take(2).product()}

## Final code

day_11.rs
.css-1mjim83{display:inline-block;width:2ch;text-align:right;-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;opacity:0.3;margin-right:0.5rem;}1#[derive(Clone)]2struct Monkey {3    items: Vec<u64>,4    operation: Operation,5    test: Test,6}7
14impl Operation {15    fn apply(&self, old: u64) -> u64 {16        match &self {17            Operation::Add(val) => old + val.number(old),18            Operation::Mul(val) => old * val.number(old),19        }20    }21}22
23#[derive(Clone)]24enum Value {25    Old,26    Num(u64),27}28
29impl Value {30    fn number(&self, old: u64) -> u64 {31        match self {32            Value::Num(n) => *n,33            Value::Old => old,34        }35    }36}37
38#[derive(Clone)]39struct Test {40    divisible: u64,41    true_recipient: usize,42    false_recipient: usize,43}44
45fn parse() -> Option<Vec<Monkey>> {46    let input = std::fs::read_to_string("src/day11.txt").ok()?;47
48    let mut monkeys = Vec::new();49    for block in input.split("\n\n") {50        let mut lines = block.lines().skip(1);51
52        let (_, items) = lines.next()?.split_once(": ")?;53        let items = items54            .split_terminator(", ")55            .filter_map(|s| s.parse().ok())56            .collect();57
58        let (_, operation) = lines.next()?.split_once("= old ")?;59        let (operator, operand) = operation.split_once(" ")?;60        let operand = match operand {61            "old" => Value::Old,62            _ => {63                let n = operand.parse().ok()?;64                Value::Num(n)65            }66        };67
68        let (_, divisible) = lines.next()?.rsplit_once(" ")?;69        let divisible = divisible.parse().ok()?;70        let (_, true_recipient) = lines.next()?.rsplit_once(" ")?;71        let true_recipient = true_recipient.parse().ok()?;72        let (_, false_recipient) = lines.next()?.rsplit_once(" ")?;73        let false_recipient = false_recipient.parse().ok()?;74
75        let operation = match operator {76            "+" => Operation::Add(operand),77            "*" => Operation::Mul(operand),78            _ => panic!("Inalid input"),79        };80
81        let test = Test {82            divisible,83            true_recipient,84            false_recipient,85        };86
87        let monkey = Monkey {88            items,89            operation,90            test,91        };92
93        monkeys.push(monkey);94    }95
96    Some(monkeys)97}98
99pub fn part_1() -> usize {100    let mut monkeys = parse().unwrap();101    let mut inspections = vec![0; monkeys.len()];102
103    for _ in 0..20 {104        for idx in 0..monkeys.len() {105            let items: Vec<u64> = monkeys[idx].items.drain(..).collect();106            let monkey = monkeys[idx].clone();107            for old in items {108                // inspect109                inspections[idx] += 1;110                // operation111                let new = monkey.operation.apply(old);112                // relieved113                let new = new / 3;114                // test115                let idx = if new % monkey.test.divisible == 0 {116                    monkey.test.true_recipient117                } else {118                    monkey.test.false_recipient119                };120                let receiver = &mut monkeys[idx];121                // throw122                receiver.items.push(new);123            }124        }125    }126
127    inspections.sort_unstable();128    inspections.iter().rev().take(2).product()129}130
131pub fn part_2() -> usize {132    let mut monkeys = parse().unwrap();133    let mut inspections = vec![0; monkeys.len()];134    let common_multiple: u64 = monkeys.iter().map(|monkey| monkey.test.divisible).product();135
136    for _ in 0..10_000 {137        for idx in 0..monkeys.len() {138            let items: Vec<u64> = monkeys[idx].items.drain(..).collect();139            let monkey = monkeys[idx].clone();140            for old in items {141                // inspect142                inspections[idx] += 1;143                // operation144                let new = monkey.operation.apply(old);145                // not relieved146                let new = new % common_multiple;147                // test148                let idx = if new % monkey.test.divisible == 0 {149                    monkey.test.true_recipient150                } else {151                    monkey.test.false_recipient152                };153                let receiver = &mut monkeys[idx];154                // throw155                receiver.items.push(new);156            }157        }158    }159
160    inspections.sort_unstable();161    inspections.iter().rev().take(2).product()162}