aoclib/
day_22.rs

1use std::cmp;
2use std::fmt::Debug;
3use std::fs;
4
5use hashbrown::HashMap;
6
7type AnyError = Box<dyn std::error::Error>;
8
9#[derive(Debug, Eq, Hash, PartialEq)]
10struct Cuboid {
11    xl: i64,
12    xr: i64,
13    yl: i64,
14    yr: i64,
15    zl: i64,
16    zr: i64,
17}
18
19impl Cuboid {
20    fn new(xl: i64, xr: i64, yl: i64, yr: i64, zl: i64, zr: i64) -> Option<Cuboid> {
21        if xr <= xl || yr <= yl || zr <= zl {
22            return None;
23        }
24        Some(Cuboid {
25            xl,
26            xr,
27            yl,
28            yr,
29            zl,
30            zr,
31        })
32    }
33}
34
35impl Cuboid {
36    fn contains_cuboid(&self, other: &Cuboid) -> bool {
37        self.xl <= other.xl
38            && self.yl <= other.yl
39            && self.zl <= other.zl
40            && other.xr <= self.xr
41            && other.yr <= self.yr
42            && other.zr <= self.zr
43    }
44
45    fn intersection(&self, other: &Cuboid) -> Option<Cuboid> {
46        Cuboid::new(
47            cmp::max(self.xl, other.xl),
48            cmp::min(self.xr, other.xr),
49            cmp::max(self.yl, other.yl),
50            cmp::min(self.yr, other.yr),
51            cmp::max(self.zl, other.zl),
52            cmp::min(self.zr, other.zr),
53        )
54    }
55
56    fn volume(&self) -> i64 {
57        (self.xr - self.xl) * (self.yr - self.yl) * (self.zr - self.zl)
58    }
59}
60
61fn _steps(text: &str) -> Result<Vec<(bool, Cuboid)>, AnyError> {
62    let re = regex::Regex::new(
63        r"(on|off) x=(-?\d+)[.][.](-?\d+),y=(-?\d+)[.][.](-?\d+),z=(-?\d+)[.][.](-?\d+)",
64    )
65    .unwrap();
66    let mut result = Vec::new();
67    for cap in re.captures_iter(text) {
68        let state = match &cap[1] {
69            "on" => true,
70            "off" => false,
71            state => panic!("Unexpected state '{}'", state),
72        };
73        let cuboid = Cuboid::new(
74            cap[2].parse::<i64>()?,
75            cap[3].parse::<i64>()? + 1,
76            cap[4].parse::<i64>()?,
77            cap[5].parse::<i64>()? + 1,
78            cap[6].parse::<i64>()?,
79            cap[7].parse::<i64>()? + 1,
80        )
81        .ok_or_else(|| format!("Not a valid cuboid: {:?}", cap))?;
82        result.push((state, cuboid));
83    }
84    Ok(result)
85}
86
87#[allow(clippy::needless_collect)]
88fn _num_on(steps: Vec<(bool, Cuboid)>) -> i64 {
89    let mut counts: HashMap<Cuboid, i64> = HashMap::new();
90    for (state, new_cuboid) in steps {
91        let changes = counts
92            .iter()
93            .filter_map(|(old_cuboid, old_count)| {
94                old_cuboid
95                    .intersection(&new_cuboid)
96                    .map(|intersection| (intersection, *old_count))
97            })
98            .collect::<Vec<(Cuboid, i64)>>();
99
100        for (intersection, old_count) in changes.into_iter() {
101            *counts.entry(intersection).or_insert(0) -= old_count;
102        }
103
104        if state {
105            *counts.entry(new_cuboid).or_insert(0) += 1;
106        }
107
108        // Make the quadratic runtime somewhat less excruciating
109        counts.retain(|_, v| *v != 0);
110    }
111    counts
112        .into_iter()
113        .map(|(cuboid, count)| cuboid.volume() * count)
114        .sum()
115}
116
117pub fn part_1(input: &str) -> Result<String, Box<dyn std::error::Error>> {
118    let bound = Cuboid::new(-50, 51, -50, 51, -50, 51).unwrap();
119    let steps = _steps(input)?
120        .into_iter()
121        .filter(|(_, cuboid)| bound.contains_cuboid(cuboid))
122        .collect();
123    Ok(format!("{}", _num_on(steps)))
124}
125
126pub fn part_2(input: &str) -> Result<String, Box<dyn std::error::Error>> {
127    let steps = _steps(input)?;
128    Ok(format!("{}", _num_on(steps)))
129}
130
131fn _from_file<F, T>(func: F, stem: &str) -> T
132where
133    F: Fn(&str) -> Result<T, Box<dyn std::error::Error>>,
134{
135    func(&fs::read_to_string(format!("inputs/22/{}.txt", stem)).unwrap()).unwrap()
136}
137
138#[cfg(test)]
139mod tests {
140    use super::*;
141
142    #[test]
143    fn part_1_works_on_example_s() {
144        assert_eq!(_from_file(part_1, "example_s"), "39");
145    }
146
147    #[test]
148    fn part_1_works_on_example_m() {
149        assert_eq!(_from_file(part_1, "example_m"), "590784");
150    }
151
152    #[test]
153    fn part_1_works_on_example_l() {
154        assert_eq!(_from_file(part_1, "example_l"), "474140");
155    }
156
157    #[test]
158    fn part_1_works_on_input() {
159        assert_eq!(_from_file(part_1, "input"), "527915");
160    }
161
162    #[test]
163    fn part_2_works_on_example_l() {
164        assert_eq!(_from_file(part_2, "example_l"), "2758514936282235");
165    }
166
167    #[test]
168    fn part_2_works_on_input() {
169        assert_eq!(_from_file(part_2, "input"), "1218645427221987");
170    }
171}
aoclib/day_22.rs

aoclib/
day_22.rs
