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::<i32>().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::new();
52
53    grid[ORIGIN] = 0;
54    todo.push_back((ORIGIN, 0));
55
56    while let Some((position, cost)) = todo.pop_front() {
57        if position == Point::new(70, 70) {
58            return cost;
59        }
60
61        for next in ORTHOGONAL.map(|o| position + o) {
62            if grid.contains(next) && grid[next] > 1024 {
63                grid[next] = 0;
64                todo.push_back((next, cost + 1));
65            }
66        }
67    }
68
69    unreachable!()
70}
71
72/// Incremental flood fill that removes one blocking byte at a time in descending order.
73pub fn part2(grid: &Grid<i32>) -> String {
74    let exit = Point::new(70, 70);
75
76    let mut time = i32::MAX - 1;
77    let mut last = ORIGIN;
78    let mut grid = grid.clone();
79    let mut todo = VecDeque::new();
80    let mut heap = MinHeap::new();
81
82    grid[ORIGIN] = 0;
83    todo.push_back(ORIGIN);
84
85    loop {
86        // Incremental flood fill that makes as much progress as possible.
87        while let Some(position) = todo.pop_front() {
88            if position == exit {
89                return format!("{},{}", last.x, last.y);
90            }
91
92            for next in ORTHOGONAL.map(|o| position + o) {
93                if grid.contains(next) {
94                    if time < grid[next] {
95                        grid[next] = 0;
96                        todo.push_back(next);
97                    } else if grid[next] < i32::MAX {
98                        // Use negative value to convert min-heap to max-heap.
99                        heap.push(-grid[next], next);
100                    }
101                }
102            }
103        }
104
105        // Remove the latest blocking byte then try to make a little more progress in flood fill.
106        let (first, saved) = heap.pop().unwrap();
107        time = -first;
108        last = saved;
109        todo.push_back(saved);
110    }
111}
aoc/year2024/day18.rs

aoc/year2024/
day18.rs
