main.rs (17002B)
1 use std::collections::{HashMap, HashSet, VecDeque};
2
3 #[derive(Debug, Copy, Clone, Eq, PartialEq)]
4 enum Amphipod {
5 A,
6 B,
7 C,
8 D,
9 }
10 impl Amphipod {
11 fn new(c: char) -> Self {
12 match c {
13 'A' => Self::A,
14 'B' => Self::B,
15 'C' => Self::C,
16 'D' => Self::D,
17 _ => unreachable!(),
18 }
19 }
20 fn cost(&self) -> usize {
21 match self {
22 Self::A => 1,
23 Self::B => 10,
24 Self::C => 100,
25 Self::D => 1000,
26 }
27 }
28 }
29 fn main() {
30 let input = std::fs::read_to_string("input.txt")
31 .unwrap()
32 .trim()
33 .split('\n')
34 .skip(2)
35 .take(2)
36 .map(|s| {
37 s.chars()
38 .filter(|c| c.is_alphabetic())
39 .map(Amphipod::new)
40 .collect::<Vec<_>>()
41 })
42 .collect::<Vec<_>>();
43 // 19059
44 println!("Part 1: {}", part_1(&input));
45 // 48541
46 println!("Part 2: {}", part_2(&input));
47 }
48
49 fn map_routes(
50 map_size: usize,
51 mut step_count: HashMap<(usize, usize), usize>,
52 ) -> HashMap<(usize, usize), usize> {
53 loop {
54 let mut step_count_new = HashMap::new();
55 for start in 0..map_size {
56 for end in 0..map_size {
57 for mid in 0..map_size {
58 if start != end && start != mid && mid != end {
59 match (
60 step_count.get(&(start, mid)),
61 step_count.get(&(mid, end)),
62 step_count.get(&(start, end)),
63 ) {
64 (Some(a), Some(b), None) => {
65 step_count_new.insert((start, end), a + b);
66 }
67 (Some(a), Some(b), Some(c)) => {
68 if a + b < *c {
69 step_count_new.insert((start, end), a + b);
70 }
71 }
72 _ => (),
73 }
74 }
75 }
76 }
77 }
78 if step_count_new.is_empty() {
79 break;
80 }
81 for ((a, b), cost) in step_count_new.into_iter() {
82 step_count.insert((a, b), cost);
83 }
84 }
85 step_count
86 }
87
88 fn part_1(input: &Vec<Vec<Amphipod>>) -> usize {
89 // #############
90 // #01.4.7.a.de#
91 // ###2#5#8#b###
92 // #3#6#9#c#
93 // #########
94 let map_size = 15;
95 let corridor_pos = [0, 1, 4, 7, 10, 13, 14]
96 .iter()
97 .map(|&x| x as usize)
98 .collect::<HashSet<usize>>();
99 let room_pos = [2, 3, 5, 6, 8, 9, 11, 12]
100 .iter()
101 .map(|&x| x as usize)
102 .collect::<HashSet<usize>>();
103 let entrance_map = {
104 let mut tmp = HashMap::<usize, usize>::new();
105 for &(a, b) in [(2, 3), (5, 6), (8, 9), (11, 12)].iter() {
106 tmp.insert(a, a);
107 tmp.insert(b, a);
108 }
109 tmp
110 };
111 let is_reachable = |pos: &[Option<Amphipod>], curr_pos: usize, dest_pos: usize| -> bool {
112 // assumes dest_pos is reachable if inside a room
113 let corridor_clear = corridor_pos
114 .iter()
115 .filter(|&p| (*p > curr_pos && *p < dest_pos) || (*p > dest_pos && *p < curr_pos))
116 .all(|&p| pos[p].is_none());
117 let entrance_clear = if let Some(&entrance_pos) = entrance_map.get(&curr_pos) {
118 (entrance_pos..curr_pos).all(|p| pos[p].is_none())
119 } else {
120 true
121 };
122 corridor_clear && entrance_clear
123 };
124 let step_count = {
125 let mut step_count = HashMap::new();
126 // build up dist 1 step counts
127 // intersections
128 for &(a, b, c) in [(1, 2, 4), (4, 5, 7), (7, 8, 10), (10, 11, 13)].iter() {
129 step_count.insert((a, b), 2);
130 step_count.insert((b, a), 2);
131 step_count.insert((a, c), 2);
132 step_count.insert((c, a), 2);
133 step_count.insert((c, b), 2);
134 step_count.insert((b, c), 2);
135 }
136 // room
137 for &(a, b) in [(2, 3), (5, 6), (8, 9), (11, 12)].iter() {
138 step_count.insert((a, b), 1);
139 step_count.insert((b, a), 1);
140 }
141 // corridor ends
142 for &(a, b) in [(0, 1), (13, 14)].iter() {
143 step_count.insert((a, b), 1);
144 step_count.insert((b, a), 1);
145 }
146 map_routes(map_size, step_count)
147 };
148 let init_pos = {
149 let mut tmp = vec![None; map_size];
150 tmp[2] = Some(input[0][0]);
151 tmp[3] = Some(input[1][0]);
152 tmp[5] = Some(input[0][1]);
153 tmp[6] = Some(input[1][1]);
154 tmp[8] = Some(input[0][2]);
155 tmp[9] = Some(input[1][2]);
156 tmp[11] = Some(input[0][3]);
157 tmp[12] = Some(input[1][3]);
158 tmp
159 };
160 let final_pos = {
161 let mut tmp = vec![None; map_size];
162 tmp[2] = Some(Amphipod::A);
163 tmp[3] = Some(Amphipod::A);
164 tmp[5] = Some(Amphipod::B);
165 tmp[6] = Some(Amphipod::B);
166 tmp[8] = Some(Amphipod::C);
167 tmp[9] = Some(Amphipod::C);
168 tmp[11] = Some(Amphipod::D);
169 tmp[12] = Some(Amphipod::D);
170 tmp
171 };
172 let mut min_cost = None;
173 let mut queue = VecDeque::new();
174 queue.push_back((0usize, init_pos));
175 while let Some((cost, pos)) = queue.pop_front() {
176 // check if we've reached destination
177 if (0..pos.len()).all(|i| pos[i] == final_pos[i]) {
178 min_cost = match min_cost {
179 None => Some(cost),
180 Some(min_cost) => Some(min_cost.min(cost)),
181 };
182 continue;
183 }
184 // check possible moves for each amphipod, perform one of the following:
185 // 1. from room pos to corridor pos + from corridor pos to dest room pos
186 // 2. from room pos directly to dest room pos
187 for curr_pos in 0..map_size {
188 if let Some(x) = pos[curr_pos] {
189 let dest_room = match x {
190 Amphipod::A => (2, 3),
191 Amphipod::B => (5, 6),
192 Amphipod::C => (8, 9),
193 Amphipod::D => (11, 12),
194 };
195 // no need to move if already at destination room
196 if curr_pos == dest_room.1
197 || (curr_pos == dest_room.0 && pos[dest_room.1] == Some(x))
198 {
199 continue;
200 }
201 // pick dest
202 if let Some(dest_pos) = match (pos[dest_room.0], pos[dest_room.1]) {
203 (None, None) => Some(dest_room.1),
204 (None, Some(y)) => {
205 if y == x {
206 Some(dest_room.0)
207 } else {
208 None
209 }
210 }
211 _ => None,
212 } {
213 // move to dest room if available
214 if is_reachable(&pos, curr_pos, dest_pos) {
215 let next_cost =
216 cost + x.cost() * step_count.get(&(curr_pos, dest_pos)).unwrap();
217 if let Some(min_cost) = min_cost {
218 if min_cost < next_cost {
219 continue;
220 }
221 }
222 let mut next_pos = pos.clone();
223 next_pos[curr_pos] = None;
224 next_pos[dest_pos] = Some(x);
225 queue.push_back((next_cost, next_pos));
226 }
227 } else if room_pos.contains(&curr_pos) {
228 // try one of the corridor positions if starting from room pos
229 for &dest_pos in corridor_pos.iter() {
230 if pos[dest_pos].is_none() && is_reachable(&pos, curr_pos, dest_pos) {
231 let next_cost =
232 cost + x.cost() * step_count.get(&(curr_pos, dest_pos)).unwrap();
233 if let Some(min_cost) = min_cost {
234 if min_cost < next_cost {
235 continue;
236 }
237 }
238 let mut next_pos = pos.clone();
239 next_pos[curr_pos] = None;
240 next_pos[dest_pos] = Some(x);
241 queue.push_back((next_cost, next_pos));
242 }
243 }
244 }
245 }
246 }
247 }
248 min_cost.unwrap()
249 }
250 fn part_2(input: &Vec<Vec<Amphipod>>) -> usize {
251 // #################
252 // #01.6.11.16.2122#
253 // ###2# 7#12#17####
254 // #3# 8#13#18#
255 // #4# 9#14#19#
256 // #5#10#15#20#
257 // ############
258 let map_size = 23;
259 let corridor_pos = [0, 1, 6, 11, 16, 21, 22]
260 .iter()
261 .map(|&x| x as usize)
262 .collect::<HashSet<usize>>();
263 let room_pos = [2, 3, 4, 5, 7, 8, 9, 10, 12, 13, 14, 15, 17, 18, 19, 20]
264 .iter()
265 .map(|&x| x as usize)
266 .collect::<HashSet<usize>>();
267 let entrance_map = {
268 let mut tmp = HashMap::<usize, usize>::new();
269 for &(a, b, c, d) in [
270 (2, 3, 4, 5),
271 (7, 8, 9, 10),
272 (12, 13, 14, 15),
273 (17, 18, 19, 20),
274 ]
275 .iter()
276 {
277 tmp.insert(a, a);
278 tmp.insert(b, a);
279 tmp.insert(c, a);
280 tmp.insert(d, a);
281 }
282 tmp
283 };
284 let is_reachable = |pos: &[Option<Amphipod>], curr_pos: usize, dest_pos: usize| -> bool {
285 // assumes dest_pos is reachable if inside a room
286 let corridor_clear = corridor_pos
287 .iter()
288 .filter(|&p| (*p > curr_pos && *p < dest_pos) || (*p > dest_pos && *p < curr_pos))
289 .all(|&p| pos[p].is_none());
290 let entrance_clear = if let Some(&entrance_pos) = entrance_map.get(&curr_pos) {
291 (entrance_pos..curr_pos).all(|p| pos[p].is_none())
292 } else {
293 true
294 };
295 corridor_clear && entrance_clear
296 };
297 let step_count = {
298 let mut step_count = HashMap::new();
299 // build up dist 1 step counts
300 // intersections
301 for &(a, b, c) in [(1, 2, 6), (6, 7, 11), (11, 12, 16), (16, 17, 21)].iter() {
302 step_count.insert((a, b), 2);
303 step_count.insert((b, a), 2);
304 step_count.insert((a, c), 2);
305 step_count.insert((c, a), 2);
306 step_count.insert((c, b), 2);
307 step_count.insert((b, c), 2);
308 }
309 // room
310 for &(a, b) in [(2, 5), (7, 10), (12, 15), (17, 20)].iter() {
311 for start in a..=b {
312 for end in (start + 1)..=b {
313 if start != end {
314 step_count.insert((start, end), end - start);
315 step_count.insert((end, start), end - start);
316 }
317 }
318 }
319 }
320 // corridor ends
321 for &(a, b) in [(0, 1), (21, 22)].iter() {
322 step_count.insert((a, b), 1);
323 step_count.insert((b, a), 1);
324 }
325 map_routes(map_size, step_count)
326 };
327 let init_pos = {
328 let mut tmp = vec![None; map_size];
329 tmp[2] = Some(input[0][0]);
330 tmp[3] = Some(Amphipod::D);
331 tmp[4] = Some(Amphipod::D);
332 tmp[5] = Some(input[1][0]);
333 tmp[7] = Some(input[0][1]);
334 tmp[8] = Some(Amphipod::C);
335 tmp[9] = Some(Amphipod::B);
336 tmp[10] = Some(input[1][1]);
337 tmp[12] = Some(input[0][2]);
338 tmp[13] = Some(Amphipod::B);
339 tmp[14] = Some(Amphipod::A);
340 tmp[15] = Some(input[1][2]);
341 tmp[17] = Some(input[0][3]);
342 tmp[18] = Some(Amphipod::A);
343 tmp[19] = Some(Amphipod::C);
344 tmp[20] = Some(input[1][3]);
345 tmp
346 };
347 let final_pos = {
348 let mut tmp = vec![None; map_size];
349 for a in 2..=5 {
350 tmp[a] = Some(Amphipod::A);
351 }
352 for b in 7..=10 {
353 tmp[b] = Some(Amphipod::B);
354 }
355 for c in 12..=15 {
356 tmp[c] = Some(Amphipod::C);
357 }
358 for d in 17..=20 {
359 tmp[d] = Some(Amphipod::D);
360 }
361 tmp
362 };
363 let mut min_cost = None;
364 let mut queue = VecDeque::new();
365 queue.push_back((0usize, init_pos));
366 while let Some((cost, pos)) = queue.pop_front() {
367 // check if we've reached destination
368 if (0..pos.len()).all(|i| pos[i] == final_pos[i]) {
369 min_cost = match min_cost {
370 None => Some(cost),
371 Some(min_cost) => Some(min_cost.min(cost)),
372 };
373 continue;
374 }
375 // check possible moves for each amphipod, perform one of the following:
376 // 1. from room pos to corridor pos + from corridor pos to dest room pos
377 // 2. from room pos directly to dest room pos
378 for curr_pos in 0..map_size {
379 if let Some(x) = pos[curr_pos] {
380 // check if it can/need to move to destination room
381 let dest_room = match x {
382 Amphipod::A => (2, 3, 4, 5),
383 Amphipod::B => (7, 8, 9, 10),
384 Amphipod::C => (12, 13, 14, 15),
385 Amphipod::D => (17, 18, 19, 20),
386 };
387 // no need to move if already at destination room
388 if curr_pos == dest_room.3
389 || (curr_pos == dest_room.2 && pos[dest_room.3] == Some(x))
390 || (curr_pos == dest_room.1
391 && pos[dest_room.2] == Some(x)
392 && pos[dest_room.3] == Some(x))
393 || (curr_pos == dest_room.0
394 && pos[dest_room.1] == Some(x)
395 && pos[dest_room.2] == Some(x)
396 && pos[dest_room.3] == Some(x))
397 {
398 continue;
399 }
400 // pick dest
401 if let Some(dest_pos) = match (
402 pos[dest_room.0],
403 pos[dest_room.1],
404 pos[dest_room.2],
405 pos[dest_room.3],
406 ) {
407 (None, None, None, None) => Some(dest_room.3),
408 (None, None, None, Some(y3)) => {
409 if y3 == x {
410 Some(dest_room.2)
411 } else {
412 None
413 }
414 }
415 (None, None, Some(y2), Some(y3)) => {
416 if y3 == x && y2 == x {
417 Some(dest_room.1)
418 } else {
419 None
420 }
421 }
422 (None, Some(y1), Some(y2), Some(y3)) => {
423 if y3 == x && y2 == x && y1 == x {
424 Some(dest_room.0)
425 } else {
426 None
427 }
428 }
429 _ => None,
430 } {
431 // move to dest room if available
432 if is_reachable(&pos, curr_pos, dest_pos) {
433 let next_cost =
434 cost + x.cost() * step_count.get(&(curr_pos, dest_pos)).unwrap();
435 if let Some(min_cost) = min_cost {
436 if min_cost < next_cost {
437 continue;
438 }
439 }
440 let mut next_pos = pos.clone();
441 next_pos[curr_pos] = None;
442 next_pos[dest_pos] = Some(x);
443 queue.push_back((next_cost, next_pos));
444 }
445 } else if room_pos.contains(&curr_pos) {
446 // try one of the corridor positions if starting from room pos
447 for &dest_pos in corridor_pos.iter() {
448 if pos[dest_pos].is_none() && is_reachable(&pos, curr_pos, dest_pos) {
449 let next_cost =
450 cost + x.cost() * step_count.get(&(curr_pos, dest_pos)).unwrap();
451 if let Some(min_cost) = min_cost {
452 if min_cost < next_cost {
453 continue;
454 }
455 }
456 let mut next_pos = pos.clone();
457 next_pos[curr_pos] = None;
458 next_pos[dest_pos] = Some(x);
459 queue.push_back((next_cost, next_pos));
460 }
461 }
462 }
463 }
464 }
465 }
466 min_cost.unwrap()
467 }