1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

//! # Reservoir Research
//!
//! Starting from the spring, recursively works out the kind of each tile, memoizing values for
//! efficiency. Tiles are one of 3 kinds:
//!
//! * `Sand` Indicates a tile of unknown type.
//! * `Moving` Flowing water.
//! * `Stopped` Either clay tile or water that has settled.
//!
//! This problem is similar to [Year 2022 Day 14].
//!
//! [Year 2022 Day 14]: crate::year2022::day14
use crate::util::iter::*;
use crate::util::parse::*;
use Kind::*;

#[derive(Clone, Copy, PartialEq, Eq)]
enum Kind {
    Sand,
    Moving,
    Stopped,
}

pub struct Scan {
    width: usize,
    top: usize,
    bottom: usize,
    kind: Vec<Kind>,
    moving: usize,
    stopped: usize,
}

pub fn parse(input: &str) -> Scan {
    let first = input.lines().map(|line| line.as_bytes()[0]);
    let second = input.iter_unsigned::<usize>().chunk::<3>();
    let clay: Vec<_> = first.zip(second).collect();

    // Find boundaries of the 2D scan.
    let mut min_x = usize::MAX;
    let mut max_x = 0;
    let mut min_y = usize::MAX;
    let mut max_y = 0;

    for &(direction, triple) in &clay {
        let (x1, x2, y1, y2) = if direction == b'x' {
            let [x, y1, y2] = triple;
            (x, x, y1, y2)
        } else {
            let [y, x1, x2] = triple;
            (x1, x2, y, y)
        };

        min_x = min_x.min(x1);
        max_x = max_x.max(x2);
        min_y = min_y.min(y1);
        max_y = max_y.max(y2);
    }

    // Leave room for water on either side.
    let width = max_x - min_x + 3;
    let top = width * min_y;
    let bottom = width * (max_y + 1);
    let mut kind = vec![Sand; bottom];

    // Draw each of the clay veins.
    for (direction, triple) in clay {
        if direction == b'x' {
            let [x, y1, y2] = triple;
            for y in y1..y2 + 1 {
                kind[(width * y) + (x - min_x + 1)] = Stopped;
            }
        } else {
            let [y, x1, x2] = triple;
            for x in x1..x2 + 1 {
                kind[(width * y) + (x - min_x + 1)] = Stopped;
            }
        }
    }

    let mut scan = Scan { width, top, bottom, kind, moving: 0, stopped: 0 };
    flow(&mut scan, 500 - min_x + 1);
    scan
}

pub fn part1(input: &Scan) -> usize {
    input.moving + input.stopped
}

pub fn part2(input: &Scan) -> usize {
    input.stopped
}

/// Recursively work out the kind of each tile, memoizing values for efficiency.
fn flow(scan: &mut Scan, index: usize) -> Kind {
    if index >= scan.bottom {
        // Water has gone past the lowest clay tiles, so will fall for infinity.
        Moving
    } else if scan.kind[index] != Sand {
        // Return memoized value.
        scan.kind[index]
    } else if flow(scan, index + scan.width) == Moving {
        // Tile underneath is moving, so this tile must be moving too.
        scan.kind[index] = Moving;
        if index >= scan.top {
            scan.moving += 1;
        }
        Moving
    } else {
        // Tile is stopped (either clay or still water) so water flows both left and right.
        let mut left = index;
        let mut right = index;

        while scan.kind[left - 1] == Sand && flow(scan, left + scan.width) == Stopped {
            left -= 1;
        }

        while scan.kind[right + 1] == Sand && flow(scan, right + scan.width) == Stopped {
            right += 1;
        }

        if scan.kind[left - 1] == Stopped && scan.kind[right + 1] == Stopped {
            for index in left..right + 1 {
                scan.kind[index] = Stopped;
            }
            if index >= scan.top {
                scan.stopped += right + 1 - left;
            }
            Stopped
        } else {
            for index in left..right + 1 {
                scan.kind[index] = Moving;
            }
            if index >= scan.top {
                scan.moving += right + 1 - left;
            }
            Moving
        }
    }
}