aoc/year2018/
day17.rs

1//! # Reservoir Research
2//!
3//! Starting from the spring, recursively works out the kind of each tile, memoizing values for
4//! efficiency. Tiles are one of 3 kinds:
5//!
6//! * `Sand` Indicates a tile of unknown type.
7//! * `Moving` Flowing water.
8//! * `Stopped` Either clay tile or water that has settled.
9//!
10//! This problem is similar to [Year 2022 Day 14].
11//!
12//! [Year 2022 Day 14]: crate::year2022::day14
13use crate::util::iter::*;
14use crate::util::parse::*;
15use Kind::*;
16
17#[derive(Clone, Copy, PartialEq, Eq)]
18enum Kind {
19    Sand,
20    Moving,
21    Stopped,
22}
23
24pub struct Scan {
25    width: usize,
26    top: usize,
27    bottom: usize,
28    kind: Vec<Kind>,
29    moving: usize,
30    stopped: usize,
31}
32
33pub fn parse(input: &str) -> Scan {
34    let first = input.lines().map(|line| line.as_bytes()[0]);
35    let second = input.iter_unsigned::<usize>().chunk::<3>();
36    let clay: Vec<_> = first.zip(second).collect();
37
38    // Find boundaries of the 2D scan.
39    let mut min_x = usize::MAX;
40    let mut max_x = 0;
41    let mut min_y = usize::MAX;
42    let mut max_y = 0;
43
44    for &(direction, triple) in &clay {
45        let (x1, x2, y1, y2) = if direction == b'x' {
46            let [x, y1, y2] = triple;
47            (x, x, y1, y2)
48        } else {
49            let [y, x1, x2] = triple;
50            (x1, x2, y, y)
51        };
52
53        min_x = min_x.min(x1);
54        max_x = max_x.max(x2);
55        min_y = min_y.min(y1);
56        max_y = max_y.max(y2);
57    }
58
59    // Leave room for water on either side.
60    let width = max_x - min_x + 3;
61    let top = width * min_y;
62    let bottom = width * (max_y + 1);
63    let mut kind = vec![Sand; bottom];
64
65    // Draw each of the clay veins.
66    for (direction, triple) in clay {
67        if direction == b'x' {
68            let [x, y1, y2] = triple;
69            for y in y1..y2 + 1 {
70                kind[(width * y) + (x - min_x + 1)] = Stopped;
71            }
72        } else {
73            let [y, x1, x2] = triple;
74            for x in x1..x2 + 1 {
75                kind[(width * y) + (x - min_x + 1)] = Stopped;
76            }
77        }
78    }
79
80    let mut scan = Scan { width, top, bottom, kind, moving: 0, stopped: 0 };
81    flow(&mut scan, 500 - min_x + 1);
82    scan
83}
84
85pub fn part1(input: &Scan) -> usize {
86    input.moving + input.stopped
87}
88
89pub fn part2(input: &Scan) -> usize {
90    input.stopped
91}
92
93/// Recursively work out the kind of each tile, memoizing values for efficiency.
94fn flow(scan: &mut Scan, index: usize) -> Kind {
95    if index >= scan.bottom {
96        // Water has gone past the lowest clay tiles, so will fall for infinity.
97        Moving
98    } else if scan.kind[index] != Sand {
99        // Return memoized value.
100        scan.kind[index]
101    } else if flow(scan, index + scan.width) == Moving {
102        // Tile underneath is moving, so this tile must be moving too.
103        scan.kind[index] = Moving;
104        if index >= scan.top {
105            scan.moving += 1;
106        }
107        Moving
108    } else {
109        // Tile is stopped (either clay or still water) so water flows both left and right.
110        let mut left = index;
111        let mut right = index;
112
113        while scan.kind[left - 1] == Sand && flow(scan, left + scan.width) == Stopped {
114            left -= 1;
115        }
116
117        while scan.kind[right + 1] == Sand && flow(scan, right + scan.width) == Stopped {
118            right += 1;
119        }
120
121        if scan.kind[left - 1] == Stopped && scan.kind[right + 1] == Stopped {
122            for index in left..right + 1 {
123                scan.kind[index] = Stopped;
124            }
125            if index >= scan.top {
126                scan.stopped += right + 1 - left;
127            }
128            Stopped
129        } else {
130            for index in left..right + 1 {
131                scan.kind[index] = Moving;
132            }
133            if index >= scan.top {
134                scan.moving += right + 1 - left;
135            }
136            Moving
137        }
138    }
139}
aoc/year2018/day17.rs

aoc/year2018/
day17.rs
