aoc/year2022/
day14.rs

1//! # Regolith Reservoir
2//!
3//! We could simulate each grain of sand falling one at a time, for example:
4//!
5//! ```none
6//!     #o#    # #    # #    # #
7//!     # #    #o#    # #    # #
8//!     # # => # # => #o# => # #
9//!     # #    # #    # #    #o#
10//!     ###    ###    ###    ###
11//! ```
12//!
13//! In this example it would take 4 steps to simulate the first grain, 3 steps for the second
14//! and so on. More generally it would take `∑n` = `n * (n + 1) / 2` or `O(n²)` complexity for
15//! the whole pile.
16//!
17//! We instead simulate in `O(n)` complexity by recursively checking each grain's underneath
18//! neighbors until we have a conclusive result then propagating that back up the stack,
19//! for example:
20//!
21//! ```none
22//!     #?#    #?#    #?#    #?#    #?#    #?#    #?#    #o#
23//!     # #    #?#    #?#    #?#    #?#    #?#    #o#    #o#
24//!     # # => # # => #?# => #?# => #?# => #o# => #o# => #o#
25//!     # #    # #    # #    #?#    #o#    #o#    #o#    #o#
26//!     ###    ###    ###    ###    ###    ###    ###    ###
27//! ```
28//!
29//! We model the cave as a grid in the possible states:
30//! * `Air` Empty blocks, treated as unknown status when checking underneath neighbors.
31//! * `Falling` Grains of sand that will continue to fall continuously forever.
32//! * `Stopped` Both original rock walls and any grains of sand that have come to rest.
33use crate::util::parse::*;
34use Kind::*;
35
36#[derive(Clone, Copy, PartialEq, Eq)]
37enum Kind {
38    Air,
39    Falling,
40    Stopped,
41}
42
43#[derive(Clone)]
44pub struct Cave {
45    width: usize,
46    height: usize,
47    kind: Vec<Kind>,
48}
49
50/// Creates a 2D grid cave exactly the maximum possible size.
51pub fn parse(input: &str) -> Cave {
52    let points: Vec<Vec<usize>> =
53        input.lines().map(|line| line.iter_unsigned().collect()).collect();
54    let max_y = points.iter().flat_map(|row| row.iter().skip(1).step_by(2)).max().unwrap();
55
56    // Floor is 2 below the bottommost wall.
57    let height = max_y + 2;
58    // Allow enough horizontal room to spread out.
59    let width = 2 * height + 1;
60
61    // Draw each of the walls.
62    let mut kind = vec![Air; width * height];
63
64    for row in points {
65        for &[x1, y1, x2, y2] in row.array_windows().step_by(2) {
66            if x1 == x2 {
67                for y in y1.min(y2)..=y1.max(y2) {
68                    kind[width * y + x1 + height - 500] = Stopped;
69                }
70            } else {
71                for x in x1.min(x2)..=x1.max(x2) {
72                    kind[width * y1 + x + height - 500] = Stopped;
73                }
74            }
75        }
76    }
77
78    Cave { width, height, kind }
79}
80
81/// If a grain of sand reaches the floor it will fall forever.
82pub fn part1(input: &Cave) -> u32 {
83    simulate(input, Falling)
84}
85
86/// The floor is solid rock.
87pub fn part2(input: &Cave) -> u32 {
88    simulate(input, Stopped)
89}
90
91fn simulate(input: &Cave, floor: Kind) -> u32 {
92    let Cave { width, height, mut kind } = input.clone();
93    let mut count = 0;
94
95    // Height is also the x coordinate of the central starting location for grains.
96    let mut todo = Vec::with_capacity(1_000);
97    todo.push(height);
98
99    'outer: while let Some(index) = todo.pop() {
100        // Check in order: center, left then right
101        for next in [index + width, index + width - 1, index + width + 1] {
102            // If we've reached the "floor" then return that.
103            let tile = if next >= kind.len() { floor } else { kind[next] };
104
105            match tile {
106                // If we're unknown then check underneath neighbors first then re-check this tile.
107                Air => {
108                    todo.push(index);
109                    todo.push(next);
110                    continue 'outer;
111                }
112                // Any falling tile underneath means that this tile is also falling.
113                Falling => {
114                    kind[index] = Falling;
115                    continue 'outer;
116                }
117                Stopped => (),
118            }
119        }
120
121        // If all 3 tiles underneath are stopped then this tile is also stopped.
122        kind[index] = Stopped;
123        count += 1;
124    }
125
126    count
127}
aoc/year2022/day14.rs

aoc/year2022/
day14.rs
