year2018/
day17.rs

1use utils::prelude::*;
2
3/// Simulating water flow in a 2D grid.
4#[derive(Clone, Debug)]
5pub struct Day17 {
6    part1: u32,
7    part2: u32,
8}
9
10#[repr(u8)]
11#[derive(Clone, Copy, Debug, PartialEq)]
12enum State {
13    Empty,
14    Flowing,
15    Filled,
16}
17
18impl Day17 {
19    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
20        let segments = parser::byte_range(b'x'..=b'y')
21            .with_suffix(b'=')
22            .then(parser::number_range(1..=2999).with_suffix(", "))
23            .then(parser::byte_range(b'x'..=b'y').with_suffix(b'='))
24            .then(parser::number_range(1..=2999).with_suffix(".."))
25            .then(parser::number_range(1..=2999))
26            .map_res(|(axis1, c1, axis2, c2, c3)| {
27                if axis1 == axis2 {
28                    Err("expected line segment")
29                } else if c2 > c3 {
30                    Err("expected range to be sorted")
31                } else {
32                    Ok((axis1, c1, c2, c3))
33                }
34            })
35            .parse_lines(input)?;
36
37        let (mut x_min, mut x_max, mut y_min, mut y_max) = (500, 500, usize::MAX, 0);
38        for &(axis, c1, c2, c3) in &segments {
39            if axis == b'x' {
40                x_min = x_min.min(c1);
41                x_max = x_max.max(c1);
42                y_min = y_min.min(c2);
43                y_max = y_max.max(c3);
44            } else {
45                x_min = x_min.min(c2);
46                x_max = x_max.max(c3);
47                y_min = y_min.min(c1);
48                y_max = y_max.max(c1);
49            }
50        }
51
52        // Reserve the top row for the spring
53        y_min -= 1;
54        // Padding to avoid wrapping around rows
55        x_min -= 1;
56        x_max += 1;
57
58        let width = x_max - x_min + 1;
59        let height = y_max - y_min + 1;
60        let mut grid = vec![State::Empty; width * height];
61        for &(axis, c1, c2, c3) in &segments {
62            if axis == b'x' {
63                let x = c1 - x_min;
64                for y in c2 - y_min..=c3 - y_min {
65                    grid[y * width + x] = State::Filled;
66                }
67            } else {
68                let y = c1 - y_min;
69                for x in c2 - x_min..=c3 - x_min {
70                    grid[y * width + x] = State::Filled;
71                }
72            }
73        }
74
75        let mut counts = [0; 3];
76        Self::flow(&mut grid, width, &mut counts, 500 - x_min);
77
78        Ok(Self {
79            part1: counts[State::Filled as usize] + counts[State::Flowing as usize],
80            part2: counts[State::Filled as usize],
81        })
82    }
83
84    fn flow(grid: &mut [State], width: usize, counts: &mut [u32; 3], index: usize) -> State {
85        if index >= grid.len() {
86            return State::Flowing;
87        }
88        if grid[index] != State::Empty {
89            return grid[index];
90        }
91
92        if Self::flow(grid, width, counts, index + width) == State::Flowing {
93            grid[index] = State::Flowing;
94            if index >= width {
95                counts[State::Flowing as usize] += 1;
96            }
97            return State::Flowing;
98        }
99
100        let mut left = index;
101        while grid[left - 1] == State::Empty {
102            left -= 1;
103            if Self::flow(grid, width, counts, left + width) == State::Flowing {
104                break;
105            }
106        }
107
108        let mut right = index;
109        while grid[right + 1] == State::Empty {
110            right += 1;
111            if Self::flow(grid, width, counts, right + width) == State::Flowing {
112                break;
113            }
114        }
115
116        let state = if grid[left - 1] == State::Filled && grid[right + 1] == State::Filled {
117            State::Filled
118        } else {
119            State::Flowing
120        };
121
122        grid[left..=right].fill(state);
123        if index >= width {
124            counts[state as usize] += (right - left + 1) as u32;
125        }
126        state
127    }
128
129    #[must_use]
130    pub fn part1(&self) -> u32 {
131        self.part1
132    }
133
134    #[must_use]
135    pub fn part2(&self) -> u32 {
136        self.part2
137    }
138}
139
140examples!(Day17 -> (u32, u32) [
141    {
142        input: "x=495, y=2..7\n\
143            y=7, x=495..501\n\
144            x=501, y=3..7\n\
145            x=498, y=2..4\n\
146            x=506, y=1..2\n\
147            x=498, y=10..13\n\
148            x=504, y=10..13\n\
149            y=13, x=498..504",
150        part1: 57,
151        part2: 29,
152    },
153]);
year2018/day17.rs

year2018/
day17.rs
