main.rs (6640B)
1 use regex::Regex;
2 use std::collections::{HashMap, VecDeque};
3
4 #[derive(Debug, Clone, Copy)]
5 enum Op {
6 Add,
7 Sub,
8 Mul,
9 Div,
10 }
11
12 impl Op {
13 fn calc(&self, a: i64, b: i64) -> i64 {
14 match self {
15 Self::Add => a + b,
16 Self::Sub => a - b,
17 Self::Mul => a * b,
18 Self::Div => a / b,
19 }
20 }
21
22 fn calc_poly(&self, a: &Vec<f64>, b: &Vec<f64>) -> Vec<f64> {
23 let mut res = Vec::new();
24 match self {
25 Self::Add => {
26 res = a.clone();
27 for (j, y) in b.iter().enumerate() {
28 while res.len() < j + 1 {
29 res.push(0.0);
30 }
31 res[j] += y;
32 }
33 }
34 Self::Sub => {
35 res = a.clone();
36 for (j, y) in b.iter().enumerate() {
37 while res.len() < j + 1 {
38 res.push(0.0);
39 }
40 res[j] -= y;
41 }
42 }
43 Self::Mul => {
44 for (i, x) in a.iter().enumerate() {
45 for (j, y) in b.iter().enumerate() {
46 while res.len() < i + j + 1 {
47 res.push(0.0);
48 }
49 res[i + j] += x * y;
50 }
51 }
52 }
53 Self::Div => {
54 res = a.clone();
55 for i in 0..a.len() {
56 for (j, y) in b.iter().enumerate() {
57 if j == 0 {
58 res[i] /= b[0];
59 } else {
60 res[i + j] -= res[i] * y;
61 }
62 }
63 if i + b.len() == a.len() {
64 break;
65 }
66 }
67 }
68 }
69 let len = res.len();
70 for i in (0..len).rev() {
71 if res[i] == 0.0 {
72 res.remove(i);
73 } else {
74 break;
75 }
76 }
77 res
78 }
79 }
80
81 #[derive(Debug, Clone)]
82 enum Cell {
83 Num(i64),
84 Calc(Op, String, String),
85 }
86
87 #[derive(Debug, Clone)]
88 struct Monkey {
89 id: String,
90 cell: Cell,
91 }
92
93 impl Monkey {
94 fn from_str(s: &str) -> Option<Self> {
95 if let Some(cap) = Regex::new(r"^(?P<id>[a-z]{4}): (?P<num>[0-9]+)$")
96 .unwrap()
97 .captures(s)
98 {
99 Some(Monkey {
100 id: cap.name("id").unwrap().as_str().to_string(),
101 cell: Cell::Num(cap.name("num").unwrap().as_str().parse::<i64>().unwrap()),
102 })
103 } else if let Some(cap) =
104 Regex::new(r"^(?P<id>[a-z]{4}): (?P<id_1>[a-z]{4}) (?P<op>[-+*/]) (?P<id_2>[a-z]{4})$")
105 .unwrap()
106 .captures(s)
107 {
108 Some(Monkey {
109 id: cap.name("id").unwrap().as_str().to_string(),
110 cell: Cell::Calc(
111 match cap.name("op").unwrap().as_str() {
112 "+" => Op::Add,
113 "-" => Op::Sub,
114 "*" => Op::Mul,
115 "/" => Op::Div,
116 _ => unreachable!(),
117 },
118 cap.name("id_1").unwrap().as_str().to_string(),
119 cap.name("id_2").unwrap().as_str().to_string(),
120 ),
121 })
122 } else {
123 None
124 }
125 }
126 }
127
128 fn main() {
129 let input = std::fs::read_to_string("input.txt")
130 .unwrap()
131 .trim()
132 .split('\n')
133 .map(|s| Monkey::from_str(s).unwrap())
134 .collect::<Vec<Monkey>>();
135 // 364367103397416
136 println!("Part 1: {}", part_1(&input));
137 // 3782852515583
138 println!("Part 2: {:?}", part_2(&input));
139 }
140
141 fn part_1(input: &Vec<Monkey>) -> i64 {
142 let monkeys = input
143 .iter()
144 .map(|m| (m.id.clone(), m.clone()))
145 .collect::<HashMap<String, Monkey>>();
146
147 let mut results = HashMap::new();
148 let mut stack = VecDeque::new();
149 stack.push_front("root".to_string());
150 while let Some(id_curr) = stack.pop_front() {
151 match &monkeys.get(&id_curr).unwrap().cell {
152 Cell::Num(x) => {
153 results.insert(id_curr, *x);
154 }
155 Cell::Calc(op, id_1, id_2) => match (results.get(id_1), results.get(id_2)) {
156 (Some(a), Some(b)) => {
157 results.insert(id_curr.clone(), op.calc(*a, *b));
158 }
159 (res_1, res_2) => {
160 stack.push_front(id_curr.clone());
161 if res_1.is_none() {
162 stack.push_front(id_1.clone());
163 }
164 if res_2.is_none() {
165 stack.push_front(id_2.clone());
166 }
167 }
168 },
169 }
170 }
171 *results.get("root").unwrap()
172 }
173
174 fn part_2(input: &Vec<Monkey>) -> i64 {
175 let mut monkeys = input
176 .iter()
177 .map(|m| (m.id.clone(), m.clone()))
178 .collect::<HashMap<String, Monkey>>();
179 if let Cell::Calc(_, id_1, id_2) = &monkeys.get("root").unwrap().cell {
180 monkeys.insert(
181 "root".to_string(),
182 Monkey {
183 id: "root".to_string(),
184 cell: Cell::Calc(Op::Sub, id_1.clone(), id_2.clone()),
185 },
186 );
187 }
188 let mut results = HashMap::new();
189 let mut stack = VecDeque::new();
190 stack.push_front("root".to_string());
191 while let Some(id_curr) = stack.pop_front() {
192 if id_curr == "humn" {
193 results.insert(id_curr.clone(), vec![0.0, 1.0]);
194 continue;
195 }
196 match &monkeys.get(&id_curr).unwrap().cell {
197 Cell::Num(x) => {
198 results.insert(id_curr, vec![*x as f64]);
199 }
200 Cell::Calc(op, id_1, id_2) => match (results.get(id_1), results.get(id_2)) {
201 (Some(a), Some(b)) => {
202 results.insert(id_curr.clone(), op.calc_poly(a, b));
203 }
204 (res_1, res_2) => {
205 stack.push_front(id_curr.clone());
206 if res_1.is_none() {
207 stack.push_front(id_1.clone());
208 }
209 if res_2.is_none() {
210 stack.push_front(id_2.clone());
211 }
212 }
213 },
214 }
215 }
216 let res = results.get("root").unwrap();
217 println!("Polynomial: {:?}", res);
218 // assume greatest power of 1
219 (-res[0] / res[1]) as i64
220 }