commit 4f5e25bf1cb56099850e056dd397f7fce89b4ba4
parent 08be272b68f31424b8f5502051a966acb786d7b4
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date: Sun, 11 Dec 2022 11:20:55 -0500
Add 2022 day 11
Diffstat:
3 files changed, 239 insertions(+), 0 deletions(-)
diff --git a/2022/day11/Cargo.toml b/2022/day11/Cargo.toml
@@ -0,0 +1,9 @@
+[package]
+name = "day11"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
+regex = "1"+
\ No newline at end of file
diff --git a/2022/day11/input.txt b/2022/day11/input.txt
@@ -0,0 +1,55 @@
+Monkey 0:
+ Starting items: 89, 73, 66, 57, 64, 80
+ Operation: new = old * 3
+ Test: divisible by 13
+ If true: throw to monkey 6
+ If false: throw to monkey 2
+
+Monkey 1:
+ Starting items: 83, 78, 81, 55, 81, 59, 69
+ Operation: new = old + 1
+ Test: divisible by 3
+ If true: throw to monkey 7
+ If false: throw to monkey 4
+
+Monkey 2:
+ Starting items: 76, 91, 58, 85
+ Operation: new = old * 13
+ Test: divisible by 7
+ If true: throw to monkey 1
+ If false: throw to monkey 4
+
+Monkey 3:
+ Starting items: 71, 72, 74, 76, 68
+ Operation: new = old * old
+ Test: divisible by 2
+ If true: throw to monkey 6
+ If false: throw to monkey 0
+
+Monkey 4:
+ Starting items: 98, 85, 84
+ Operation: new = old + 7
+ Test: divisible by 19
+ If true: throw to monkey 5
+ If false: throw to monkey 7
+
+Monkey 5:
+ Starting items: 78
+ Operation: new = old + 8
+ Test: divisible by 5
+ If true: throw to monkey 3
+ If false: throw to monkey 0
+
+Monkey 6:
+ Starting items: 86, 70, 60, 88, 88, 78, 74, 83
+ Operation: new = old + 4
+ Test: divisible by 11
+ If true: throw to monkey 1
+ If false: throw to monkey 2
+
+Monkey 7:
+ Starting items: 81, 58
+ Operation: new = old + 5
+ Test: divisible by 17
+ If true: throw to monkey 3
+ If false: throw to monkey 5
diff --git a/2022/day11/src/main.rs b/2022/day11/src/main.rs
@@ -0,0 +1,174 @@
+use regex::Regex;
+use std::collections::{BinaryHeap, HashMap};
+
+#[derive(Debug, Clone)]
+enum Op {
+ Mult(i64),
+ MultSelf,
+ Add(i64),
+ AddSelf,
+}
+
+impl Op {
+ fn from_str(s: &str) -> Option<Self> {
+ if let Some(cap) =
+ Regex::new(r"^ Operation: new = old (?P<op>[\*\+]) (?P<target>(old|[-0-9]+))$")
+ .unwrap()
+ .captures(s)
+ {
+ match (
+ cap.name("op").unwrap().as_str(),
+ cap.name("target").unwrap().as_str(),
+ ) {
+ ("*", "old") => Some(Self::MultSelf),
+ ("*", target) => Some(Self::Mult(target.parse::<i64>().unwrap())),
+ ("+", "old") => Some(Self::AddSelf),
+ ("+", target) => Some(Self::Add(target.parse::<i64>().unwrap())),
+ _ => None,
+ }
+ } else {
+ None
+ }
+ }
+
+ fn exec(&self, old: i64) -> i64 {
+ match self {
+ Self::MultSelf => old * old,
+ Self::Mult(x) => old * x,
+ Self::AddSelf => old + old,
+ Self::Add(x) => old + x,
+ }
+ }
+}
+
+#[derive(Debug, Clone)]
+struct Monkey {
+ id: usize,
+ items: Vec<i64>,
+ op: Op,
+ test: i64,
+ id_true: usize,
+ id_false: usize,
+}
+
+impl Monkey {
+ fn from_str(s: &str) -> Option<Self> {
+ let mut ss = s.trim().split('\n');
+ if let (Some(cap_1), Some(cap_2), Some(op), Some(cap_3), Some(cap_4), Some(cap_5)) = (
+ Regex::new(r"^Monkey (?P<id>[0-9]+):$")
+ .unwrap()
+ .captures(ss.next().unwrap()),
+ Regex::new(r"^ Starting items: (?P<items>[0-9 ,]+)$")
+ .unwrap()
+ .captures(ss.next().unwrap()),
+ Op::from_str(ss.next().unwrap()),
+ Regex::new(r"^ Test: divisible by (?P<test>[0-9]+)$")
+ .unwrap()
+ .captures(ss.next().unwrap()),
+ Regex::new(r"^ If true: throw to monkey (?P<id_true>[0-9]+)$")
+ .unwrap()
+ .captures(ss.next().unwrap()),
+ Regex::new(r"^ If false: throw to monkey (?P<id_false>[0-9]+)$")
+ .unwrap()
+ .captures(ss.next().unwrap()),
+ ) {
+ let m = Monkey {
+ id: cap_1.name("id").unwrap().as_str().parse::<usize>().unwrap(),
+ items: cap_2
+ .name("items")
+ .unwrap()
+ .as_str()
+ .split(", ")
+ .map(|x| x.parse::<i64>().unwrap())
+ .collect(),
+ op: op,
+ test: cap_3.name("test").unwrap().as_str().parse::<i64>().unwrap(),
+ id_true: cap_4
+ .name("id_true")
+ .unwrap()
+ .as_str()
+ .parse::<usize>()
+ .unwrap(),
+ id_false: cap_5
+ .name("id_false")
+ .unwrap()
+ .as_str()
+ .parse::<usize>()
+ .unwrap(),
+ };
+ Some(m)
+ } else {
+ None
+ }
+ }
+}
+
+fn main() {
+ let input: Vec<Monkey> = std::fs::read_to_string("input.txt")
+ .unwrap()
+ .trim()
+ .split("\n\n")
+ .map(|x| Monkey::from_str(x).unwrap())
+ .collect();
+ // 119715
+ println!("Part 1: {}", part_1(&input, 20));
+ // 18085004878
+ println!("Part 2: {}", part_2(&input, 10000));
+}
+
+fn part_1(input: &Vec<Monkey>, rounds: usize) -> i64 {
+ let mut inspect_count = HashMap::new();
+ let mut monkeys = (*input).clone();
+ for _ in 0..rounds {
+ for i in 0..monkeys.len() {
+ let mut item_idx = 0;
+ let item_count = monkeys[i].items.len();
+ while item_idx < item_count {
+ let worry_new = monkeys[i].op.exec(monkeys[i].items[item_idx]) / 3;
+ inspect_count.insert(
+ monkeys[i].id,
+ *inspect_count.get(&monkeys[i].id).unwrap_or(&0) + 1,
+ );
+ let new_id = if worry_new % monkeys[i].test == 0 {
+ monkeys[i].id_true
+ } else {
+ monkeys[i].id_false
+ };
+ monkeys[new_id].items.push(worry_new);
+ item_idx += 1;
+ }
+ monkeys[i].items.clear();
+ }
+ }
+ let mut monkey_business = BinaryHeap::from_iter(inspect_count.values());
+ monkey_business.pop().unwrap() * monkey_business.pop().unwrap()
+}
+
+fn part_2(input: &Vec<Monkey>, rounds: usize) -> i64 {
+ let mut inspect_count = HashMap::new();
+ let mut monkeys = (*input).clone();
+ let mod_factor = monkeys.iter().map(|m| m.test).product::<i64>();
+ for _ in 0..rounds {
+ for i in 0..monkeys.len() {
+ let mut item_idx = 0;
+ let item_count = monkeys[i].items.len();
+ while item_idx < item_count {
+ let worry_new = monkeys[i].op.exec(monkeys[i].items[item_idx]) % mod_factor;
+ inspect_count.insert(
+ monkeys[i].id,
+ *inspect_count.get(&monkeys[i].id).unwrap_or(&0) + 1,
+ );
+ let new_id = if worry_new % monkeys[i].test == 0 {
+ monkeys[i].id_true
+ } else {
+ monkeys[i].id_false
+ };
+ monkeys[new_id].items.push(worry_new);
+ item_idx += 1;
+ }
+ monkeys[i].items.clear();
+ }
+ }
+ let mut monkey_business = BinaryHeap::from_iter(inspect_count.values());
+ monkey_business.pop().unwrap() * monkey_business.pop().unwrap()
+}