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

year2024/
day15.rs
