bwc9876.dev
Advent of Code solutions
1use advent_core::{day_stuff, ex_for_day, Day};
2
3pub struct Day17;
4
5#[derive(Clone, Copy, Debug)]
6pub struct Registers {
7 a: u128,
8 b: u128,
9 c: u128,
10}
11
12impl Registers {
13 fn with_combo_op(&self, combo_op: &ComboOperand) -> u128 {
14 match combo_op {
15 ComboOperand::RegA => self.a,
16 ComboOperand::RegB => self.b,
17 ComboOperand::RegC => self.c,
18 _ => panic!(),
19 }
20 }
21}
22
23#[derive(Clone, Copy, Debug)]
24enum ComboOperand {
25 Literal(u128),
26 RegA,
27 RegB,
28 RegC,
29 Reserved,
30}
31
32impl ComboOperand {
33 fn from_u128(v: u128) -> Self {
34 match v {
35 4 => Self::RegA,
36 5 => Self::RegB,
37 6 => Self::RegC,
38 7 => Self::Reserved,
39 o => Self::Literal(o),
40 }
41 }
42
43 fn get_val(&self, regs: &Registers) -> u128 {
44 match self {
45 Self::Literal(v) => *v,
46 Self::Reserved => panic!(),
47 reg => regs.with_combo_op(reg),
48 }
49 }
50}
51
52#[derive(Clone, Copy, Debug)]
53enum Instruction {
54 Adv(ComboOperand),
55 Bxl(u128),
56 Bst(ComboOperand),
57 Jnz(u128),
58 Bxc(()),
59 Out(ComboOperand),
60 Bdv(ComboOperand),
61 Cdv(ComboOperand),
62}
63
64impl Instruction {
65 fn from_slice(ins: &[u128]) -> Self {
66 let op = ins[0];
67 let opr = ins[1];
68
69 match op {
70 0 => Self::Adv(ComboOperand::from_u128(opr)),
71 1 => Self::Bxl(opr),
72 2 => Self::Bst(ComboOperand::from_u128(opr)),
73 3 => Self::Jnz(opr),
74 4 => Self::Bxc(()),
75 5 => Self::Out(ComboOperand::from_u128(opr)),
76 6 => Self::Bdv(ComboOperand::from_u128(opr)),
77 7 => Self::Cdv(ComboOperand::from_u128(opr)),
78 _ => unreachable!(),
79 }
80 }
81
82 fn execute(&self, ip: u128, regs: &mut Registers) -> (u128, Option<u128>) {
83 match self {
84 Self::Adv(op) => {
85 regs.a /= 2_u128.pow(op.get_val(regs) as u32);
86 }
87 Self::Bxl(v) => {
88 regs.b ^= v;
89 }
90 Self::Bst(op) => {
91 regs.b = op.get_val(regs) % 8;
92 }
93 Self::Jnz(v) => {
94 if regs.a != 0 {
95 return (*v, None);
96 }
97 }
98 Self::Bxc(_) => {
99 regs.b ^= regs.c;
100 }
101 Self::Out(op) => {
102 return (ip + 2, Some(op.get_val(regs) % 8));
103 }
104 Self::Bdv(op) => {
105 regs.b = regs.a / 2_u128.pow(op.get_val(regs) as u32);
106 }
107 Self::Cdv(op) => {
108 regs.c = regs.a / 2_u128.pow(op.get_val(regs) as u32);
109 }
110 }
111
112 (ip + 2, None)
113 }
114}
115
116#[derive(Debug, Clone)]
117pub struct Computer {
118 regs: Registers,
119 instructions: Vec<u128>,
120}
121
122impl Computer {
123 fn parse(input: &str) -> Self {
124 let (raw_regs, raw_program) = input.trim().split_once("\n\n").unwrap();
125 let mut regs = raw_regs
126 .lines()
127 .map(|l| l.split_once(": ").unwrap().1.parse::<u128>().unwrap());
128 let regs = Registers {
129 a: regs.next().unwrap(),
130 b: regs.next().unwrap(),
131 c: regs.next().unwrap(),
132 };
133 let instructions = raw_program
134 .split_once(": ")
135 .unwrap()
136 .1
137 .split(',')
138 .map(|s| s.parse::<u128>().unwrap())
139 .collect::<Vec<_>>();
140
141 Self { regs, instructions }
142 }
143}
144
145impl Day for Day17 {
146 day_stuff!(17, "4,6,3,5,6,3,5,2,1,0", "117440", Computer);
147
148 fn part_1(mut input: Self::Input) -> Option<String> {
149 let mut ip = 0;
150 let mut out = Vec::with_capacity(20);
151 while ip < input.instructions.len() - 1 {
152 let (next_ip, output) = Instruction::from_slice(&input.instructions[ip..=ip + 1])
153 .execute(ip as u128, &mut input.regs);
154 if let Some(v) = output {
155 out.push(v.to_string());
156 }
157 ip = next_ip as usize;
158 }
159 Some(out.join(","))
160 }
161
162 fn part_2(input: Self::Input) -> Option<String> {
163 let mut possible_a = Vec::with_capacity(1000);
164 possible_a.push(0);
165 for ins in input.instructions.iter().rev().copied() {
166 possible_a = possible_a
167 .into_iter()
168 .flat_map(|a| {
169 let mut branch_possible = vec![];
170 for possible_bits in 0_u128..=7 {
171 let new_a = (a << 3) + possible_bits;
172 let mut ip = 0;
173 let mut regs = Registers {
174 a: new_a,
175 b: 0,
176 c: 0,
177 };
178 let val = loop {
179 if ip >= input.instructions.len() - 1 {
180 break None;
181 }
182 let (next_ip, output) =
183 Instruction::from_slice(&input.instructions[ip..=ip + 1])
184 .execute(ip as u128, &mut regs);
185 if let Some(v) = output {
186 break Some(v);
187 }
188 ip = next_ip as usize;
189 };
190
191 if let Some(val) = val
192 && val == ins
193 {
194 branch_possible.push(new_a);
195 }
196 }
197 branch_possible
198 })
199 .collect();
200 }
201 let ans = possible_a.into_iter().min().map(|v| v.to_string()).unwrap();
202 Some(ans)
203 }
204
205 fn parse_input(input: &str) -> Self::Input {
206 Computer::parse(input)
207 }
208}