bwc9876.dev
Advent of Code solutions
1use std::collections::{HashMap, HashSet, VecDeque};
2
3use advent_core::{day_stuff, ex_for_day, Day};
4
5pub struct Day24;
6
7pub type Wires = HashMap<String, bool>;
8pub type Gates = HashMap<(String, String, String), Gate>;
9
10fn find_gate<'a>(gates: &'a Gates, lhs: &str, rhs: &str, op: Op) -> Option<&'a Gate> {
11 gates.get(&(lhs.to_string(), rhs.to_string(), format!("{op:?}")))
12}
13
14#[derive(Debug, Clone, Copy, Eq, PartialEq)]
15pub enum Op {
16 And,
17 Or,
18 Xor,
19}
20
21impl Op {
22 fn eval(&self, lhs: bool, rhs: bool) -> bool {
23 match self {
24 Self::And => lhs & rhs,
25 Self::Or => lhs | rhs,
26 Self::Xor => lhs ^ rhs,
27 }
28 }
29}
30
31#[derive(Debug, Clone)]
32pub struct Gate {
33 lhs: String,
34 op: Op,
35 rhs: String,
36 target: String,
37}
38
39impl Gate {
40 pub fn parse(raw: &str) -> Self {
41 let mut s = raw.split(" ");
42 let lhs = s.next().unwrap().to_string();
43 let op = s.next().unwrap();
44 let rhs = s.next().unwrap().to_string();
45 let target = s.nth(1).unwrap().to_string();
46 let op = match op {
47 "AND" => Op::And,
48 "OR" => Op::Or,
49 "XOR" => Op::Xor,
50 _ => panic!(),
51 };
52 Self {
53 lhs,
54 rhs,
55 target,
56 op,
57 }
58 }
59
60 pub fn run(&self, wires: &mut Wires) -> bool {
61 if let (Some(&lhs), Some(&rhs)) = (wires.get(&self.lhs), wires.get(&self.rhs)) {
62 wires.insert(self.target.clone(), self.op.eval(lhs, rhs));
63 true
64 } else {
65 false
66 }
67 }
68}
69
70enum AdderTestResult {
71 Okay(String),
72 SwapNeeded(String, String),
73 CompletelyWrong,
74 End,
75}
76
77impl AdderTestResult {
78 fn unwrap_okay(self) -> String {
79 match self {
80 Self::Okay(s) => s,
81 _ => panic!(),
82 }
83 }
84}
85
86// The first adder is a half adder and needs to follow this format:
87//
88// x00, y00 -> AND -> [carry output wire]
89// x00, y00 -> XOR -> z00
90//
91fn test_first_adder(gates: &Gates) -> AdderTestResult {
92 let x0 = "x00".to_string();
93 let y0 = "y00".to_string();
94 if let Some(Gate { target, .. }) = find_gate(gates, &x0, &y0, Op::And) {
95 if let Some(Gate {
96 target: z_target, ..
97 }) = find_gate(gates, &x0, &y0, Op::Xor)
98 {
99 if z_target == "z00" {
100 if target == "z01" {
101 AdderTestResult::End
102 } else {
103 AdderTestResult::Okay(target.to_string())
104 }
105 } else {
106 AdderTestResult::SwapNeeded(target.to_string(), z_target.to_string())
107 }
108 } else {
109 AdderTestResult::CompletelyWrong
110 }
111 } else {
112 AdderTestResult::CompletelyWrong
113 }
114}
115
116// Full adders must follow this pattern:
117//
118// 1. x[], y[] -> AND -> [xy_and_target]
119// 2. x[], y[] -> XOR -> [xy_xor_target]
120// 3. [carry_input], [xy_xor_target] -> XOR -> z[]
121// 4. [carry_input], [xy_xor_target] -> AND -> [carry_xy_target]
122// 5. [carry_xy_target], [xy_and_target] -> OR -> [carry_output]
123//
124// Of the gates, the ones that can swap outputs without creating a loop are as follows:
125// A. #1 & #2
126// B. #3 & #5
127// C. #3 & #4
128// D. #1 & #3
129//
130// These ones would result in insane or same output:
131// #1 & #4, this actually results in the same output no matter what
132// #2 & #3, this will result in #3's own output be its input which is invalid to this problem
133// #2 & #4, ^
134// #2 & #5, ^
135// #4 & #5, ^
136//
137fn test_adder(num: usize, carry_input: &str, gates: &Gates) -> AdderTestResult {
138 let x = format!("x{num:02}");
139 let y = format!("y{num:02}");
140 let z = format!("z{num:02}");
141 if let (
142 Some(Gate {
143 target: xy_and_target,
144 ..
145 }),
146 Some(Gate {
147 target: xy_xor_target,
148 ..
149 }),
150 ) = (
151 find_gate(gates, &x, &y, Op::And),
152 find_gate(gates, &x, &y, Op::Xor),
153 ) {
154 if let Some(Gate {
155 target: z_target, ..
156 }) = find_gate(gates, carry_input, xy_xor_target.as_str(), Op::Xor)
157 {
158 if *z_target != z {
159 // We know gate #3 is pointing to the wrong target, as it should be pointing to z[]
160 // We can now confidently swap z[] and this target
161 // This covers invalid state B, C, and D
162 return AdderTestResult::SwapNeeded(z_target.to_string(), z);
163 }
164 } else {
165 // We know that gate #2 has an invalid output, and since the only case that involves #2
166 // is case A, we know that we're swapped with gate #1, we simply need to return the two
167 // targets we already have
168 return AdderTestResult::SwapNeeded(
169 xy_and_target.to_string(),
170 xy_xor_target.to_string(),
171 );
172 };
173
174 // From here we've checked all test cases, we can confidently attempt to find the carry
175 // output now
176 let carry_xy_target = &find_gate(gates, xy_xor_target, carry_input, Op::And)
177 .expect("Failed to find carry_xy_target")
178 .target;
179 let carry_out = &find_gate(gates, carry_xy_target, xy_and_target, Op::Or)
180 .expect("Failed to find carry_out")
181 .target;
182 if *carry_out == format!("z{:02}", num + 1) {
183 AdderTestResult::End
184 } else {
185 AdderTestResult::Okay(carry_out.to_string())
186 }
187 } else {
188 AdderTestResult::CompletelyWrong
189 }
190}
191
192fn swap_outputs(gates: &mut Gates, out1: &String, out2: &String) {
193 gates.values_mut().for_each(|g| {
194 if g.target == *out1 {
195 g.target = out2.to_string();
196 } else if g.target == *out2 {
197 g.target = out1.to_string();
198 }
199 });
200}
201
202// 0,1,
203// z16,tdv,hnd,z09,z23,bks,nrn,tjp
204
205impl Day for Day24 {
206 day_stuff!(24, "4", "bks,hnd,nrn,tdv,tjp,z09,z16,z23", (Wires, Gates));
207
208 fn part_1((mut wires, gates): Self::Input) -> Option<String> {
209 let mut all_zs = gates
210 .values()
211 .filter(|g| g.target.starts_with('z'))
212 .map(|g| &g.target)
213 .collect::<Vec<_>>();
214 all_zs.sort();
215 all_zs.dedup();
216
217 let mut current_zs = HashSet::<&String>::with_capacity(all_zs.len());
218
219 let mut queue = gates.values().collect::<VecDeque<_>>();
220
221 while let Some(gate) = queue.pop_front()
222 && current_zs.len() < all_zs.len()
223 {
224 if gate.run(&mut wires) {
225 if gate.target.starts_with('z') {
226 current_zs.insert(&gate.target);
227 }
228 } else {
229 queue.push_back(gate);
230 }
231 }
232
233 let ans = all_zs.into_iter().enumerate().fold(0_usize, |acc, (i, z)| {
234 let wire = wires.get(z).unwrap();
235 if *wire {
236 acc | (1 << i)
237 } else {
238 acc
239 }
240 });
241
242 Some(ans.to_string())
243 }
244
245 fn part_2((_, mut gates): Self::Input) -> Option<String> {
246 let mut swapped = Vec::with_capacity(8);
247 let mut current_carry = String::new();
248
249 for i in 0.. {
250 let res = if i == 0 {
251 test_first_adder(&gates)
252 } else {
253 test_adder(i, ¤t_carry, &gates)
254 };
255
256 match res {
257 AdderTestResult::Okay(new_carry) => {
258 current_carry = new_carry;
259 }
260 AdderTestResult::End => {
261 break;
262 }
263 AdderTestResult::CompletelyWrong => {
264 panic!("Wrong adder");
265 }
266 AdderTestResult::SwapNeeded(l, r) => {
267 swap_outputs(&mut gates, &l, &r);
268 current_carry = test_adder(i, ¤t_carry, &gates).unwrap_okay();
269 swapped.push(l);
270 swapped.push(r);
271 }
272 };
273 }
274
275 swapped.sort();
276
277 Some(swapped.join(","))
278 }
279
280 fn parse_input(input: &str) -> Self::Input {
281 let (inits, gates) = input.trim().split_once("\n\n").unwrap();
282
283 let wires = inits
284 .lines()
285 .map(|l| {
286 let (name, val) = l.split_once(": ").unwrap();
287 (name.to_string(), val == "1")
288 })
289 .collect::<HashMap<_, _>>();
290
291 let gates = gates
292 .lines()
293 .flat_map(|l| {
294 let gate = Gate::parse(l);
295 let op_str = format!("{:?}", gate.op);
296 [
297 (
298 (gate.lhs.clone(), gate.rhs.clone(), op_str.clone()),
299 gate.clone(),
300 ),
301 ((gate.rhs.clone(), gate.lhs.clone(), op_str), gate),
302 ]
303 })
304 .collect::<HashMap<_, _>>();
305
306 (wires, gates)
307 }
308}