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 check 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 continously 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 unsigned = |line: &str| line.iter_unsigned().collect();
53    let points: Vec<Vec<usize>> = input.lines().map(unsigned).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 window in row.windows(4).step_by(2) {
66            if let &[x1, y1, x2, y2] = window {
67                if x1 == x2 {
68                    for y in y1.min(y2)..=y1.max(y2) {
69                        kind[width * y + x1 + height - 500] = Stopped;
70                    }
71                } else {
72                    for x in x1.min(x2)..=x1.max(x2) {
73                        kind[width * y1 + x + height - 500] = Stopped;
74                    }
75                }
76            }
77        }
78    }
79
80    Cave { width, height, kind }
81}
82
83/// If a grain of sand reaches the floor it will fall forever.
84pub fn part1(input: &Cave) -> u32 {
85    simulate(input, Falling)
86}
87
88/// The floor is solid rock.
89pub fn part2(input: &Cave) -> u32 {
90    simulate(input, Stopped)
91}
92
93fn simulate(input: &Cave, floor: Kind) -> u32 {
94    let Cave { width, height, mut kind } = input.clone();
95    let mut count = 0;
96
97    // Height is also the x coordinate of the central starting location for grains.
98    let mut todo = Vec::with_capacity(1_000);
99    todo.push(height);
100
101    'outer: while let Some(index) = todo.pop() {
102        // Check in order: center, left then right
103        for next in [index + width, index + width - 1, index + width + 1] {
104            // If we've reached the "floor" then return that.
105            let tile = if next >= kind.len() { floor } else { kind[next] };
106
107            match tile {
108                // If we're unknown then check underneath neighbors first then re-check this tile.
109                Air => {
110                    todo.push(index);
111                    todo.push(next);
112                    continue 'outer;
113                }
114                // Any falling tile underneath means that this tile is also falling.
115                Falling => {
116                    kind[index] = Falling;
117                    continue 'outer;
118                }
119                Stopped => (),
120            }
121        }
122
123        // If all 3 tiles underneath are stopped then this tile is also stopped.
124        kind[index] = Stopped;
125        count += 1;
126    }
127
128    count
129}
aoc/year2022/day14.rs

aoc/year2022/
day14.rs
