main.rs (5747B)
1 use regex::Regex;
2 use std::collections::{BinaryHeap, HashMap};
3
4 #[derive(Debug, Clone)]
5 enum Op {
6 Mult(i64),
7 MultSelf,
8 Add(i64),
9 AddSelf,
10 }
11
12 impl Op {
13 fn from_str(s: &str) -> Option<Self> {
14 if let Some(cap) =
15 Regex::new(r"^ Operation: new = old (?P<op>[\*\+]) (?P<target>(old|[-0-9]+))$")
16 .unwrap()
17 .captures(s)
18 {
19 match (
20 cap.name("op").unwrap().as_str(),
21 cap.name("target").unwrap().as_str(),
22 ) {
23 ("*", "old") => Some(Self::MultSelf),
24 ("*", target) => Some(Self::Mult(target.parse::<i64>().unwrap())),
25 ("+", "old") => Some(Self::AddSelf),
26 ("+", target) => Some(Self::Add(target.parse::<i64>().unwrap())),
27 _ => None,
28 }
29 } else {
30 None
31 }
32 }
33
34 fn exec(&self, old: i64) -> i64 {
35 match self {
36 Self::MultSelf => old * old,
37 Self::Mult(x) => old * x,
38 Self::AddSelf => old + old,
39 Self::Add(x) => old + x,
40 }
41 }
42 }
43
44 #[derive(Debug, Clone)]
45 struct Monkey {
46 id: usize,
47 items: Vec<i64>,
48 op: Op,
49 test: i64,
50 id_true: usize,
51 id_false: usize,
52 }
53
54 impl Monkey {
55 fn from_str(s: &str) -> Option<Self> {
56 let mut ss = s.trim().split('\n');
57 if let (Some(cap_1), Some(cap_2), Some(op), Some(cap_3), Some(cap_4), Some(cap_5)) = (
58 Regex::new(r"^Monkey (?P<id>[0-9]+):$")
59 .unwrap()
60 .captures(ss.next().unwrap()),
61 Regex::new(r"^ Starting items: (?P<items>[0-9 ,]+)$")
62 .unwrap()
63 .captures(ss.next().unwrap()),
64 Op::from_str(ss.next().unwrap()),
65 Regex::new(r"^ Test: divisible by (?P<test>[0-9]+)$")
66 .unwrap()
67 .captures(ss.next().unwrap()),
68 Regex::new(r"^ If true: throw to monkey (?P<id_true>[0-9]+)$")
69 .unwrap()
70 .captures(ss.next().unwrap()),
71 Regex::new(r"^ If false: throw to monkey (?P<id_false>[0-9]+)$")
72 .unwrap()
73 .captures(ss.next().unwrap()),
74 ) {
75 let m = Monkey {
76 id: cap_1.name("id").unwrap().as_str().parse::<usize>().unwrap(),
77 items: cap_2
78 .name("items")
79 .unwrap()
80 .as_str()
81 .split(", ")
82 .map(|x| x.parse::<i64>().unwrap())
83 .collect(),
84 op: op,
85 test: cap_3.name("test").unwrap().as_str().parse::<i64>().unwrap(),
86 id_true: cap_4
87 .name("id_true")
88 .unwrap()
89 .as_str()
90 .parse::<usize>()
91 .unwrap(),
92 id_false: cap_5
93 .name("id_false")
94 .unwrap()
95 .as_str()
96 .parse::<usize>()
97 .unwrap(),
98 };
99 Some(m)
100 } else {
101 None
102 }
103 }
104 }
105
106 fn main() {
107 let input: Vec<Monkey> = std::fs::read_to_string("input.txt")
108 .unwrap()
109 .trim()
110 .split("\n\n")
111 .map(|x| Monkey::from_str(x).unwrap())
112 .collect();
113 // 119715
114 println!("Part 1: {}", part_1(&input, 20));
115 // 18085004878
116 println!("Part 2: {}", part_2(&input, 10000));
117 }
118
119 fn part_1(input: &Vec<Monkey>, rounds: usize) -> i64 {
120 let mut inspect_count = HashMap::new();
121 let mut monkeys = (*input).clone();
122 for _ in 0..rounds {
123 for i in 0..monkeys.len() {
124 let mut item_idx = 0;
125 let item_count = monkeys[i].items.len();
126 while item_idx < item_count {
127 let worry_new = monkeys[i].op.exec(monkeys[i].items[item_idx]) / 3;
128 inspect_count.insert(
129 monkeys[i].id,
130 *inspect_count.get(&monkeys[i].id).unwrap_or(&0) + 1,
131 );
132 let new_id = if worry_new % monkeys[i].test == 0 {
133 monkeys[i].id_true
134 } else {
135 monkeys[i].id_false
136 };
137 monkeys[new_id].items.push(worry_new);
138 item_idx += 1;
139 }
140 monkeys[i].items.clear();
141 }
142 }
143 let mut monkey_business = BinaryHeap::from_iter(inspect_count.values());
144 monkey_business.pop().unwrap() * monkey_business.pop().unwrap()
145 }
146
147 fn part_2(input: &Vec<Monkey>, rounds: usize) -> i64 {
148 let mut inspect_count = HashMap::new();
149 let mut monkeys = (*input).clone();
150 let mod_factor = monkeys.iter().map(|m| m.test).product::<i64>();
151 for _ in 0..rounds {
152 for i in 0..monkeys.len() {
153 let mut item_idx = 0;
154 let item_count = monkeys[i].items.len();
155 while item_idx < item_count {
156 let worry_new = monkeys[i].op.exec(monkeys[i].items[item_idx]) % mod_factor;
157 inspect_count.insert(
158 monkeys[i].id,
159 *inspect_count.get(&monkeys[i].id).unwrap_or(&0) + 1,
160 );
161 let new_id = if worry_new % monkeys[i].test == 0 {
162 monkeys[i].id_true
163 } else {
164 monkeys[i].id_false
165 };
166 monkeys[new_id].items.push(worry_new);
167 item_idx += 1;
168 }
169 monkeys[i].items.clear();
170 }
171 }
172 let mut monkey_business = BinaryHeap::from_iter(inspect_count.values());
173 monkey_business.pop().unwrap() * monkey_business.pop().unwrap()
174 }