year2024/
day15.rs

1use utils::grid;
2use utils::prelude::*;
3
4/// Moving boxes around a grid.
5#[derive(Clone, Debug)]
6pub struct Day15<'a> {
7    cols: usize,
8    grid: Vec<u8>,
9    robot: usize,
10    moves: &'a str,
11}
12
13impl<'a> Day15<'a> {
14    pub fn new(input: &'a str, _: InputType) -> Result<Self, InputError> {
15        let Some((grid, moves)) = input.split_once("\n\n") else {
16            return Err(InputError::new(input, 0, "expected grid and moves"));
17        };
18
19        let (rows, cols, mut grid) = grid::from_str(grid, |b| match b {
20            b'.' | b'#' | b'O' | b'@' => Some(b),
21            _ => None,
22        })?;
23        if !grid::is_enclosed(rows, cols, &grid, |&b| b == b'#') {
24            return Err(InputError::new(
25                input,
26                0,
27                "expected grid to be enclosed by walls",
28            ));
29        }
30
31        let mut robots = grid.iter().enumerate().filter(|&(_, &b)| b == b'@');
32        let Some((robot, _)) = robots.next() else {
33            return Err(InputError::new(input, 0, "expected a robot"));
34        };
35        if robots.count() > 0 {
36            return Err(InputError::new(input, 0, "expected only one robot"));
37        }
38        grid[robot] = b'.';
39
40        if let Some(idx) = moves.find(|b| !matches!(b, '^' | 'v' | '<' | '>' | '\n')) {
41            return Err(InputError::new(
42                input,
43                &moves[idx..],
44                "expected ^, v, <, or >",
45            ));
46        }
47
48        Ok(Self {
49            cols,
50            grid,
51            robot,
52            moves,
53        })
54    }
55
56    #[must_use]
57    pub fn part1(&self) -> u32 {
58        let mut grid = self.grid.clone();
59        let mut robot = self.robot;
60
61        for offset in self.moves_iterator(self.cols) {
62            let next = robot.wrapping_add_signed(offset);
63            if grid[next] == b'.' {
64                robot = next;
65            } else if grid[next] == b'O' {
66                let mut next_free = next.wrapping_add_signed(offset);
67                while grid[next_free] == b'O' {
68                    next_free = next_free.wrapping_add_signed(offset);
69                }
70                if grid[next_free] == b'.' {
71                    grid[next_free] = b'O';
72                    grid[next] = b'.';
73                    robot = next;
74                }
75            }
76        }
77
78        Self::sum_box_coords(&grid, self.cols, b'O')
79    }
80
81    #[must_use]
82    pub fn part2(&self) -> u32 {
83        let mut grid = self
84            .grid
85            .iter()
86            .flat_map(|&b| match b {
87                b'#' => [b'#', b'#'],
88                b'.' => [b'.', b'.'],
89                b'O' => [b'[', b']'],
90                _ => unreachable!(),
91            })
92            .collect::<Vec<_>>();
93        let cols = self.cols * 2;
94        let mut robot = (self.robot / self.cols * cols) + (self.robot % self.cols * 2);
95
96        for offset in self.moves_iterator(cols) {
97            let next = robot.wrapping_add_signed(offset);
98            if grid[next] == b'.' {
99                robot = next;
100            } else if (grid[next] == b'[' || grid[next] == b']')
101                && Self::can_move_p2(&grid, next, offset)
102            {
103                Self::move_box_p2(&mut grid, next, offset);
104                robot = next;
105            }
106        }
107
108        Self::sum_box_coords(&grid, cols, b'[')
109    }
110
111    #[inline]
112    fn moves_iterator(&self, cols: usize) -> impl Iterator<Item = isize> + use<'_> {
113        self.moves.bytes().filter_map(move |c| match c {
114            b'^' => Some(-(cols as isize)),
115            b'v' => Some(cols as isize),
116            b'<' => Some(-1),
117            b'>' => Some(1),
118            _ => None,
119        })
120    }
121
122    #[inline]
123    fn sum_box_coords(grid: &[u8], cols: usize, box_byte: u8) -> u32 {
124        grid.iter()
125            .enumerate()
126            .map(|(i, &b)| {
127                if b == box_byte {
128                    100 * ((i / cols) as u32) + ((i % cols) as u32)
129                } else {
130                    0
131                }
132            })
133            .sum()
134    }
135
136    fn can_move_p2(grid: &[u8], pos: usize, offset: isize) -> bool {
137        let (left, right) = match grid[pos] {
138            b'[' => (pos, pos + 1),
139            b']' => (pos - 1, pos),
140            b'.' => return true,
141            b'#' => return false,
142            _ => unreachable!(),
143        };
144
145        if offset == -1 || offset == 1 {
146            Self::can_move_p2(grid, pos.wrapping_add_signed(offset), offset)
147        } else if grid[left.wrapping_add_signed(offset)] == b'[' {
148            // One box directly above/below, only need to recurse once
149            Self::can_move_p2(grid, left.wrapping_add_signed(offset), offset)
150        } else {
151            Self::can_move_p2(grid, left.wrapping_add_signed(offset), offset)
152                && Self::can_move_p2(grid, right.wrapping_add_signed(offset), offset)
153        }
154    }
155
156    fn move_box_p2(grid: &mut [u8], pos: usize, offset: isize) {
157        let (left, right) = match grid[pos] {
158            b'[' => (pos, pos + 1),
159            b']' => (pos - 1, pos),
160            b'.' => return,
161            _ => unreachable!(),
162        };
163
164        if offset == -1 || offset == 1 {
165            Self::move_box_p2(grid, pos.wrapping_add_signed(offset * 2), offset);
166        } else {
167            Self::move_box_p2(grid, left.wrapping_add_signed(offset), offset);
168            Self::move_box_p2(grid, right.wrapping_add_signed(offset), offset);
169        }
170
171        grid[left] = b'.';
172        grid[right] = b'.';
173        grid[left.wrapping_add_signed(offset)] = b'[';
174        grid[right.wrapping_add_signed(offset)] = b']';
175    }
176}
177
178examples!(Day15<'_> -> (u32, u32) [
179    {file: "day15_example0.txt", part1: 10092, part2: 9021},
180    {file: "day15_example1.txt", part1: 2028},
181    {file: "day15_example2.txt", part2: 618},
182]);
year2024/day15.rs

year2024/
day15.rs
