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

year2024/
day15.rs
