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 call 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::*;
34
35#[derive(Clone, Copy, PartialEq, Eq)]
36enum Kind {
37    Air,
38    Falling,
39    Stopped,
40}
41
42#[derive(Clone)]
43pub struct Cave {
44    width: usize,
45    height: usize,
46    size: usize,
47    kind: Vec<Kind>,
48    floor: Kind,
49    count: u32,
50}
51
52impl Cave {
53    fn fall(&mut self, index: usize) -> Kind {
54        // Check in order: center, left then right
55        let result = self.check(index + self.width)
56            && self.check(index + self.width - 1)
57            && self.check(index + self.width + 1);
58
59        // If all 3 bottom neighbors are stopped then so are we.
60        // Cache the result into the grid then propagate result back up the call stack.
61        if result {
62            self.count += 1;
63            self.kind[index] = Kind::Stopped;
64            Kind::Stopped
65        } else {
66            self.kind[index] = Kind::Falling;
67            Kind::Falling
68        }
69    }
70
71    // Returns `true` if cell is stopped.
72    fn check(&mut self, index: usize) -> bool {
73        let kind = if index >= self.size {
74            // If we've reached the "floor" then return that.
75            self.floor
76        } else if self.kind[index] == Kind::Air {
77            // If we're unknown then recursively check our own underneath neighbors
78            self.fall(index)
79        } else {
80            // Otherwise use the cached value.
81            self.kind[index]
82        };
83        kind == Kind::Stopped
84    }
85}
86
87/// Creates a 2D grid cave exactly the maximum possible size.
88pub fn parse(input: &str) -> Cave {
89    let unsigned = |line: &str| line.iter_unsigned().collect();
90    let points: Vec<Vec<usize>> = input.lines().map(unsigned).collect();
91    let max_y = points.iter().flat_map(|row| row.iter().skip(1).step_by(2)).max().unwrap();
92    // Floor is 2 below the bottommost wall.
93    let height = max_y + 2;
94    // Allow enough horizontal room to spread out.
95    let width = 2 * height + 1;
96    let size = width * height;
97    let mut kind = vec![Kind::Air; size];
98
99    // Draw each of the walls.
100    for row in points {
101        for window in row.windows(4).step_by(2) {
102            if let &[x1, y1, x2, y2] = window {
103                for x in x1.min(x2)..=x1.max(x2) {
104                    for y in y1.min(y2)..=y1.max(y2) {
105                        kind[(width * y) + (x + height - 500)] = Kind::Stopped;
106                    }
107                }
108            }
109        }
110    }
111
112    Cave { width, height, size, kind, floor: Kind::Air, count: 0 }
113}
114
115/// If a grain of sand reaches the floor it will fall forever.
116pub fn part1(input: &Cave) -> u32 {
117    simulate(input, Kind::Falling)
118}
119
120/// The floor is solid rock.
121pub fn part2(input: &Cave) -> u32 {
122    simulate(input, Kind::Stopped)
123}
124
125fn simulate(input: &Cave, floor: Kind) -> u32 {
126    let mut cave = input.clone();
127    cave.floor = floor;
128    // Height is also the x coordinate of the central starting location for grains.
129    cave.fall(cave.height);
130    cave.count
131}
aoc/year2022/day14.rs

aoc/year2022/
day14.rs
