Advent of Rust // Day 11

//

I love that each Advent of Code reminds me at one point that I never paid much attention in math class. Part one of day 11 was, as usual, straightforward. With the divider gone and the number of rounds up to 10.000 in part two, I knew I was fucked. I made a desperate attempt to crunch it using BigInt, but when I returned to my computer after a couple of hours, it was still crunching. Of course, I had forgotten to add debug output, so I didn’t even know if it was in the 500 or 5.000 iteration.

So I tried to keep the numbers from overflowing. I was right about using modulo, but that was it already. I eventually gave up and looked at other solutions. In a way, it makes sense to me, but if you asked me to explain it to a 5-year-old, I probably couldn’t. This would be a chance to catch up on something I missed in school. But then again, I’m lagging behind and want to move forward. Maybe next year.

Aside from the math, I had fun with mutable references. Having two mutable monkeys in a loop isn’t something Rust is happy about. I discovered Cell/RefCell from the cell module, which allows you to have mutable references inside an immutable reference. I feel that I have abused this functionality and that there is probably a very simple solution that I just can’t see due to my lack of experience with Rust. If you read the source code below and your brain starts to hurt, I would appreciate it if you could give me a hint as to where I took a wrong turn.

struct Monkey {  
    items: RefCell<Vec<u64>>,  
    operation: String,  
    divisible: u64,  
    divisible_true: usize,  
    divisible_false: usize,  
    inspections: Cell<u64>,  
}  
  
impl Monkey {  
    fn next_monkey(&self, worry_level: u64) -> usize {  
        if worry_level % self.divisible == 0 { self.divisible_true } else { self.divisible_false }  
    }  
  
    fn worry_level(&self, worry_level: &u64) -> u64 {  
        let operation = self.operation.replace("old", worry_level.to_string().as_str());  
        let mut iter = operation.splitn(3, " ");  
        let left = iter.next().unwrap().parse::<u64>().unwrap();  
        let operator = iter.next().unwrap();  
        let right = iter.next().unwrap().parse::<u64>().unwrap();  
  
        return match operator {  
            "+" => left + right,  
            "*" => left * right,  
            _ => panic!("unexpected operator {operator}")  
        };  
    }  
  
    fn increment_inspections(&self) {  
        self.inspections.set(self.inspections.get() + 1);  
    }  
  
    fn drain_items(&self) -> Vec<u64> {  
        return self.items.take();  
    }  
  
    fn add_item(&self, worry_level: &u64) {  
        self.items.borrow_mut().push(*worry_level);  
    }  
}

I still haven’t looked at parser combinators and have resorted to good ol' regex. It’s not pretty, but it’s concise, I can crank it out, and it just works™

fn monkeys_from_input(input: &str) -> Vec<Monkey> {
    let re = Regex::new(r"(?x)
        Monkey\ (?P<monkey>\d+):\n
        \ \ Starting\ items:\ (?P<items>.+)\n
        \ \ Operation:\ new\ =\ (?P<operation>.+)\n
        \ \ Test:\ divisible\ by\ (?P<divisible>.+)\n
        \ \ \ \ If\ true:\ throw\ to\ monkey\ (?P<divisible_true>.+)\n
        \ \ \ \ If\ false:\ throw\ to\ monkey\ (?P<divisible_false>.+)"
    ).unwrap();

    return re.captures_iter(input)
        .map(|item| Monkey {
            items: RefCell::new(item.name("items").unwrap().as_str().split(", ")
                .map(|i| u64::from(i.parse::<u64>().unwrap()))
                .collect()),
            operation: String::from(item.name("operation").unwrap().as_str()),
            divisible: item.name("divisible").unwrap().as_str().parse().unwrap(),
            divisible_true: item.name("divisible_true").unwrap().as_str().parse().unwrap(),
            divisible_false: item.name("divisible_false").unwrap().as_str().parse().unwrap(),
            inspections: Cell::new(0),
        })
        .collect();
}

The rest is simple: iterate, calculate, delegate.

fn inspections(monkeys: &mut Vec<Monkey>, rounds: u64, divisor: u64, divprod: u64) -> u64 {
    for _ in 0..rounds {
        for index in 0..monkeys.len() {
            let monkey = monkeys.get(index).unwrap();

            for current_worry_level in monkey.drain_items() {
                monkey.increment_inspections();

                let mut new_worry_level = monkey.worry_level(&current_worry_level) / divisor;

                if divprod != 0 {
                    new_worry_level %= divprod;
                }

                monkeys[monkey.next_monkey(new_worry_level)].add_item(&new_worry_level);
            }
        }
    }

    return monkeys.iter().map(|m| m.inspections.get()).sorted().rev().take(2).product();
}

fn part_one(input: &str) -> u64 {
    let mut monkeys = monkeys_from_input(input);

    return inspections(&mut monkeys, 20, 3, 0);
}

fn part_two(input: &str) -> u64 {
    let mut monkeys = monkeys_from_input(input);
    let divprod: u64 = monkeys.iter().map(|m| m.divisible).product();

    return inspections(&mut monkeys, 10_000, 1, divprod);
}

The full source and solutions for the others puzzles of Advent of Code can be found in my GitHub repository.

See also in Advent of Rust

Comments

You can leave a comment by replying to this post on Mastodon.