aoc/year2021/
day22.rs

1//! # Reactor Reboot
2//!
3//! The key to solving this problem efficiently is the
4//! [inclusion-exclusion principle](https://en.wikipedia.org/wiki/Inclusion-exclusion_principle).
5//!
6//! Looking at a two-dimensional example:
7//!
8//! ```none
9//!    ┌──────────────┐A            Volume of A: 144
10//!    │              │             Volume of B: 66
11//!    │ ┌─────────┐B │             Volume of C: 18
12//!    │ │         │  │
13//!    │ │ ┌────┐C │  │
14//!    │ │ │    │  │  │
15//!    │ │ └────┘  │  │
16//!    │ └─────────┘  │
17//!    └──────────────┘
18//! ```
19//!
20//! Using the inclusion-exclusion principle the remaining size of A is:
21//!
22//! 144 (initial size) - 66 (overlap with B) - 18 (overlap with C) + 18
23//! (overlap between B and C) = 78
24//!
25//! If there were any triple overlaps we would subtract those, add quadruple, and so on until
26//! there are no more overlaps remaining.
27//!
28//! The complexity of this approach depends on how many cubes overlap. In my input most
29//! cubes overlapped with zero others, a few with one and rarely with more than one.
30use crate::util::iter::*;
31use crate::util::parse::*;
32
33/// Wraps a cube with on/off information.
34pub struct RebootStep {
35    on: bool,
36    cube: Cube,
37}
38
39impl RebootStep {
40    fn from((command, points): (&str, [i32; 6])) -> RebootStep {
41        let on = command == "on";
42        let cube = Cube::from(points);
43        RebootStep { on, cube }
44    }
45}
46
47/// Technically this is actually a [rectangular cuboid](https://en.wikipedia.org/wiki/Cuboid#Rectangular_cuboid)
48/// but that was longer to type!
49#[derive(Clone, Copy)]
50pub struct Cube {
51    x1: i32,
52    x2: i32,
53    y1: i32,
54    y2: i32,
55    z1: i32,
56    z2: i32,
57}
58
59impl Cube {
60    /// Keeping the coordinates in ascending order per axis makes calculating intersections
61    /// and volume easier.
62    fn from(points: [i32; 6]) -> Cube {
63        let [a, b, c, d, e, f] = points;
64        let x1 = a.min(b);
65        let x2 = a.max(b);
66        let y1 = c.min(d);
67        let y2 = c.max(d);
68        let z1 = e.min(f);
69        let z2 = e.max(f);
70        Cube { x1, x2, y1, y2, z1, z2 }
71    }
72
73    /// Returns a `Some` of the intersection if two cubes overlap or `None` if they don't.
74    fn intersect(&self, other: &Cube) -> Option<Cube> {
75        let x1 = self.x1.max(other.x1);
76        let x2 = self.x2.min(other.x2);
77        let y1 = self.y1.max(other.y1);
78        let y2 = self.y2.min(other.y2);
79        let z1 = self.z1.max(other.z1);
80        let z2 = self.z2.min(other.z2);
81        (x1 <= x2 && y1 <= y2 && z1 <= z2).then_some(Cube { x1, x2, y1, y2, z1, z2 })
82    }
83
84    /// Returns the volume of a cube, converting to `i64` to prevent overflow.
85    fn volume(&self) -> i64 {
86        let w = (self.x2 - self.x1 + 1) as i64;
87        let h = (self.y2 - self.y1 + 1) as i64;
88        let d = (self.z2 - self.z1 + 1) as i64;
89        w * h * d
90    }
91}
92
93pub fn parse(input: &str) -> Vec<RebootStep> {
94    let first = input.split_ascii_whitespace().step_by(2);
95    let second = input.iter_signed().chunk::<6>();
96    first.zip(second).map(RebootStep::from).collect()
97}
98
99/// We reuse the logic between part one and two, by first intersecting all cubes with
100/// the specified range. Any cubes that lie completely outside the range will be filtered out.
101pub fn part1(input: &[RebootStep]) -> i64 {
102    let region = Cube { x1: -50, x2: 50, y1: -50, y2: 50, z1: -50, z2: 50 };
103
104    let filtered: Vec<_> = input
105        .iter()
106        .filter_map(|RebootStep { on, cube }| {
107            region.intersect(cube).map(|next| RebootStep { on: *on, cube: next })
108        })
109        .collect();
110
111    part2(&filtered)
112}
113
114pub fn part2(input: &[RebootStep]) -> i64 {
115    let mut total = 0;
116    let mut candidates = Vec::new();
117    // Only "on" cubes contribute to volume.
118    // "off" cubes are considered when subtracting volume.
119    let on_cubes = input.iter().enumerate().filter_map(|(i, rs)| rs.on.then_some((i, rs.cube)));
120
121    for (i, cube) in on_cubes {
122        // Only consider cubes after this one in input order.
123        // Previous cubes have already had all possible intersections subtracted from their
124        // volume, so no longer need to be considered.
125        // We check both "on" and "off" cubes when calculating overlaps to subtract volume.
126        candidates.extend(input[(i + 1)..].iter().filter_map(|rs| cube.intersect(&rs.cube)));
127
128        // Apply the inclusion/exclusion principle recursively, considering overlaps of
129        // increasingly higher order until there are no more overlaps remaining.
130        total += cube.volume() + subsets(&cube, -1, &candidates);
131        candidates.clear();
132    }
133
134    total
135}
136
137// Apply inclusion/exclusion principle. The sign of the result alternates with each level,
138// so that we subtract single overlaps, then add double, subtract triple, and so on...
139fn subsets(cube: &Cube, sign: i64, candidates: &[Cube]) -> i64 {
140    let mut total = 0;
141
142    for (i, other) in candidates.iter().enumerate() {
143        if let Some(next) = cube.intersect(other) {
144            // Subtle nuance here. Similar to the main input we only need to consider higher level
145            // overlaps of inputs *after* this one, as any overlaps with previous cubes
146            // have already been considered.
147            total += sign * next.volume() + subsets(&next, -sign, &candidates[(i + 1)..]);
148        }
149    }
150
151    total
152}
aoc/year2021/day22.rs

aoc/year2021/
day22.rs
