main.rs (6785B)
1 use std::collections::{HashMap, VecDeque};
2
3 #[derive(Debug, Copy, Clone, Hash, Eq, PartialEq)]
4 enum Reg {
5 W,
6 X,
7 Y,
8 Z,
9 }
10
11 impl Reg {
12 fn new(s: &str) -> Self {
13 match s {
14 "w" => Self::W,
15 "x" => Self::X,
16 "y" => Self::Y,
17 "z" => Self::Z,
18 _ => unreachable!(),
19 }
20 }
21
22 fn get_val(&self, regs: &HashMap<Reg, i64>) -> i64 {
23 *regs.get(self).unwrap_or(&0)
24 }
25 }
26
27 #[derive(Debug, Copy, Clone)]
28 enum Arg {
29 Register(Reg),
30 Value(i64),
31 }
32
33 impl Arg {
34 fn new(s: &str) -> Self {
35 match s.parse::<i64>() {
36 Ok(val) => Self::Value(val),
37 Err(_) => Self::Register(Reg::new(s)),
38 }
39 }
40
41 fn get_val(&self, regs: &HashMap<Reg, i64>) -> i64 {
42 match self {
43 Self::Register(r) => *regs.get(r).unwrap_or(&0),
44 Self::Value(v) => *v,
45 }
46 }
47 }
48
49 #[derive(Debug, Copy, Clone)]
50 enum Op {
51 Inp(Reg),
52 Add(Reg, Arg),
53 Mul(Reg, Arg),
54 Div(Reg, Arg),
55 Mod(Reg, Arg),
56 Eql(Reg, Arg),
57 }
58
59 impl Op {
60 fn new(s: &str) -> Self {
61 let mut it = s.split(' ');
62 match (it.next(), it.next(), it.next()) {
63 (Some("inp"), Some(a), None) => Self::Inp(Reg::new(a)),
64 (Some("add"), Some(a), Some(b)) => Self::Add(Reg::new(a), Arg::new(b)),
65 (Some("mul"), Some(a), Some(b)) => Self::Mul(Reg::new(a), Arg::new(b)),
66 (Some("div"), Some(a), Some(b)) => Self::Div(Reg::new(a), Arg::new(b)),
67 (Some("mod"), Some(a), Some(b)) => Self::Mod(Reg::new(a), Arg::new(b)),
68 (Some("eql"), Some(a), Some(b)) => Self::Eql(Reg::new(a), Arg::new(b)),
69 _ => unreachable!(),
70 }
71 }
72
73 fn eval(&self, regs: &mut HashMap<Reg, i64>, input: &mut VecDeque<i64>) {
74 match self {
75 Self::Inp(a) => {
76 regs.insert(*a, input.pop_front().unwrap());
77 }
78 Self::Add(a, b) => {
79 regs.insert(*a, a.get_val(regs) + b.get_val(regs));
80 }
81 Self::Mul(a, b) => {
82 regs.insert(*a, a.get_val(regs) * b.get_val(regs));
83 }
84 Self::Div(a, b) => {
85 regs.insert(*a, a.get_val(regs) / b.get_val(regs));
86 }
87 Self::Mod(a, b) => {
88 regs.insert(*a, a.get_val(regs) % b.get_val(regs));
89 }
90 Self::Eql(a, b) => {
91 regs.insert(*a, (a.get_val(regs) == b.get_val(regs)) as i64);
92 }
93 }
94 }
95 }
96
97 fn main() {
98 let input = std::fs::read_to_string("input.txt")
99 .unwrap()
100 .trim()
101 .split('\n')
102 .map(|s| s.to_string())
103 .collect::<Vec<String>>();
104 let program = input.iter().map(|s| Op::new(&s)).collect::<Vec<Op>>();
105 let alt_program = (0..input.len())
106 .filter(|i| match i % (input.len() / 14) {
107 4 | 5 | 15 => true,
108 _ => false,
109 })
110 .map(|i| {
111 input[i]
112 .split(' ')
113 .skip(2)
114 .next()
115 .unwrap()
116 .parse::<i64>()
117 .unwrap()
118 })
119 .collect::<Vec<_>>()
120 .chunks_exact(3)
121 .map(|c| (c[0], c[1], c[2]))
122 .collect::<Vec<(i64, i64, i64)>>();
123 println!("Part 1: {}", part_1(&program, &alt_program));
124 println!("Part 2: {}", part_2(&program, &alt_program));
125 }
126
127 fn run(program: &Vec<Op>, input: &VecDeque<i64>) -> i64 {
128 let mut input = input.clone();
129 let mut regs = HashMap::new();
130 for &op in program.iter() {
131 op.eval(&mut regs, &mut input);
132 }
133 *regs.get(&Reg::Z).unwrap()
134 }
135
136 fn alt_run(alt_input: &Vec<(i64, i64, i64)>, input: &VecDeque<i64>) -> i64 {
137 let mut input = input.clone();
138 let mut z = 0;
139 for &(v1, v2, v3) in alt_input {
140 let w = input.pop_front().unwrap();
141 // let x = ((z % 26 + v2) != w) as i64;
142 // z = (z / v1) * (x * 25 + 1) + (w + v3) * x;
143 if z % 26 != w - v2 {
144 z = z / v1 * 26 + w + v3;
145 } else {
146 z = z / v1;
147 }
148 // we always have v1 = 1 when v2 > 9 (upper path)
149 // these steps essentially enqueues (w + v3) into a stack (*= 26)
150 // conversely we always have v1 = 26 when v2 < 0
151 // we can deque (/= 26) if the last enqueued number is equal to (w - v2)
152 // there are 7 fixed enqueues, and goals is to follow the deque branch
153 // in other 7
154 }
155 z
156 }
157
158 fn part_1(program: &Vec<Op>, alt_program: &Vec<(i64, i64, i64)>) -> i64 {
159 let mut digits = [0; 14].iter().map(|&x| x).collect::<VecDeque<_>>();
160 let mut queue = VecDeque::<(usize, i64)>::new();
161 for (i, &(v1, v2, v3)) in alt_program.iter().enumerate() {
162 match v1 {
163 1 => {
164 queue.push_back((i, v3));
165 }
166 26 => {
167 let (prev_i, prev_v3) = queue.pop_back().unwrap();
168 // find largest prev_w and w such that prev_w + prev_v3 == w - v2
169 // v2 is always negative
170 // diff = w - prev_w
171 let diff = prev_v3 + v2;
172 if diff > 0 {
173 digits[i] = 9;
174 digits[prev_i] = 9 - diff;
175 } else {
176 digits[i] = 9 + diff;
177 digits[prev_i] = 9;
178 }
179 }
180 _ => unreachable!(),
181 }
182 }
183 let model_number = digits.iter().fold(0, |acc, x| acc * 10 + x);
184 assert!(alt_run(alt_program, &mut digits.clone()) == 0);
185 assert!(run(program, &mut digits.clone()) == 0);
186 model_number
187 }
188
189 fn part_2(program: &Vec<Op>, alt_program: &Vec<(i64, i64, i64)>) -> i64 {
190 let mut digits = [0; 14].iter().map(|&x| x).collect::<VecDeque<_>>();
191 let mut queue = VecDeque::<(usize, i64)>::new();
192 for (i, &(v1, v2, v3)) in alt_program.iter().enumerate() {
193 match v1 {
194 1 => {
195 queue.push_back((i, v3));
196 }
197 26 => {
198 let (prev_i, prev_v3) = queue.pop_back().unwrap();
199 // find largest prev_w and w such that prev_w + prev_v3 == w - v2
200 // v2 is always negative
201 // diff = w - prev_w
202 let diff = prev_v3 + v2;
203 if diff > 0 {
204 digits[i] = 1 + diff;
205 digits[prev_i] = 1;
206 } else {
207 digits[i] = 1;
208 digits[prev_i] = 1 - diff;
209 }
210 }
211 _ => unreachable!(),
212 }
213 }
214 let model_number = digits.iter().fold(0, |acc, x| acc * 10 + x);
215 assert!(alt_run(alt_program, &mut digits.clone()) == 0);
216 assert!(run(program, &mut digits.clone()) == 0);
217 model_number
218 }