Advent of Code 2022: Days 20 and 21

Two more down, today. Magit has been awesome, and I think I made it through the entirety of both of these problems without reflexively opening a terminal to solve some problem I encountered (either regarding git, or basic file manipulation)!

Day 20

A short one, though not as quick as it could have been; I ran into some off-by-one errors, and some issues with the remainder operator when going negative. (Wikipedia has a quick review; Rust’s modulo (%) operator uses the truncated division variant. I wanted Euclidian modulo, which is now available as a method on numeric types! See the RFC, the implementation PR, or the docs.)

Source code

use std::fs;

#[allow(dead_code)]
fn print_current_order(original_order: &Vec<i64>, positions: &Vec<usize>) {
    println!(
        "{}\n",
        positions
            .iter()
            .map(|p| original_order[*p].to_string())
            .reduce(|a, b| a + ", " + &b)
            .unwrap()
    );
}

fn process(data: &str, decryption_key: i64, mix_count: usize) -> i64 {
    let original_order: Vec<i64> = data
        .split("\n")
        .map(|n| n.parse::<i64>().unwrap() * decryption_key)
        .collect();
    let mut positions: Vec<usize> = (0..original_order.len()).collect();

    for _ in 0..mix_count {
        for i in 0..original_order.len() {
            let current_pos = positions.iter().position(|x| *x == i).unwrap();
            positions.remove(current_pos);
            let new_pos = (current_pos as i64 + original_order[i])
                .rem_euclid(positions.len() as i64) as usize;
            positions.insert(new_pos, i);
        }
    }

    let original_zero_pos = original_order.iter().position(|x| *x == 0).unwrap();
    let start = positions
        .iter()
        .position(|x| *x == original_zero_pos)
        .unwrap();

    println!(
        "{} {} {}",
        original_order[positions[(start + 1000) % positions.len()]],
        original_order[positions[(start + 2000) % positions.len()]],
        original_order[positions[(start + 3000) % positions.len()]]
    );

    original_order[positions[(start + 1000) % positions.len()]]
        + original_order[positions[(start + 2000) % positions.len()]]
        + original_order[positions[(start + 3000) % positions.len()]]
}

fn main() {
    let data = fs::read_to_string("input.txt").unwrap();
    let data = data.trim();
    println!("{}", process(data, 811589153, 10));
}

#[cfg(test)]
mod test {
    use super::*;

    const DATA: &str = "1
2
-3
3
-2
0
4";

    #[test]
    fn test_part1() {
        assert_eq!(process(DATA, 1, 1), 3);
    }

    #[test]
    fn test_part2() {
        assert_eq!(process(DATA, 811589153, 10), 1623178306);
    }
}

Day 21

This was the quickest first half AoC I’ve done in a while; I’m guessing it took just under fifteen minutes from start to finish. (Not even remotely quick enough to get on the leaderboard, by any means; the hundredth person was done with part 21 in less than five minutes!)

The second half, once I realized it’s not feasible to just try every number, was straightforward enough—just recurse up like I’ve recursed down before, and solve from the bottom up. Easier said than done, and the implementation didn’t end up being terribly elegant.

Source code

use std::collections::HashMap;
use std::fs;

#[derive(Clone, Copy)]
enum Monkey<'a> {
    Const(i64),
    Add(&'a str, &'a str),
    Sub(&'a str, &'a str),
    Mul(&'a str, &'a str),
    Div(&'a str, &'a str),
}

fn eval_monkey(monkeys: &HashMap<&str, Monkey>, addr: &str) -> i64 {
    let monkey = monkeys[addr];
    match monkey {
        Monkey::Const(a) => a,
        Monkey::Add(a, b) => eval_monkey(&monkeys, a) + eval_monkey(&monkeys, b),
        Monkey::Sub(a, b) => eval_monkey(&monkeys, a) - eval_monkey(&monkeys, b),
        Monkey::Mul(a, b) => eval_monkey(&monkeys, a) * eval_monkey(&monkeys, b),
        Monkey::Div(a, b) => eval_monkey(&monkeys, a) / eval_monkey(&monkeys, b),
    }
}

fn get_value_for(
    monkeys: &HashMap<&str, Monkey>,
    monkeys_used_by: &HashMap<&str, &str>,
    addr: &str,
) -> i64 {
    let parent = monkeys_used_by[addr];
    let (parent_first_child, parent_second_child) = match monkeys[parent] {
        Monkey::Const(_) => panic!("We're a child of const"),
        Monkey::Add(a, b) => (a, b),
        Monkey::Sub(a, b) => (a, b),
        Monkey::Mul(a, b) => (a, b),
        Monkey::Div(a, b) => (a, b),
    };
    if parent == "root" {
        if parent_first_child == addr {
            eval_monkey(&monkeys, parent_second_child)
        } else {
            eval_monkey(&monkeys, parent_first_child)
        }
    } else {
        match monkeys[parent] {
            Monkey::Const(_) => panic!("We're a child of const"),
            Monkey::Add(a, b) => {
                if a == addr {
                    get_value_for(&monkeys, &monkeys_used_by, parent) - eval_monkey(&monkeys, b)
                } else {
                    get_value_for(&monkeys, &monkeys_used_by, parent) - eval_monkey(&monkeys, a)
                }
            }
            Monkey::Sub(a, b) => {
                if a == addr {
                    get_value_for(&monkeys, &monkeys_used_by, parent) + eval_monkey(&monkeys, b)
                } else {
                    eval_monkey(&monkeys, a) - get_value_for(&monkeys, &monkeys_used_by, parent)
                }
            }
            Monkey::Mul(a, b) => {
                if a == addr {
                    get_value_for(&monkeys, &monkeys_used_by, parent) / eval_monkey(&monkeys, b)
                } else {
                    get_value_for(&monkeys, &monkeys_used_by, parent) / eval_monkey(&monkeys, a)
                }
            }
            Monkey::Div(a, b) => {
                if a == addr {
                    get_value_for(&monkeys, &monkeys_used_by, parent) * eval_monkey(&monkeys, b)
                } else {
                    eval_monkey(&monkeys, a) / get_value_for(&monkeys, &monkeys_used_by, parent)
                }
            }
        }
    }
}

fn parse(data: &str) -> (HashMap<&str, Monkey>, HashMap<&str, &str>) {
    let mut monkeys: HashMap<&str, Monkey> = HashMap::new();
    let mut monkeys_used_by: HashMap<&str, &str> = HashMap::new();
    for row in data.split("\n") {
        let (monkey, op) = row.split_once(": ").unwrap();
        let op: Vec<&str> = op.split(" ").collect();
        monkeys.insert(
            monkey,
            match op.len() {
                1 => Monkey::Const(op[0].parse().unwrap()),
                3 => {
                    assert_eq!(monkeys_used_by.insert(op[0], monkey), None);
                    assert_eq!(monkeys_used_by.insert(op[2], monkey), None);
                    match op[1] {
                        "+" => Monkey::Add(op[0], op[2]),
                        "-" => Monkey::Sub(op[0], op[2]),
                        "*" => Monkey::Mul(op[0], op[2]),
                        "/" => Monkey::Div(op[0], op[2]),
                        other => panic!("Unknown operator {}", other),
                    }
                }
                _ => panic!("Unknown operator {:?}", op),
            },
        );
    }

    (monkeys, monkeys_used_by)
}

fn process1(data: &str) -> i64 {
    let (monkeys, _monkeys_used_by) = parse(data);
    eval_monkey(&monkeys, "root")
}

fn process2(data: &str) -> i64 {
    let (monkeys, monkeys_used_by) = parse(data);

    get_value_for(&monkeys, &monkeys_used_by, "humn")
}

fn main() {
    let data = fs::read_to_string("input.txt").unwrap();
    let data = data.trim();
    println!("{}", process2(data)); // process1(data) for part 1
}

#[cfg(test)]
mod test {
    use super::*;

    const DATA: &str = "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";

    #[test]
    fn test_part1() {
        assert_eq!(process1(DATA), 152);
    }

    #[test]
    fn test_part2() {
        assert_eq!(process2(DATA), 301);
    }
}

Soundtrack

(Available at Bandcamp, or on YouTube!)

I don't have a formal commenting system set up. If you have questions or comments about anything I've written, send me an email and I'd be delighted to hear what you have to say!