Advent of Code 2022: Days 10 and 11

I’m getting caught back up, slowly!

Day 10

Day 10 was pretty quick. Both parts, but especially part 2, were sort of hacky, but that’s okay; this script only has to run once! In an ideal world, I might have made an iterator that generates per-cycle “bytecode” (this could be as simple as inserting an extra noop before each addx) so that each instruction takes exactly one cycle. But day 11 awaits, so move on we must.

Part 1 source code

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

fn process(data: &str) -> i32 {
    let mut current_cycle = 1;
    let mut accumulator = 1;
    let mut value_at_cycle = HashMap::new();
    for line in data.split("\n") {
        let instruction: Vec<&str> = line.split(" ").collect();
        match instruction[0] {
            "noop" => {
                value_at_cycle.insert(current_cycle, accumulator);
                current_cycle += 1;
            }
            "addx" => {
                value_at_cycle.insert(current_cycle, accumulator);
                current_cycle += 1;
                value_at_cycle.insert(current_cycle, accumulator);
                current_cycle += 1;
                accumulator += instruction[1].parse::<i32>().unwrap();
            }
            _ => panic!("Unknown instruction {}", instruction[0]),
        }
    }
    let mut total_signal_strength = 0;
    for i in vec![20, 60, 100, 140, 180, 220] {
        total_signal_strength += i * value_at_cycle[&i];
    }
    total_signal_strength
}

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

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

    static DATA: &str = "addx 15
addx -11
addx 6
addx -3
addx 5
addx -1
addx -8
addx 13
addx 4
noop
addx -1
addx 5
addx -1
addx 5
addx -1
addx 5
addx -1
addx 5
addx -1
addx -35
addx 1
addx 24
addx -19
addx 1
addx 16
addx -11
noop
noop
addx 21
addx -15
noop
noop
addx -3
addx 9
addx 1
addx -3
addx 8
addx 1
addx 5
noop
noop
noop
noop
noop
addx -36
noop
addx 1
addx 7
noop
noop
noop
addx 2
addx 6
noop
noop
noop
noop
noop
addx 1
noop
noop
addx 7
addx 1
noop
addx -13
addx 13
addx 7
noop
addx 1
addx -33
noop
noop
noop
addx 2
noop
noop
noop
addx 8
noop
addx -1
addx 2
addx 1
noop
addx 17
addx -9
addx 1
addx 1
addx -3
addx 11
noop
noop
addx 1
noop
addx 1
noop
noop
addx -13
addx -19
addx 1
addx 3
addx 26
addx -30
addx 12
addx -1
addx 3
addx 1
noop
noop
noop
addx -9
addx 18
addx 1
addx 2
noop
noop
addx 9
noop
noop
noop
addx -1
addx 2
addx -37
addx 1
addx 3
noop
addx 15
addx -21
addx 22
addx -6
addx 1
noop
addx 2
addx 1
noop
addx -10
noop
noop
addx 20
addx 1
addx 2
addx 2
addx -6
addx -11
noop
noop
noop";

    #[test]
    fn test() {
        assert!(process(DATA) == 13140);
    }
}

Part 2 source code

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

fn process(data: &str) -> i32 {
    let mut current_cycle = 1;
    let mut accumulator = 1;
    let mut value_at_cycle = HashMap::new();
    for line in data.split("\n") {
        let instruction: Vec<&str> = line.split(" ").collect();
        match instruction[0] {
            "noop" => {
                value_at_cycle.insert(current_cycle, accumulator);
                current_cycle += 1;
            }
            "addx" => {
                value_at_cycle.insert(current_cycle, accumulator);
                current_cycle += 1;
                value_at_cycle.insert(current_cycle, accumulator);
                current_cycle += 1;
                accumulator += instruction[1].parse::<i32>().unwrap();
            }
            _ => panic!("Unknown instruction {}", instruction[0]),
        }
    }
    let mut total_signal_strength = 0;
    for i in vec![20, 60, 100, 140, 180, 220] {
        total_signal_strength += i * value_at_cycle[&i];
    }
    total_signal_strength
}

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

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

    static DATA: &str = "addx 15
addx -11
addx 6
addx -3
addx 5
addx -1
addx -8
addx 13
addx 4
noop
addx -1
addx 5
addx -1
addx 5
addx -1
addx 5
addx -1
addx 5
addx -1
addx -35
addx 1
addx 24
addx -19
addx 1
addx 16
addx -11
noop
noop
addx 21
addx -15
noop
noop
addx -3
addx 9
addx 1
addx -3
addx 8
addx 1
addx 5
noop
noop
noop
noop
noop
addx -36
noop
addx 1
addx 7
noop
noop
noop
addx 2
addx 6
noop
noop
noop
noop
noop
addx 1
noop
noop
addx 7
addx 1
noop
addx -13
addx 13
addx 7
noop
addx 1
addx -33
noop
noop
noop
addx 2
noop
noop
noop
addx 8
noop
addx -1
addx 2
addx 1
noop
addx 17
addx -9
addx 1
addx 1
addx -3
addx 11
noop
noop
addx 1
noop
addx 1
noop
noop
addx -13
addx -19
addx 1
addx 3
addx 26
addx -30
addx 12
addx -1
addx 3
addx 1
noop
noop
noop
addx -9
addx 18
addx 1
addx 2
noop
noop
addx 9
noop
noop
noop
addx -1
addx 2
addx -37
addx 1
addx 3
noop
addx 15
addx -21
addx 22
addx -6
addx 1
noop
addx 2
addx 1
noop
addx -10
noop
noop
addx 20
addx 1
addx 2
addx 2
addx -6
addx -11
noop
noop
noop";

    #[test]
    fn test() {
        assert!(process(DATA) == 13140);
    }
}

Day 11

Today’s round 2 was a bit of a brainteaser. For round 1, I’d been doing what I imagine was intended: Make the number a sufficiently large type (I’m using usize, the pointer-sized uint, which is 64-bit on my platform), and rely on the division by three to keep things manageable. For a limited number of rounds and with repeated division by three, these numbers stay manageable; however, for this part of the puzzle, that’s not quite the case any more!

Since all of our tests are testing for divisibility, it’s modular arithmetic to the rescue! But suppose I have three divisibility conditions: divisible by 2, by 3, and by 5. If I use 2, or 3, or 5 as the modulus, that successfully shrinks my total, but at the expense of being completely wrong! So we can instead take the least common multiple of these; or, more simply, just multiply them all together! For my input, this results in a number less than a hundred thousand; very reasonable. This would fit fine in an u32, and certainly in a u64 with no trouble. (If this weren’t the case, repeated passes through the hands of the monkey that multiples the worry by itself would rapidly run me out of space; each squaring doubles the number of bits that my answer needs to use, so I have a maximum of 64 passes through that monkey’s hands before I’m out of space!)

I’ve been busy enough with the puzzles that I haven’t been taking much time to engross myself in new emacs features; instead, I’m focusing on refining my knowledge of the features I know, and retraining my muscle memory from Vim. That said, next up on the list is Version Control and/or Magit (or another of Emacs’ many git-related tools). I may also have to learn a bit about installing and managing packages, editing my emacs config file, and writing elisp. On to tomorrow!

Source code

use std::collections::VecDeque;
use std::fs;

#[derive(Eq, PartialEq, Debug)]
struct Monkey {
    starting_items: VecDeque<usize>,
    operation: Vec<String>,
    test_divisible_by_cond: usize,
    target_if_test: usize,
    target_if_not_test: usize,
    inspected_item_count: usize,
}

fn update_worry_level(operation: &Vec<String>, level: usize) -> usize {
    if operation[4] == "old" {
        // new = old * old
        level * level
    } else {
        match operation[3].as_str() {
            "*" => level * operation[4].parse::<usize>().unwrap(),
            "+" => level + operation[4].parse::<usize>().unwrap(),
            _ => panic!("Unknown operator {}", operation[3]),
        }
    }
}

fn parse(data: &str) -> Vec<Monkey> {
    let mut monkeys = Vec::new();
    for monkey_data in data.split("\n\n") {
        let lines: Vec<&str> = monkey_data.split("\n").collect();
        monkeys.push(Monkey {
            starting_items: lines[1][18..]
                .split(", ")
                .map(|i| i.parse().unwrap())
                .collect(),
            operation: lines[2][13..].split(" ").map(|s| s.to_string()).collect(),
            test_divisible_by_cond: lines[3][21..].parse().unwrap(),
            target_if_test: lines[4][29..].parse().unwrap(),
            target_if_not_test: lines[5][30..].parse().unwrap(),
            inspected_item_count: 0,
        });
    }
    monkeys
}

fn process(monkeys: &mut Vec<Monkey>, rounds: usize) -> usize {
    let test_product: usize = monkeys.iter().map(|m| m.test_divisible_by_cond).product();
    for _round in 0..rounds {
        for i in 0..monkeys.len() {
            while monkeys[i].starting_items.len() > 0 {
                monkeys[i].inspected_item_count += 1;
                let mut item = monkeys[i].starting_items.pop_front().unwrap();
                item = update_worry_level(&monkeys[i].operation, item);
                // item /= 3; // part 1 only
                item %= test_product; // part 2 only
                let target_monkey = if item % monkeys[i].test_divisible_by_cond == 0 {
                    monkeys[i].target_if_test
                } else {
                    monkeys[i].target_if_not_test
                };
                monkeys[target_monkey].starting_items.push_back(item);
            }
        }
    }
    let mut access_counts: Vec<usize> = monkeys.iter().map(|m| m.inspected_item_count).collect();
    access_counts.sort_unstable_by(|a, b| b.cmp(a));
    access_counts[0] * access_counts[1]
}

fn main() {
    let data = fs::read_to_string("input.txt").unwrap();
    let data = data.trim();
    let mut monkeys = parse(data);
    println!("{}", process(&mut monkeys, 10000)); // 20 for part 1
}

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

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

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";

    #[test]
    fn test_parse_one_monkey() {
        let data = "Monkey 0:
  Starting items: 75, 63
  Operation: new = old * 3
  Test: divisible by 11
    If true: throw to monkey 7
    If false: throw to monkey 2";
        let monkeys = parse(data);
        println!("{:?}", monkeys);
        let goal_monkeys = vec![Monkey {
            starting_items: VecDeque::from([75, 63]),
            operation: vec!["new", "=", "old", "*", "3"]
                .iter()
                .map(|s| s.to_string())
                .collect(),
            test_divisible_by_cond: 11,
            target_if_test: 7,
            target_if_not_test: 2,
            inspected_item_count: 0,
        }];
        println!("Goal:     {:?}\nActual: {:?}", goal_monkeys, monkeys);
        assert!(goal_monkeys == monkeys);
    }
    #[test]
    fn test() {
        let desired_results = vec![
            (1, 4 * 6),
            (20, 99 * 103),
            (1000, 5204 * 5192),
            (2000, 10419 * 10391),
            (3000, 15638 * 15593),
            (4000, 20858 * 20797),
            (5000, 26075 * 26000),
            (6000, 31294 * 31204),
            (7000, 36508 * 36400),
            (8000, 41728 * 41606),
            (9000, 46945 * 46807),
            (10000, 52166 * 52013),
        ];
        for (rounds, desired_result) in desired_results {
            let mut monkeys = parse(DATA);
            let result = process(&mut monkeys, rounds);
            println!("{} == {}", result, desired_result);
            assert!(result == desired_result);
        }
    }
}

Soundtrack

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!