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
37        .zip(second)
38        .map(|(d, [a, b, c])| if d == b'x' { (a, a, b, c) } else { (b, c, a, a) })
39        .collect();
40
41    // Find boundaries of the 2D scan.
42    let min_x = clay.iter().map(|c| c.0).min().unwrap();
43    let max_x = clay.iter().map(|c| c.1).max().unwrap();
44    let min_y = clay.iter().map(|c| c.2).min().unwrap();
45    let max_y = clay.iter().map(|c| c.3).max().unwrap();
46
47    // Leave room for water on either side.
48    let width = max_x - min_x + 3;
49    let top = width * min_y;
50    let bottom = width * (max_y + 1);
51    let mut kind = vec![Sand; bottom];
52
53    // Draw each of the clay veins.
54    for (x1, x2, y1, y2) in clay {
55        if x1 == x2 {
56            for y in y1..y2 + 1 {
57                kind[width * y + x1 - min_x + 1] = Stopped;
58            }
59        } else {
60            for x in x1..x2 + 1 {
61                kind[width * y1 + x - min_x + 1] = Stopped;
62            }
63        }
64    }
65
66    let mut scan = Scan { width, top, bottom, kind, moving: 0, stopped: 0 };
67    flow(&mut scan, 500 - min_x + 1);
68    scan
69}
70
71pub fn part1(input: &Scan) -> usize {
72    input.moving + input.stopped
73}
74
75pub fn part2(input: &Scan) -> usize {
76    input.stopped
77}
78
79/// Recursively work out the kind of each tile, memoizing values for efficiency.
80fn flow(scan: &mut Scan, index: usize) -> Kind {
81    if index >= scan.bottom {
82        // Water has gone past the lowest clay tiles, so will fall for infinity.
83        Moving
84    } else if scan.kind[index] != Sand {
85        // Return memoized value.
86        scan.kind[index]
87    } else if flow(scan, index + scan.width) == Moving {
88        // Tile underneath is moving, so this tile must be moving too.
89        scan.kind[index] = Moving;
90        if index >= scan.top {
91            scan.moving += 1;
92        }
93        Moving
94    } else {
95        // Tile is stopped (either clay or still water) so water flows both left and right.
96        let left = (0..index).rev().find(|&i| !spread(scan, i)).unwrap();
97        let right = (index + 1..scan.bottom).find(|&i| !spread(scan, i)).unwrap();
98
99        if scan.kind[left] == Stopped && scan.kind[right] == Stopped {
100            scan.kind[left + 1..right].fill(Stopped);
101            scan.stopped += right - left - 1;
102            Stopped
103        } else {
104            // Open on one or both sides, continue to flow off the sides.
105            flow(scan, left);
106            flow(scan, right);
107            scan.kind[left + 1..right].fill(Moving);
108            if index >= scan.top {
109                scan.moving += right - left - 1;
110            }
111            Moving
112        }
113    }
114}
115
116/// Check the neighboring horizontal tile first to see if we can keep spreading, then check the
117/// tile underneath. Speed things up by first checking via the middle condition if the tile
118/// is already stopped water or clay.
119fn spread(scan: &mut Scan, index: usize) -> bool {
120    scan.kind[index] == Sand
121        && (scan.kind[index + scan.width] == Stopped || flow(scan, index + scan.width) == Stopped)
122}
aoc/year2018/day17.rs

aoc/year2018/
day17.rs
