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        RebootStep { on: command == "on", cube: Cube::from(points) }
42    }
43}
44
45/// Technically this is actually a [rectangular cuboid](https://en.wikipedia.org/wiki/Cuboid#Rectangular_cuboid)
46/// but that was longer to type!
47#[derive(Clone, Copy)]
48pub struct Cube {
49    x1: i32,
50    x2: i32,
51    y1: i32,
52    y2: i32,
53    z1: i32,
54    z2: i32,
55}
56
57impl Cube {
58    /// Keeping the coordinates in ascending order per axis makes calculating intersections
59    /// and volume easier.
60    fn from(points: [i32; 6]) -> Cube {
61        let [a, b, c, d, e, f] = points;
62        let x1 = a.min(b);
63        let x2 = a.max(b);
64        let y1 = c.min(d);
65        let y2 = c.max(d);
66        let z1 = e.min(f);
67        let z2 = e.max(f);
68        Cube { x1, x2, y1, y2, z1, z2 }
69    }
70
71    /// Returns a `Some` of the intersection if two cubes overlap or `None` if they don't.
72    fn intersect(&self, other: &Cube) -> Option<Cube> {
73        let x1 = self.x1.max(other.x1);
74        let x2 = self.x2.min(other.x2);
75        let y1 = self.y1.max(other.y1);
76        let y2 = self.y2.min(other.y2);
77        let z1 = self.z1.max(other.z1);
78        let z2 = self.z2.min(other.z2);
79        (x1 <= x2 && y1 <= y2 && z1 <= z2).then_some(Cube { x1, x2, y1, y2, z1, z2 })
80    }
81
82    /// Returns the volume of a cube, converting to `i64` to prevent overflow.
83    fn volume(&self) -> i64 {
84        let w = (self.x2 - self.x1 + 1) as i64;
85        let h = (self.y2 - self.y1 + 1) as i64;
86        let d = (self.z2 - self.z1 + 1) as i64;
87        w * h * d
88    }
89}
90
91pub fn parse(input: &str) -> Vec<RebootStep> {
92    let first = input.split_ascii_whitespace().step_by(2);
93    let second = input.iter_signed().chunk::<6>();
94    first.zip(second).map(RebootStep::from).collect()
95}
96
97/// We reuse the logic between part one and two, by first intersecting all cubes with
98/// the specified range. Any cubes that lie completely outside the range will be filtered out.
99pub fn part1(input: &[RebootStep]) -> i64 {
100    let region = Cube { x1: -50, x2: 50, y1: -50, y2: 50, z1: -50, z2: 50 };
101
102    let filtered: Vec<_> = input
103        .iter()
104        .filter_map(|RebootStep { on, cube }| {
105            region.intersect(cube).map(|next| RebootStep { on: *on, cube: next })
106        })
107        .collect();
108
109    part2(&filtered)
110}
111
112pub fn part2(input: &[RebootStep]) -> i64 {
113    let mut total = 0;
114    let mut candidates = Vec::new();
115    // Only "on" cubes contribute to volume.
116    // "off" cubes are considered when subtracting volume.
117    let on_cubes = input.iter().enumerate().filter_map(|(i, rs)| rs.on.then_some((i, rs.cube)));
118
119    for (i, cube) in on_cubes {
120        // Only consider cubes after this one in input order.
121        // Previous cubes have already had all possible intersections subtracted from their
122        // volume, so no longer need to be considered.
123        // We check both "on" and "off" cubes when calculating overlaps to subtract volume.
124        candidates.extend(input[(i + 1)..].iter().filter_map(|rs| cube.intersect(&rs.cube)));
125
126        // Apply the inclusion/exclusion principle recursively, considering overlaps of
127        // increasingly higher order until there are no more overlaps remaining.
128        total += cube.volume() + subsets(&cube, -1, &candidates);
129        candidates.clear();
130    }
131
132    total
133}
134
135// Apply inclusion/exclusion principle. The sign of the result alternates with each level,
136// so that we subtract single overlaps, then add double, subtract triple, and so on...
137fn subsets(cube: &Cube, sign: i64, candidates: &[Cube]) -> i64 {
138    let mut total = 0;
139
140    for (i, other) in candidates.iter().enumerate() {
141        if let Some(next) = cube.intersect(other) {
142            // Subtle nuance here. Similar to the main input we only need to consider higher level
143            // overlaps of inputs *after* this one, as any overlaps with previous cubes
144            // have already been considered.
145            total += sign * next.volume() + subsets(&next, -sign, &candidates[(i + 1)..]);
146        }
147    }
148
149    total
150}
aoc/year2021/day22.rs

aoc/year2021/
day22.rs
