aoc/year2024/
day18.rs

1//! # RAM Run
2//!
3//! We use a trick to speed things up. Instead of storing `#` and `.` in the grid, we store
4//! the time when a block arrives. For example:
5//!
6//! ```none
7//!        ...#...    ∞ ∞ ∞ 3 ∞ ∞ ∞
8//! 5,4    ..#....    ∞ ∞ 4 ∞ ∞ ∞ ∞
9//! 4,2    ....#..    ∞ ∞ ∞ ∞ 1 ∞ ∞
10//! 4,5 => ....... => ∞ ∞ ∞ ∞ ∞ ∞ ∞
11//! 3,0    .....#.    ∞ ∞ ∞ ∞ ∞ 0 ∞
12//! 2,1    ....#..    ∞ ∞ ∞ ∞ 2 ∞ ∞
13//!        .......    ∞ ∞ ∞ ∞ ∞ ∞ ∞
14//! ```
15//!
16//! Now we can [BFS](https://en.wikipedia.org/wiki/Breadth-first_search) from any arbitrary
17//! start time. Squares are safe if the grid time is greater than the start time.
18//!
19//! Part two uses an incremental flood fill, getting a little further each time and removing
20//! blocking bytes in descending order of time until we reach the exit.
21//!
22//! * Start with `t = i32::MAX - 1`.
23//! * Start flood fill from top-left origin.
24//! * If we encounter a blocking byte with a time less than `t` then push `(time, position)` onto a
25//!   max heap keyed by time.
26//! * If we exhaust the flood fill `VecDeque` then pop the heap's top item. This is the oldest byte
27//!   that we encountered blocking the way. Set `t` to the byte's time and push position to the
28//!   deque.
29//! * Restart flood fill from new position until we reach the exit.
30use std::collections::VecDeque;
31
32use crate::util::grid::*;
33use crate::util::heap::*;
34use crate::util::iter::*;
35use crate::util::parse::*;
36use crate::util::point::*;
37
38pub fn parse(input: &str) -> Grid<i32> {
39    let mut grid = Grid::new(71, 71, i32::MAX);
40
41    for (i, [x, y]) in input.iter_signed().chunk::<2>().enumerate() {
42        grid[Point::new(x, y)] = i as i32;
43    }
44
45    grid
46}
47
48/// BFS from start to exit using a fixed time of 1024.
49pub fn part1(grid: &Grid<i32>) -> u32 {
50    let mut grid = grid.clone();
51    let mut todo = VecDeque::from([(ORIGIN, 0)]);
52
53    grid[ORIGIN] = 0;
54
55    while let Some((position, cost)) = todo.pop_front() {
56        if position == Point::new(70, 70) {
57            return cost;
58        }
59
60        for next in ORTHOGONAL.map(|o| position + o) {
61            if grid.contains(next) && grid[next] > 1024 {
62                grid[next] = 0;
63                todo.push_back((next, cost + 1));
64            }
65        }
66    }
67
68    unreachable!()
69}
70
71/// Incremental flood fill that removes one blocking byte at a time in descending order.
72pub fn part2(grid: &Grid<i32>) -> String {
73    let exit = Point::new(70, 70);
74
75    let mut time = i32::MAX - 1;
76    let mut last = ORIGIN;
77    let mut grid = grid.clone();
78    let mut todo = VecDeque::from([ORIGIN]);
79    let mut heap = MinHeap::new();
80
81    grid[ORIGIN] = 0;
82
83    loop {
84        // Incremental flood fill that makes as much progress as possible.
85        while let Some(position) = todo.pop_front() {
86            if position == exit {
87                return format!("{},{}", last.x, last.y);
88            }
89
90            for next in ORTHOGONAL.map(|o| position + o) {
91                if grid.contains(next) {
92                    if time < grid[next] {
93                        grid[next] = 0;
94                        todo.push_back(next);
95                    } else {
96                        // Use negative value to convert min-heap to max-heap.
97                        heap.push(-grid[next], next);
98                    }
99                }
100            }
101        }
102
103        // Remove the latest blocking byte then try to make a little more progress in flood fill.
104        let (negated, blocked) = heap.pop().unwrap();
105        time = -negated;
106        last = blocked;
107        todo.push_back(blocked);
108    }
109}
aoc/year2024/day18.rs

aoc/year2024/
day18.rs
