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

aoc/year2021/
day22.rs
