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`
23//! * Start flood fill from top-left origin.
24//! * If we encounter a blocking byte with a time less than `t`
25//!   then push `(time, position)` onto a max heap keyed by time.
26//! * If we exhaust the flood fill `VecDeque` then pop the heap's top item.
27//!   This is the oldest byte that we encountered blocking the way.
28//!   Set `t` to the byte's time and push position to the dequeue.
29//! * Restart flood fill from new position until we reach the exit.
30use crate::util::grid::*;
31use crate::util::heap::*;
32use crate::util::iter::*;
33use crate::util::parse::*;
34use crate::util::point::*;
35use std::collections::VecDeque;
36
37pub fn parse(input: &str) -> Grid<i32> {
38    let mut grid = Grid::new(71, 71, i32::MAX);
39
40    for (i, [x, y]) in input.iter_signed::<i32>().chunk::<2>().enumerate() {
41        grid[Point::new(x, y)] = i as i32;
42    }
43
44    grid
45}
46
47/// BFS from start to exit using a fixed time of 1024.
48pub fn part1(grid: &Grid<i32>) -> u32 {
49    let mut grid = grid.clone();
50    let mut todo = VecDeque::new();
51
52    grid[ORIGIN] = 0;
53    todo.push_back((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 mut time = i32::MAX;
74    let mut heap = MinHeap::new();
75
76    let mut grid = grid.clone();
77    let mut todo = VecDeque::new();
78
79    grid[ORIGIN] = 0;
80    todo.push_back(ORIGIN);
81
82    loop {
83        // Incremental flood fill that makes as much progress as possible.
84        while let Some(position) = todo.pop_front() {
85            if position == Point::new(70, 70) {
86                let index = grid.bytes.iter().position(|&b| b == time).unwrap() as i32;
87                return format!("{},{}", index % grid.width, index / grid.width);
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 (first, saved) = heap.pop().unwrap();
105        time = -first;
106        todo.push_back(saved);
107    }
108}
aoc/year2024/day18.rs

aoc/year2024/
day18.rs
