1use std::fs;
2
3use hashbrown::HashMap;
4
5type Tile = u64;
6type Room = u64;
7type Amphipod = u64;
8
9const NUM_ROOM: usize = 4;
10
11type Rooms = [Room; NUM_ROOM];
12type Hallway = u64;
13type Paths = HashMap<(Room, Tile), Vec<Tile>>;
14
15const EXISTENCE_MASK: u64 = 0b100;
16const VALUE_MASK: u64 = 0b011;
17const MASK_WIDTH: u64 = 3;
18
19fn _push(vs: u64, v: u64) -> u64 {
20 (vs << MASK_WIDTH) | EXISTENCE_MASK | v
21}
22
23fn _pop(vs: u64) -> (u64, u64) {
24 let v = vs & VALUE_MASK;
25 (vs >> MASK_WIDTH, v)
26}
27
28fn _insert(vs: u64, k: u64, v: u64) -> u64 {
29 vs | (v | EXISTENCE_MASK) << (MASK_WIDTH * k)
30}
31
32fn _get(vs: u64, k: u64) -> u64 {
33 let value_mask = VALUE_MASK << (MASK_WIDTH * k);
34 (vs & value_mask) >> (MASK_WIDTH * k)
35}
36
37fn _remove(vs: u64, k: u64) -> (u64, u64) {
38 let v = _get(vs, k);
39 let erasure_mask = !((EXISTENCE_MASK | VALUE_MASK) << (MASK_WIDTH * k));
40 (vs & erasure_mask, v)
41}
42
43fn _is_empty(vs: u64) -> bool {
44 vs == 0
45}
46
47fn _contains(vs: u64, k: u64) -> bool {
48 let mask = EXISTENCE_MASK << (MASK_WIDTH * k);
49 vs & mask == mask
50}
51
52fn _fmt(vs: u64, len: u64) -> String {
53 (0..len)
54 .map(|i| match _contains(vs, i) {
55 false => '.',
56 true => {
57 let (_, v) = _remove(vs, i);
58 _fmt_amphipod(v)
59 }
60 })
61 .collect()
62}
63
64fn _rooms(input: &str) -> Rooms {
65 let mut lines = input.lines();
66 lines.next();
67 lines.next();
68 let mut result = [0; NUM_ROOM];
69 for line in lines.rev() {
70 for (occupant, room) in line
71 .trim()
72 .chars()
73 .filter(|ch| *ch != '#')
74 .zip([0, 1, 2, 3])
75 {
76 result[room] = _push(
77 result[room],
78 match occupant {
79 'A' => 0,
80 'B' => 1,
81 'C' => 2,
82 'D' => 3,
83 _ => panic!("Unexpected occupant '{}'", occupant),
84 },
85 );
86 }
87 }
88 result
89}
90
91const TILES: [Tile; 7] = [0, 1, 3, 5, 7, 9, 10];
92
93fn _paths() -> Paths {
94 let nogo = [2, 4, 6, 8];
95
96 let mut result = HashMap::new();
97 for room in 0..NUM_ROOM as u64 {
98 let src = _tile(room);
99 for dst in TILES {
100 let mut path = Vec::new();
101 if src < dst {
102 for step in src..=dst {
103 if !nogo.contains(&step) {
104 path.push(step);
105 }
106 }
107 } else {
108 for step in dst..=src {
109 if !nogo.contains(&step) {
110 path.insert(0, step);
111 }
112 }
113 }
114
115 result.insert((room, dst), path);
116 }
117 }
118 result
119}
120
121fn _accessible_tiles(paths: &Paths, hallway: Hallway, src: Room) -> Vec<Tile> {
122 let mut result = Vec::new();
123 for step in paths.get(&(src, 0)).unwrap() {
124 if _contains(hallway, *step) {
125 break;
126 }
127 result.push(*step);
128 }
129 for step in paths.get(&(src, 10)).unwrap() {
130 if _contains(hallway, *step) {
131 break;
132 }
133 result.push(*step);
134 }
135 result
136}
137
138fn _room_is_accessible(paths: &Paths, hallway: Hallway, src: Tile, dst: Room) -> bool {
139 for step in paths.get(&(dst, src)).unwrap() {
140 if src == *step {
141 continue;
142 }
143 if _contains(hallway, *step) {
144 return false;
145 }
146 }
147 true
148}
149
150fn _room_contains_only(vs: u64, v: u64) -> bool {
151 for k in 0.. {
152 if !_contains(vs, k) {
153 return true;
154 }
155 if _get(vs, k) != v {
156 return false;
157 }
158 }
159 panic!(
160 "Ran out of spots to check for {}",
161 _fmt(vs, NUM_ROOM as u64)
162 );
163}
164
165fn _move_from_hallway(paths: &Paths, hallway: &mut Hallway, rooms: &mut Rooms) {
166 let mut making_progress = true;
167 while making_progress {
168 making_progress = false;
169 for src in TILES {
170 if _contains(*hallway, src) {
171 let dst = _get(*hallway, src);
172 if !_room_is_accessible(paths, *hallway, src, dst) {
173 continue;
174 }
175 if !_room_contains_only(rooms[dst as usize], dst) {
176 continue;
177 }
178 let tmp = _remove(*hallway, src);
179 *hallway = tmp.0;
180 rooms[dst as usize] = _push(rooms[dst as usize], dst);
181 making_progress = true;
182 }
183 }
184 }
185}
186
187fn _tile(room: Room) -> Tile {
188 room * 2 + 2
189}
190
191fn _multiplier(amphipod: Amphipod) -> u64 {
192 10_u64.pow(amphipod as u32)
193}
194
195fn _distance(left: u64, right: u64) -> u64 {
196 if left < right {
197 right - left
198 } else {
199 left - right
200 }
201}
202
203fn _room_hallway_distance(room: Room, location: Tile, amphipod: Amphipod) -> u64 {
204 (_distance(_tile(room), location) + _distance(_tile(amphipod), location)) as u64
205}
206
207fn _fmt_amphipod(amphipod: Amphipod) -> char {
208 match amphipod {
209 0 => 'A',
210 1 => 'B',
211 2 => 'C',
212 3 => 'D',
213 _ => panic!("Unkown amphipod '{}'", amphipod),
214 }
215}
216
217fn _print_all(title: &str, hallway: Hallway, rooms: Rooms) {
218 println!("{}", title);
219 println!("{}", _fmt(hallway, 11));
220 for room in rooms {
221 println!("{}", _fmt(room, 5));
222 }
223}
224
225fn _min_downstream_cost(rooms: Rooms) -> u64 {
226 let mut result = 0;
227 for (src, room) in rooms.iter().enumerate() {
228 for j in 0.. {
229 if !_contains(*room, j) {
230 break;
231 }
232 let dst = _get(*room, j);
233 if src as u64 != dst {
234 result += _distance(_tile(src as u64), _tile(dst)) * _multiplier(dst);
235 }
236 }
237 }
238 result
239}
240
241fn _min_cost_from_hallway(
242 cache: &mut HashMap<(Hallway, Rooms), Option<u64>>,
243 paths: &Paths,
244 mut hallway: Hallway,
245 mut rooms: Rooms,
246 upstream_cost: u64,
247 mut best_total_cost: u64,
248) -> Option<u64> {
249 let key = (hallway, rooms);
250 if cache.contains_key(&key) {
251 return *cache.get(&key).unwrap();
252 }
253
254 _move_from_hallway(paths, &mut hallway, &mut rooms);
255
256 if _is_empty(hallway)
257 && (0..NUM_ROOM as u64)
258 .all(|i| !_is_empty(rooms[i as usize]) && _room_contains_only(rooms[i as usize], i))
259 {
260 cache.insert(key, Some(0));
261 return Some(0);
262 }
263
264 let mut ok = false;
265 let mut best_cost = std::u64::MAX / 2;
266 for src in 0..NUM_ROOM as u64 {
267 if _room_contains_only(rooms[src as usize], src) {
268 continue;
269 }
270
271 let mut new_rooms = rooms;
272 let (new_room, amphipod) = _pop(rooms[src as usize]);
273 new_rooms[src as usize] = new_room;
274
275 for dst in _accessible_tiles(paths, hallway, src) {
276 let marginal_cost = _room_hallway_distance(src, dst, amphipod) * _multiplier(amphipod);
277
278 let min_downstream_cost = _min_downstream_cost(new_rooms);
279 let min_total_cost = upstream_cost + marginal_cost + min_downstream_cost;
280 if best_total_cost <= min_total_cost {
281 continue;
282 }
283
284 let new_hallway = _insert(hallway, dst, amphipod);
285
286 let downstream_cost = match _min_cost_from_hallway(
287 cache,
288 paths,
289 new_hallway,
290 new_rooms,
291 upstream_cost + marginal_cost,
292 best_total_cost,
293 ) {
294 Some(cost) => cost,
295 None => continue,
296 };
297 let cost = marginal_cost + downstream_cost;
298 if cost < best_cost {
299 ok = true;
300 best_cost = cost;
301 best_total_cost = upstream_cost + cost;
302 } else {
303 }
304 }
305 }
306 if ok {
307 cache.insert(key, Some(best_cost));
308 return Some(best_cost);
309 }
310 cache.insert(key, None);
311 None
312}
313
314fn _departure_penalty(room: Room, room_num: u64) -> u64 {
315 let mut result = 0;
316 for i in 0.. {
317 if !_contains(room, i) {
318 return result;
319 }
320 for j in i.. {
321 if !_contains(room, j) {
322 break;
323 }
324 if _get(room, j) != room_num {
325 result += (i + 1) * _multiplier(_get(room, i));
326 break;
327 }
328 }
329 }
330 panic!("Oups")
331}
332
333fn _arrival_penalty(room: Room, room_num: u64) -> u64 {
334 let mut result = 0;
335 for i in 0.. {
336 if !_contains(room, i) {
337 return result;
338 }
339 for j in i.. {
340 if !_contains(room, j) {
341 break;
342 }
343 if _get(room, j) != room_num {
344 result += (i + 1) * _multiplier(room_num);
345 break;
346 }
347 }
348 }
349 panic!("Oups")
350}
351
352fn _penalty(rooms: Rooms) -> u64 {
353 (0..NUM_ROOM)
354 .map(|i| _departure_penalty(rooms[i], i as u64) + _arrival_penalty(rooms[i], i as u64))
355 .sum()
356}
357
358fn _part_x(rooms: Rooms) -> u64 {
359 let paths = _paths();
360 let mut cache = HashMap::new();
361 let from_hallway =
362 _min_cost_from_hallway(&mut cache, &paths, 0, rooms, 0, std::u64::MAX).unwrap();
363 let from_rooms = _penalty(rooms);
364 from_hallway + from_rooms
365}
366
367pub fn part_1(input: &str) -> u64 {
368 let rooms = _rooms(input);
369 _part_x(rooms)
370}
371
372pub fn part_2(input: &str) -> u64 {
373 let mut rooms = _rooms(input);
374 let mut tmp = _pop(rooms[0]);
375 rooms[0] = _push(tmp.0, 3);
376 rooms[0] = _push(rooms[0], 3);
377 rooms[0] = _push(rooms[0], tmp.1);
378
379 tmp = _pop(rooms[1]);
380 rooms[1] = _push(tmp.0, 1);
381 rooms[1] = _push(rooms[1], 2);
382 rooms[1] = _push(rooms[1], tmp.1);
383
384 tmp = _pop(rooms[2]);
385 rooms[2] = _push(tmp.0, 0);
386 rooms[2] = _push(rooms[2], 1);
387 rooms[2] = _push(rooms[2], tmp.1);
388
389 tmp = _pop(rooms[3]);
390 rooms[3] = _push(tmp.0, 2);
391 rooms[3] = _push(rooms[3], 0);
392 rooms[3] = _push(rooms[3], tmp.1);
393
394 _part_x(rooms)
395}
396
397fn _from_file<F, T>(func: F, stem: &str) -> T
398where
399 F: Fn(&str) -> T,
400{
401 func(&fs::read_to_string(format!("inputs/23/{}.txt", stem)).unwrap())
402}
403
404#[cfg(test)]
405mod tests {
406 use super::*;
407
408 #[test]
409 fn part_1_works_on_example() {
410 assert_eq!(_from_file(part_1, "example"), 12521);
411 }
412
413 #[test]
414 fn part_1_works_on_input() {
415 assert_eq!(_from_file(part_1, "input"), 14510);
416 }
417
418 #[test]
419 fn part_1_works_on_input_1() {
420 assert_eq!(_from_file(part_1, "input_1"), 11332);
421 }
422
423 #[test]
424 fn part_2_works_on_example() {
425 assert_eq!(_from_file(part_2, "example"), 44169);
426 }
427
428 #[test]
429 fn part_2_works_on_input() {
430 assert_eq!(_from_file(part_2, "input"), 49180);
431 }
432
433 #[test]
434 fn part_2_works_on_input_1() {
435 assert_eq!(_from_file(part_2, "input_1"), 49936);
436 }
437
438 #[test]
439 fn push_pop() {
440 let vs = 0;
441 assert_eq!(_fmt(vs, 4), "....");
442 let vs = _push(vs, 0);
443 assert_eq!(_fmt(vs, 4), "A...");
444 let vs = _push(vs, 0);
445 assert_eq!(_fmt(vs, 4), "AA..");
446 let vs = _push(vs, 1);
447 assert_eq!(_fmt(vs, 4), "BAA.");
448 let (vs, v) = _pop(vs);
449 assert_eq!(_fmt(vs, 4), "AA..");
450 assert_eq!(_fmt_amphipod(v), 'B');
451 let vs = _insert(vs, 2, 3);
452 assert_eq!(_fmt(vs, 4), "AAD.");
453 let (vs, v) = _pop(vs);
454 assert_eq!(_fmt(vs, 4), "AD..");
455 assert_eq!(_fmt_amphipod(v), 'A');
456 let vs = _insert(vs, 3, 2);
457 assert_eq!(_fmt(vs, 4), "AD.C");
458 let (vs, v) = _remove(vs, 1);
459 assert_eq!(_fmt(vs, 4), "A..C");
460 assert_eq!(_fmt_amphipod(v), 'D');
461 assert!(!_is_empty(vs));
462 let (vs, v) = _remove(vs, 3);
463 assert_eq!(_fmt(vs, 4), "A...");
464 assert_eq!(_fmt_amphipod(v), 'C');
465 assert!(!_is_empty(vs));
466 let (vs, v) = _pop(vs);
467 assert_eq!(_fmt(vs, 4), "....");
468 assert_eq!(_fmt_amphipod(v), 'A');
469 assert!(_is_empty(vs));
470 }
471}