day-15.rs (9857B)
1 use std::collections::HashMap;
2 use std::collections::VecDeque;
3 type Op = i128;
4
5 fn main() {
6 let input = std::fs::read_to_string("input.txt")
7 .unwrap()
8 .trim()
9 .split(",")
10 .map(|op| op.parse::<Op>().unwrap())
11 .collect::<Vec<Op>>();
12 println!("Rust:");
13 println!("Part 1: {}", part_1(&input));
14 println!("Part 2: {}", part_2(&input));
15 }
16
17 fn computer_step(
18 program: &mut HashMap<usize, Op>,
19 pc: &mut usize,
20 relative_base: &mut Op,
21 input: &mut Option<Op>,
22 ) -> (bool, Vec<Op>) {
23 let mut output = vec![];
24 let get_param = |loc: usize, mode, program: &HashMap<usize, Op>, relative_base: &Op| -> Op {
25 match mode {
26 // Position mode.
27 0 => *program.get(&(program[&loc] as usize)).unwrap_or(&0),
28 // Immediate mode.
29 1 => program[&loc],
30 // Relative mode.
31 2 => *program
32 .get(&((*relative_base + program[&loc]) as usize))
33 .unwrap_or(&0),
34 _ => panic!(),
35 }
36 };
37
38 let get_res_loc =
39 |loc: usize, mode, program: &HashMap<usize, Op>, relative_base: &Op| -> usize {
40 match mode {
41 // Position mode.
42 0 => program[&loc] as usize,
43 // Immediate mode is banned.
44 // Relative mode.
45 2 => (relative_base + program[&loc]) as usize,
46 _ => panic!(),
47 }
48 };
49
50 loop {
51 let op_code = program[pc] % 100;
52 let mode_1 = (program[pc] % 1000) / 100;
53 let mode_2 = (program[pc] % 10000) / 1000;
54 let mode_3 = (program[pc] % 100000) / 10000;
55 match op_code {
56 1 => {
57 let res_loc = get_res_loc(*pc + 3, mode_3, &program, relative_base);
58 let param_1 = get_param(*pc + 1, mode_1, &program, relative_base);
59 let param_2 = get_param(*pc + 2, mode_2, &program, relative_base);
60 *program.entry(res_loc).or_default() = param_1 + param_2;
61 *pc += 4;
62 }
63 2 => {
64 let res_loc = get_res_loc(*pc + 3, mode_3, &program, relative_base);
65 let param_1 = get_param(*pc + 1, mode_1, &program, relative_base);
66 let param_2 = get_param(*pc + 2, mode_2, &program, relative_base);
67 *program.entry(res_loc as usize).or_default() = param_1 * param_2;
68 *pc += 4;
69 }
70 3 => {
71 let res_loc = get_res_loc(*pc + 1, mode_1, &program, relative_base);
72 // Only use input once.
73 if input.is_some() {
74 *program.entry(res_loc as usize).or_default() = input.unwrap();
75 *input = None;
76 } else {
77 // Need new input.
78 return (false, output);
79 };
80 *pc += 2;
81 }
82 4 => {
83 let param_1 = get_param(*pc + 1, mode_1, &program, relative_base);
84 output.push(param_1);
85 *pc += 2;
86 }
87 5 => {
88 let param_1 = get_param(*pc + 1, mode_1, &program, relative_base);
89 let param_2 = get_param(*pc + 2, mode_2, &program, relative_base);
90 if param_1 != 0 {
91 *pc = param_2 as usize;
92 } else {
93 *pc += 3;
94 }
95 }
96 6 => {
97 let param_1 = get_param(*pc + 1, mode_1, &program, relative_base);
98 let param_2 = get_param(*pc + 2, mode_2, &program, relative_base);
99 if param_1 == 0 {
100 *pc = param_2 as usize;
101 } else {
102 *pc += 3;
103 }
104 }
105 7 => {
106 let res_loc = get_res_loc(*pc + 3, mode_3, &program, relative_base);
107 let param_1 = get_param(*pc + 1, mode_1, &program, relative_base);
108 let param_2 = get_param(*pc + 2, mode_2, &program, relative_base);
109 *program.entry(res_loc as usize).or_default() =
110 if param_1 < param_2 { 1 } else { 0 };
111 *pc += 4;
112 }
113 8 => {
114 let res_loc = get_res_loc(*pc + 3, mode_3, &program, relative_base);
115 let param_1 = get_param(*pc + 1, mode_1, &program, relative_base);
116 let param_2 = get_param(*pc + 2, mode_2, &program, relative_base);
117 *program.entry(res_loc as usize).or_default() =
118 if param_1 == param_2 { 1 } else { 0 };
119 *pc += 4;
120 }
121 9 => {
122 let param_1 = get_param(*pc + 1, mode_1, &program, relative_base);
123 *relative_base += param_1;
124 *pc += 2;
125 }
126 99 => {
127 break;
128 }
129 _ => {
130 println!("Unknown op {}", op_code);
131 println!("{}", program[pc]);
132 panic!();
133 }
134 }
135 }
136
137 (true, output)
138 }
139
140 fn flip(cmd: &i32) -> i32 {
141 // Returns command in opposite direction.
142 match cmd {
143 1 => 2,
144 2 => 1,
145 3 => 4,
146 4 => 3,
147 _ => panic!(),
148 }
149 }
150
151 fn move_to_cmd(coord: (i32, i32), cmd: i32) -> (i32, i32) {
152 // Moves coord by cmd.
153 match cmd {
154 // North
155 1 => (coord.0, coord.1 + 1),
156 // South
157 2 => (coord.0, coord.1 - 1),
158 // West
159 3 => (coord.0 - 1, coord.1),
160 // East
161 4 => (coord.0 + 1, coord.1),
162 _ => panic!(),
163 }
164 }
165
166 fn chart_maze(input: &Vec<Op>) -> HashMap<(i32, i32), i32> {
167 // Chart the maze via DFS.
168 let mut program = input
169 .iter()
170 .enumerate()
171 .map(|(idx, &op)| (idx, op))
172 .collect::<HashMap<usize, Op>>();
173 // Set program state.
174 let mut pc = 0;
175 let mut relative_base = 0;
176 // DFS to chart the maze.
177 let mut curr_cmds = Vec::new();
178 let mut curr_path = vec![(0, 0)];
179 let mut map = HashMap::<(i32, i32), i32>::new();
180 map.insert((0, 0), 1);
181 // Start with initial directions.
182 let mut queue = VecDeque::new();
183 for cmd in 1..=4 {
184 queue.push_back((1, cmd, move_to_cmd((0, 0), cmd)));
185 }
186 while let Some((path_len, cmd, coord)) = queue.pop_back() {
187 // Check difference between current path and backtrack.
188 if curr_path.len() > path_len {
189 // Backtrack.
190 for cmd in curr_cmds[(path_len - 1)..].iter().rev().map(flip) {
191 computer_step(
192 &mut program,
193 &mut pc,
194 &mut relative_base,
195 &mut Some(cmd.into()),
196 );
197 }
198 // Clean up path.
199 curr_cmds.truncate(path_len - 1);
200 // Keep the origin.
201 curr_path.truncate(path_len);
202 }
203 // Move in specified direction.
204 let (_, step_output) = computer_step(
205 &mut program,
206 &mut pc,
207 &mut relative_base,
208 &mut Some(cmd.into()),
209 );
210 // Chart the result.
211 map.insert(coord, step_output[0] as i32);
212 // Determine if we proceed in given direction.
213 if step_output[0] != 0 {
214 // Free space, record and plan next moves.
215 // Otherwise, keep original path.
216 curr_cmds.push(cmd);
217 curr_path.push(coord);
218 for next_cmd in 1..=4 {
219 // Only visit uncharted location.
220 let target = move_to_cmd(coord, next_cmd);
221 if !map.contains_key(&target) {
222 queue.push_back((path_len + 1, next_cmd, target));
223 }
224 }
225 }
226 }
227 map
228 }
229
230 fn find_min_path(map: &HashMap<(i32, i32), i32>) -> usize {
231 // Return shortest path from (0, 0) to space labeled 2.
232 let mut queue = VecDeque::new();
233 let mut visited = HashMap::new();
234 queue.push_back((0, (0, 0)));
235 // BFS to find location.
236 while let Some((path_len, coord)) = queue.pop_front() {
237 visited.insert(coord, true);
238 match map.get(&coord).unwrap_or(&0) {
239 0 => {
240 continue;
241 }
242 1 => {
243 // Explore next steps.
244 for cmd in 1..=4 {
245 let next_coord = move_to_cmd(coord, cmd);
246 if !visited.get(&next_coord).unwrap_or(&false) {
247 queue.push_back((path_len + 1, next_coord));
248 }
249 }
250 }
251 2 => return path_len,
252 _ => panic!(),
253 }
254 }
255 usize::max_value()
256 }
257
258 fn calc_fill_time(map: &HashMap<(i32, i32), i32>) -> usize {
259 // Computes the fill time for the entire maze.
260 // Find oxygen source.
261 let source_coord = *map.iter().filter(|(_, &v)| v == 2).next().unwrap().0;
262 let mut queue = VecDeque::new();
263 let mut filled = HashMap::new();
264 queue.push_back((0, source_coord));
265 let mut max_time = 0;
266 // BFS to fill the maze.
267 while let Some((time, coord)) = queue.pop_front() {
268 max_time = max_time.max(time);
269 filled.insert(coord, true);
270 if *map.get(&coord).unwrap_or(&0) != 0 {
271 // Walls can't be filled.
272 // Fill the next area.
273 for cmd in 1..=4 {
274 let next_coord = move_to_cmd(coord, cmd);
275 if !filled.get(&next_coord).unwrap_or(&false) {
276 queue.push_back((time + 1, next_coord));
277 }
278 }
279 }
280 }
281 max_time
282 }
283
284 fn part_1(input: &Vec<Op>) -> usize {
285 let map = chart_maze(input);
286 find_min_path(&map)
287 }
288
289 fn part_2(input: &Vec<Op>) -> usize {
290 let map = chart_maze(input);
291 calc_fill_time(&map)
292 }