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        match b {
51            b'<' => narrow(&mut grid, &mut position, LEFT),
52            b'>' => narrow(&mut grid, &mut position, RIGHT),
53            b'^' => narrow(&mut grid, &mut position, UP),
54            b'v' => narrow(&mut grid, &mut position, DOWN),
55            _ => (),
56        }
57    }
58
59    gps(&grid, b'O')
60}
61
62pub fn part2(input: &Input<'_>) -> i32 {
63    let (grid, moves) = input;
64
65    let mut grid = stretch(grid);
66    let mut position = grid.find(b'@').unwrap();
67    grid[position] = b'.';
68
69    // Reuse to minimize allocations.
70    let mut todo = Vec::with_capacity(50);
71
72    // Horizontal moves reuse the part one logic, vertical moves need to cascade.
73    for b in moves.bytes() {
74        match b {
75            b'<' | b'>' => narrow(&mut grid, &mut position, Point::from(b)),
76            b'^' | b'v' => wide(&mut grid, &mut position, Point::from(b), &mut todo),
77            _ => (),
78        }
79    }
80
81    gps(&grid, b'[')
82}
83
84fn narrow(grid: &mut Grid<u8>, start: &mut Point, direction: Point) {
85    let mut position = *start + direction;
86    let mut size = 1;
87
88    // Search for the next wall or open space.
89    while grid[position] != b'.' && grid[position] != b'#' {
90        position += direction;
91        size += 1;
92    }
93
94    // Move items one space in direction.
95    if grid[position] == b'.' {
96        let mut previous = b'.';
97        let mut position = *start + direction;
98
99        for _ in 0..size {
100            swap(&mut previous, &mut grid[position]);
101            position += direction;
102        }
103
104        // Move robot.
105        *start += direction;
106    }
107}
108
109fn wide(grid: &mut Grid<u8>, start: &mut Point, direction: Point, todo: &mut Vec<Point>) {
110    // Short circuit if path in front of robot is empty.
111    if grid[*start + direction] == b'.' {
112        *start += direction;
113        return;
114    }
115
116    // Clear any items from previous push.
117    todo.clear();
118    // Add dummy item to prevent index out of bounds when checking for previously added boxes.
119    todo.push(ORIGIN);
120    todo.push(*start);
121    let mut index = 1;
122
123    while index < todo.len() {
124        let next = todo[index] + direction;
125        index += 1;
126
127        // Add boxes strictly left to right.
128        let (first, second) = match grid[next] {
129            b'[' => (next, next + RIGHT),
130            b']' => (next + LEFT, next),
131            b'#' => return, // Return early if there's a wall in the way.
132            _ => continue,  // Open space doesn't add any more items to move.
133        };
134
135        // Check if this box has already been added by the previous box in this row.
136        if first != todo[todo.len() - 2] {
137            todo.push(first);
138            todo.push(second);
139        }
140    }
141
142    // Move boxes in reverse order, skipping the dummy item and robot.
143    for &point in todo[2..].iter().rev() {
144        grid[point + direction] = grid[point];
145        grid[point] = b'.';
146    }
147
148    // Move robot.
149    *start += direction;
150}
151
152fn stretch(grid: &Grid<u8>) -> Grid<u8> {
153    let mut next = Grid::new(grid.width * 2, grid.height, b'.');
154
155    for y in 0..grid.height {
156        for x in 0..grid.width {
157            // Grid is already filled with '.', so only need to handle other kinds.
158            let (left, right) = match grid[Point::new(x, y)] {
159                b'#' => (b'#', b'#'),
160                b'O' => (b'[', b']'),
161                b'@' => (b'@', b'.'),
162                _ => continue,
163            };
164
165            next[Point::new(2 * x, y)] = left;
166            next[Point::new(2 * x + 1, y)] = right;
167        }
168    }
169
170    next
171}
172
173fn gps(grid: &Grid<u8>, needle: u8) -> i32 {
174    let mut result = 0;
175
176    for y in 0..grid.height {
177        for x in 0..grid.width {
178            let point = Point::new(x, y);
179            if grid[point] == needle {
180                result += 100 * point.y + point.x;
181            }
182        }
183    }
184
185    result
186}
aoc/year2024/day15.rs

aoc/year2024/
day15.rs
