bwc9876.dev
Advent of Code solutions
1use std::collections::{HashMap, HashSet};
2
3use advent_core::{day_stuff, ex_for_day, Day};
4use utils::{
5 dir::{Direction, Movement},
6 grid::Grid,
7 pos::Position,
8 tiles, upos,
9};
10
11pub struct Day15;
12
13tiles!(Tile, [
14 '.' => Empty,
15 '@' => Robot,
16 '#' => Wall,
17 'O' => Box,
18 '[' => BoxLeft,
19 ']' => BoxRight,
20]);
21
22fn parse_instruction(c: char) -> Direction {
23 match c {
24 '^' => Direction::North,
25 '<' => Direction::West,
26 '>' => Direction::East,
27 'v' => Direction::South,
28 _ => unreachable!("For {c:?}"),
29 }
30}
31
32type PosMap = HashMap<Position, Tile>;
33
34fn movement(robo: Position, dir: Direction, map: &mut PosMap) -> Option<Position> {
35 let mut next_pos = robo.add(&dir.get_kernel());
36 let mut to_update = Vec::with_capacity(20);
37 loop {
38 let next_tile = map.get(&next_pos).unwrap();
39 if *next_tile == Tile::Wall {
40 return None;
41 } else if *next_tile == Tile::Box {
42 to_update.push(next_pos);
43 next_pos = next_pos.add(&dir.get_kernel());
44 } else {
45 // Is Empty
46 to_update.push(next_pos);
47 break;
48 }
49 }
50 assert!(!to_update.is_empty());
51 let first = to_update.first().unwrap();
52 *map.get_mut(first).unwrap() = Tile::Robot;
53 *map.get_mut(&robo).unwrap() = Tile::Empty;
54 if to_update.len() >= 2 {
55 *map.get_mut(to_update.last().unwrap()).unwrap() = Tile::Box;
56 }
57 Some(*first)
58}
59
60fn movement_pt_2(robo: Position, dir: Direction, map: &mut PosMap) -> Option<Position> {
61 let kern = dir.get_kernel();
62 let mut to_check = HashSet::from_iter([robo.add(&kern)]);
63 let mut to_update = Vec::with_capacity(40);
64 to_update.push((robo.add(&kern), Tile::Robot));
65 while !to_check.is_empty() {
66 let mut new_check = HashSet::new();
67 for check in to_check.into_iter() {
68 let new_tile = *map.get(&check).unwrap();
69 if new_tile == Tile::Wall {
70 return None;
71 } else if new_tile == Tile::BoxLeft && !dir.is_horizontal() {
72 let my_new_pos = check.add(&kern);
73 let r_pos = check.add(&upos!(1, 0));
74 let r_new_pos = r_pos.add(&kern);
75 to_update.push((my_new_pos, Tile::BoxLeft));
76 to_update.push((r_new_pos, Tile::BoxRight));
77 new_check.insert(my_new_pos);
78 new_check.insert(r_new_pos);
79 } else if new_tile == Tile::BoxRight && !dir.is_horizontal() {
80 let my_new_pos = check.add(&kern);
81 let l_pos = check.sub(&upos!(1, 0));
82 let l_new_pos = l_pos.add(&kern);
83 to_update.push((my_new_pos, Tile::BoxRight));
84 to_update.push((l_new_pos, Tile::BoxLeft));
85 new_check.insert(my_new_pos);
86 new_check.insert(l_new_pos);
87 } else if new_tile != Tile::Empty {
88 to_update.push((check.add(&kern), new_tile));
89 new_check.insert(check.add(&kern));
90 }
91 }
92 to_check = new_check;
93 }
94 for (pos, tile) in to_update.into_iter().rev() {
95 *map.get_mut(&pos).unwrap() = tile;
96 *map.get_mut(&pos.sub(&kern)).unwrap() = Tile::Empty;
97 }
98 Some(robo.add(&kern))
99}
100
101fn gps(pos_map: &PosMap) -> usize {
102 pos_map
103 .iter()
104 .filter_map(|(pos, tile)| {
105 if matches!(*tile, Tile::Box | Tile::BoxLeft) {
106 Some(100 * pos.y as usize + pos.x as usize)
107 } else {
108 None
109 }
110 })
111 .sum()
112}
113
114type Input = (Position, PosMap, Vec<Direction>);
115
116fn actual_parse(input: &str) -> Input {
117 let (map, dirs) = input.trim().split_once("\n\n").unwrap();
118 let dirs = dirs
119 .split('\n')
120 .flat_map(|l| l.chars().map(parse_instruction))
121 .collect();
122
123 let grid = Grid::<Tile>::parse(map);
124
125 let robo = grid.find_tile(&Tile::Robot).unwrap();
126
127 let pos_map = grid.iter().map(|(pos, tile)| (pos, *tile)).collect();
128
129 (robo, pos_map, dirs)
130}
131
132fn actual_parse_part_2(input: &str) -> Input {
133 let replace = input.replace('#', "##");
134 let replace = replace.replace('.', "..");
135 let replace = replace.replace('O', "[]");
136 let replace = replace.replace('@', "@.");
137 actual_parse(&replace)
138}
139
140impl Day for Day15 {
141 day_stuff!(15, "10092", "9021");
142
143 fn part_1(input: Self::Input) -> Option<String> {
144 let (mut robo, mut pos_map, ins) = actual_parse(&input);
145 for i in ins {
146 if let Some(new_pos) = movement(robo, i, &mut pos_map) {
147 robo = new_pos;
148 }
149 }
150 Some(gps(&pos_map).to_string())
151 }
152
153 fn part_2(input: Self::Input) -> Option<String> {
154 let (mut robo, mut pos_map, ins) = actual_parse_part_2(&input);
155 for i in ins {
156 if let Some(new_pos) = movement_pt_2(robo, i, &mut pos_map) {
157 robo = new_pos;
158 }
159 }
160 Some(gps(&pos_map).to_string())
161 }
162}