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

aoc/year2021/
day22.rs
