1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154

//! # Reactor Reboot
//!
//! The key to solving this problem efficiently is the
//! [inclusion-exclusion principle ](https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle).
//!
//! Looking at a two dimensional example
//! ```none
//!    ┌──────────────┐A            Volume of A: 144
//!    │              │             Volume of B: 66
//!    │ ┌─────────┐B │             Volume of C: 18
//!    │ │         │  │
//!    │ │ ┌────┐C │  │
//!    │ │ │    │  │  │
//!    │ │ └────┘  │  │
//!    │ └─────────┘  │
//!    └──────────────┘
//! ```
//!
//! Using the inclusion-exclusion principle the remaining size of A is:
//!
//! 144 (initial size) - 66 (overlap with B) - 18 (overlap with C) + 18
//! (overlap between B and C) = 78
//!
//! If there were any triple overlaps we would subtract those, add quadruple, and so on until
//! there are no more overlaps remaining.
//!
//! The complexity of this approach depends on how many cubes overlap. In my input most
//! cubes overlapped with zero others, a few with one and rarely with more than one.
use crate::util::iter::*;
use crate::util::parse::*;

/// Wraps a cube with on/off information.
pub struct RebootStep {
    on: bool,
    cube: Cube,
}

impl RebootStep {
    fn from((command, points): (&str, [i32; 6])) -> RebootStep {
        let on = command == "on";
        let cube = Cube::from(points);
        RebootStep { on, cube }
    }
}

/// Technically this is actually a [rectangular cuboid](https://en.wikipedia.org/wiki/Cuboid#Rectangular_cuboid)
/// but that was longer to type!
#[derive(Clone, Copy)]
pub struct Cube {
    x1: i32,
    x2: i32,
    y1: i32,
    y2: i32,
    z1: i32,
    z2: i32,
}

impl Cube {
    /// Keeping the coordinates in ascending order per axis makes calculating intersections
    /// and volume easier.
    fn from(points: [i32; 6]) -> Cube {
        let [a, b, c, d, e, f] = points;
        let x1 = a.min(b);
        let x2 = a.max(b);
        let y1 = c.min(d);
        let y2 = c.max(d);
        let z1 = e.min(f);
        let z2 = e.max(f);
        Cube { x1, x2, y1, y2, z1, z2 }
    }

    /// Returns a `Some` of the intersection if two cubes overlap or `None` if they don't.
    fn intersect(&self, other: &Cube) -> Option<Cube> {
        let x1 = self.x1.max(other.x1);
        let x2 = self.x2.min(other.x2);
        let y1 = self.y1.max(other.y1);
        let y2 = self.y2.min(other.y2);
        let z1 = self.z1.max(other.z1);
        let z2 = self.z2.min(other.z2);
        (x1 <= x2 && y1 <= y2 && z1 <= z2).then_some(Cube { x1, x2, y1, y2, z1, z2 })
    }

    /// Returns the volume of a cube, converting to `i64` to prevent overflow.
    fn volume(&self) -> i64 {
        let w = (self.x2 - self.x1 + 1) as i64;
        let h = (self.y2 - self.y1 + 1) as i64;
        let d = (self.z2 - self.z1 + 1) as i64;
        w * h * d
    }
}

pub fn parse(input: &str) -> Vec<RebootStep> {
    let first = input.split_ascii_whitespace().step_by(2);
    let second = input.iter_signed().chunk::<6>();
    first.zip(second).map(RebootStep::from).collect()
}

/// We re-use the logic between part one and two, by first intersecting all cubes with
/// the specified range. Any cubes that lie completely outside the range will be filtered out.
pub fn part1(input: &[RebootStep]) -> i64 {
    let region = Cube { x1: -50, x2: 50, y1: -50, y2: 50, z1: -50, z2: 50 };

    let filtered: Vec<_> = input
        .iter()
        .filter_map(|RebootStep { on, cube }| {
            region.intersect(cube).map(|next| RebootStep { on: *on, cube: next })
        })
        .collect();

    part2(&filtered)
}

pub fn part2(input: &[RebootStep]) -> i64 {
    let mut total = 0;
    let mut candidates = Vec::new();
    // Only "on" cubes contribute to volume.
    // "off" cubes are considered when subtracting volume
    let on_cubes = input.iter().enumerate().filter_map(|(i, rs)| rs.on.then_some((i, rs.cube)));

    for (i, cube) in on_cubes {
        // Only consider cubes after this one in input order.
        // Previous cubes have already had all possible intersections subtracted from their
        // volume, so no longer need to be considered.
        // We check both "on" and "off" cubes when calculating overlaps to subtract volume.
        input[(i + 1)..]
            .iter()
            .filter_map(|rs| cube.intersect(&rs.cube))
            .for_each(|next| candidates.push(next));

        // Apply the inclusion/exclusion principle recursively, considering overlaps of
        // increasingly higher order until there are no more overlaps remaining.
        total += cube.volume() + subsets(&cube, -1, &candidates);
        candidates.clear();
    }

    total
}

// Apply inclusion/exclusion principle. The sign of the result alternates with each level,
// so that we subtract single overlaps, then add double, subtract triple, and so on...
fn subsets(cube: &Cube, sign: i64, candidates: &[Cube]) -> i64 {
    let mut total = 0;

    for (i, other) in candidates.iter().enumerate() {
        if let Some(next) = cube.intersect(other) {
            // Subtle nuance here. Similar to the main input we only need to consider higher level
            // overlaps of inputs *after* this one, as any overlaps with previous cubes
            // have already been considered.
            total += sign * next.volume() + subsets(&next, -sign, &candidates[(i + 1)..]);
        }
    }

    total
}