aoc/year2024/
day15.rs

1//! # Warehouse Woes
2//!
3//! Festive version of [Sokoban](https://en.wikipedia.org/wiki/Sokoban).
4//!
5//! Part one loops in a straight line looking for the next space `.` or wall `#`. No bounds checks
6//! are needed as the maze is enclosed. If a space is found then all items are pushed one block
7//! in that direction.
8//!
9//! Part two reuses the part one logic for horizontal moves. Vertical moves use a
10//! [breadth-first search](https://en.wikipedia.org/wiki/Breadth-first_search) to identify the
11//! cascading boxes that need to be moved. Boxes are added strictly left to right to make checking
12//! for previously added boxes easier. To prevent adding a box twice we check that the
13//! item at `index - 2` is different. For example:
14//!
15//! ```none
16//!  @          Indices:
17//!  []         23
18//! [][]       4567
19//!  []         89
20//! ```
21//!
22//! When processing 6 we try to add 8, however 8 and 9 have already been added when processing 4
23//! so we skip.
24//!
25//! If any next space is a wall then we cancel the entire move and return right away. Otherwise
26//! all boxes are moved in the *reverse* order that they were found by the search.
27use std::mem::swap;
28
29use crate::util::grid::*;
30use crate::util::point::*;
31
32type Input<'a> = (Grid<u8>, &'a str);
33
34pub fn parse(input: &str) -> Input<'_> {
35    let (prefix, suffix) = input.split_once("\n\n").unwrap();
36    let grid = Grid::parse(prefix);
37    (grid, suffix)
38}
39
40pub fn part1(input: &Input<'_>) -> i32 {
41    let (grid, moves) = input;
42
43    // We don't need to move the robot symbol so mark as empty space once located.
44    let mut grid = grid.clone();
45    let mut position = grid.find(b'@').unwrap();
46    grid[position] = b'.';
47
48    // Treat moves as a single string ignoring any newline characters.
49    for b in moves.bytes() {
50        if b != b'\n' {
51            narrow(&mut grid, &mut position, Point::from(b));
52        }
53    }
54
55    gps(&grid, b'O')
56}
57
58pub fn part2(input: &Input<'_>) -> i32 {
59    let (grid, moves) = input;
60
61    let mut grid = stretch(grid);
62    let mut position = grid.find(b'@').unwrap();
63    grid[position] = b'.';
64
65    // Reuse to minimize allocations.
66    let mut todo = Vec::with_capacity(50);
67
68    // Horizontal moves reuse the part one logic, vertical moves need to cascade.
69    for b in moves.bytes() {
70        match b {
71            b'<' | b'>' => narrow(&mut grid, &mut position, Point::from(b)),
72            b'^' | b'v' => wide(&mut grid, &mut position, Point::from(b), &mut todo),
73            _ => (),
74        }
75    }
76
77    gps(&grid, b'[')
78}
79
80fn narrow(grid: &mut Grid<u8>, start: &mut Point, direction: Point) {
81    let mut position = *start + direction;
82    let mut size = 1;
83
84    // Search for the next wall or open space.
85    while grid[position] != b'.' && grid[position] != b'#' {
86        position += direction;
87        size += 1;
88    }
89
90    // Move items one space in direction.
91    if grid[position] == b'.' {
92        let mut previous = b'.';
93        let mut position = *start + direction;
94
95        for _ in 0..size {
96            swap(&mut previous, &mut grid[position]);
97            position += direction;
98        }
99
100        // Move robot.
101        *start += direction;
102    }
103}
104
105fn wide(grid: &mut Grid<u8>, start: &mut Point, direction: Point, todo: &mut Vec<Point>) {
106    // Short circuit if path in front of robot is empty.
107    if grid[*start + direction] == b'.' {
108        *start += direction;
109        return;
110    }
111
112    // Clear any items from previous push.
113    todo.clear();
114    // Add dummy item to prevent index out of bounds when checking for previously added boxes.
115    todo.push(ORIGIN);
116    todo.push(*start);
117    let mut index = 1;
118
119    while index < todo.len() {
120        let next = todo[index] + direction;
121        index += 1;
122
123        // Add boxes strictly left to right.
124        let (first, second) = match grid[next] {
125            b'[' => (next, next + RIGHT),
126            b']' => (next + LEFT, next),
127            b'#' => return, // Return early if there's a wall in the way.
128            _ => continue,  // Open space doesn't add any more items to move.
129        };
130
131        // Check if this box has already been added by the previous box in this row.
132        if first != todo[todo.len() - 2] {
133            todo.push(first);
134            todo.push(second);
135        }
136    }
137
138    // Move boxes in reverse order, skipping the dummy item and robot.
139    for &point in todo[2..].iter().rev() {
140        grid[point + direction] = grid[point];
141        grid[point] = b'.';
142    }
143
144    // Move robot.
145    *start += direction;
146}
147
148fn stretch(grid: &Grid<u8>) -> Grid<u8> {
149    let mut next = Grid::new(grid.width * 2, grid.height, b'.');
150
151    for y in 0..grid.height {
152        for x in 0..grid.width {
153            // Grid is already filled with '.', so only need to handle other kinds.
154            let (left, right) = match grid[Point::new(x, y)] {
155                b'#' => (b'#', b'#'),
156                b'O' => (b'[', b']'),
157                b'@' => (b'@', b'.'),
158                _ => continue,
159            };
160
161            next[Point::new(2 * x, y)] = left;
162            next[Point::new(2 * x + 1, y)] = right;
163        }
164    }
165
166    next
167}
168
169fn gps(grid: &Grid<u8>, needle: u8) -> i32 {
170    let mut result = 0;
171
172    for y in 0..grid.height {
173        for x in 0..grid.width {
174            if grid[Point::new(x, y)] == needle {
175                result += 100 * y + x;
176            }
177        }
178    }
179
180    result
181}
aoc/year2024/day15.rs

aoc/year2024/
day15.rs
