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

aoc/year2024/
day15.rs
