Advent Of Code 2021 Day 22 (Rust)

use regex::Regex;
use std::cmp::{max, min, Ordering};
use std::fmt::{Display, Error, Formatter};
use std::fs::File;
use std::hash::{Hash, Hasher};
use std::io::BufRead;
use std::time::Instant;

mod range {
    use super::*;

    #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
    pub enum Range {
        Empty,
        Interval { min: i64, max: i64 },
    }

    impl Range {
        pub fn new(min: i64, max: i64) -> Range {
            if min > max {
                Range::Empty
            } else {
                Range::Interval { min, max }
            }
        }

        pub fn len(&self) -> u64 {
            use Range::*;
            match self {
                Empty => 0,
                Interval {
                    min: self_min,
                    max: self_max,
                } => (self_max - self_min + 1) as u64,
            }
        }

        pub fn inter(&self, other: &Range) -> Range {
            use Range::*;
            match (self, other) {
                (Empty, _) | (_, Empty) => Empty,
                (
                    Interval {
                        min: self_min,
                        max: self_max,
                    },
                    Interval {
                        min: other_min,
                        max: other_max,
                    },
                ) => Range::new(max(*self_min, *other_min), min(*self_max, *other_max)),
            }
        }

        pub fn part1(&self) -> Range {
            self.inter(&Range::new(-50, 50))
        }

        pub fn is_empty(&self) -> bool {
            *self == Range::Empty
        }
    }

    impl PartialOrd for Range {
        fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
            use Ordering::*;
            use Range::*;
            match (self, other) {
                (Empty, Empty) => Some(Equal),
                (Empty, _) => Some(Less),
                (_, Empty) => Some(Greater),
                (
                    Interval {
                        min: self_min,
                        max: self_max,
                    },
                    Interval {
                        min: other_min,
                        max: other_max,
                    },
                ) => match (i64::cmp(self_min, other_min), i64::cmp(self_max, other_max)) {
                    (Equal, Equal) => Some(Equal),
                    (Less | Equal, Greater | Equal) => Some(Greater),
                    (Greater | Equal, Less | Equal) => Some(Less),
                    _ => None,
                },
            }
        }
    }

    impl Display for Range {
        fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
            use Range::*;
            match self {
                Empty => write!(f, "∅"),
                Interval { min, max } => {
                    if min == max {
                        write!(f, "{}", min)
                    } else {
                        write!(f, "{}..{}", min, max)
                    }
                }
            }
        }
    }
}

use range::Range;

mod cuboid {
    use super::*;

    #[derive(Debug, Clone, Copy)]
    pub struct Cuboid {
        pub x: Range,
        pub y: Range,
        pub z: Range,
    }

    impl Cuboid {
        pub fn empty() -> Cuboid {
            Cuboid {
                x: Range::Empty,
                y: Range::Empty,
                z: Range::Empty,
            }
        }

        pub fn is_empty(&self) -> bool {
            self.x.is_empty() || self.y.is_empty() || self.z.is_empty()
        }

        pub fn len(&self) -> u64 {
            self.x.len() * self.y.len() * self.z.len()
        }

        pub fn part1(&self) -> Cuboid {
            Cuboid {
                x: self.x.part1(),
                y: self.y.part1(),
                z: self.z.part1(),
            }
        }

        pub fn inter(&self, other: &Cuboid) -> Cuboid {
            Cuboid {
                x: self.x.inter(&other.x),
                y: self.y.inter(&other.y),
                z: self.z.inter(&other.z),
            }
        }
    }

    impl PartialOrd for Cuboid {
        fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
            use Ordering::*;

            match (
                PartialOrd::partial_cmp(&self.x, &other.x),
                PartialOrd::partial_cmp(&self.y, &other.y),
                PartialOrd::partial_cmp(&self.z, &other.z),
            ) {
                (Some(Equal), Some(Equal), Some(Equal)) => Some(Equal),
                (Some(Less | Equal), Some(Less | Equal), Some(Less | Equal)) => Some(Less),
                (Some(Greater | Equal), Some(Greater | Equal), Some(Greater | Equal)) => {
                    Some(Greater)
                }
                _ => None,
            }
        }
    }

    impl PartialEq for Cuboid {
        fn eq(&self, other: &Self) -> bool {
            self.partial_cmp(other) == Some(Ordering::Equal)
        }
    }

    impl Eq for Cuboid {}

    impl Hash for Cuboid {
        fn hash<H: Hasher>(&self, state: &mut H) {
            if self.is_empty() {
                state.write_u8(0);
            } else {
                self.x.hash(state);
                self.y.hash(state);
                self.y.hash(state);
            }
        }
    }

    impl Display for Cuboid {
        fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
            write!(f, "[x={},y={},z={}]", self.x, self.y, self.z)
        }
    }
}

use cuboid::Cuboid;

mod on_off {
    use super::*;

    /// Stores the Set of cubes that are ON.
    ///
    /// A cube is the set if and only if it is one of the children trees.
    ///
    /// INVARIANT: A cube must be in at most one child true, no more.
    #[derive(Debug, Clone, PartialEq, Eq, Hash)]
    pub struct OnOffForest {
        children: Vec<OnOffTree>,
    }

    impl OnOffForest {
        pub fn new() -> OnOffForest {
            OnOffForest {
                children: Vec::new(),
            }
        }

        pub fn len(&self) -> u64 {
            self.children.iter().map(OnOffTree::len).sum::<u64>()
        }

        pub fn clear(&mut self) {
            self.children.clear();
        }

        pub fn insert(&mut self, c: Cuboid) {
            use Ordering::*;
            if !c.is_empty() {
                // The cuboid to insert is inserted as a child.
                let old_children = std::mem::replace(
                    &mut self.children,
                    vec![OnOffTree {
                        cuboid: c,
                        children: OnOffForest {
                            children: Vec::new(),
                        },
                    }],
                );

                // The cuboid inserted is removed from every
                // pre-existent children.
                for mut child in old_children {
                    match &c.partial_cmp(&child.cuboid) {
                        Some(Equal | Greater) => (),
                        _ => {
                            child.remove(&c);
                            self.children.push(child);
                        }
                    }
                }
            }
        }

        pub fn remove(&mut self, c: &Cuboid) {
            use Ordering::*;
            if !c.is_empty() {
                for mut child in std::mem::replace(&mut self.children, Vec::new()) {
                    match &c.partial_cmp(&child.cuboid) {
                        Some(Equal | Greater) => (),
                        _ => {
                            child.remove(&c);
                            self.children.push(child);
                        }
                    }
                }
            }
        }

        pub fn set(&mut self, c: &Cuboid, b: bool) {
            if b {
                self.insert(*c)
            } else {
                self.remove(c)
            }
        }
    }

    /// Stores the Set of cubes that are ON in a given cuboid.
    ///
    /// A cube is the set if and only if
    ///     - it is in the cuboid
    ///     - no child tree contains this point
    ///
    /// Said differently, the set of points is "cuboid - children"
    ///
    /// INVARIANT:
    ///  - Every child is a sub-region of the tree cuboid.
    #[derive(Debug, Clone, PartialEq, Eq, Hash)]
    struct OnOffTree {
        cuboid: Cuboid,
        children: OnOffForest,
    }

    impl OnOffTree {
        fn len(&self) -> u64 {
            self.cuboid.len() - self.children.len()
        }

        fn remove(&mut self, c: &Cuboid) {
            use Ordering::*;
            let inter = self.cuboid.inter(&c);

            if !inter.is_empty() {
                match inter.partial_cmp(&self.cuboid) {
                    Some(Equal) => {
                        self.cuboid = Cuboid::empty();
                        self.children.clear();
                    }
                    // To remove a sub-cuboid, we insert it as a children.
                    // Because the cubes of a tree are: node cuboids - children.
                    Some(Less) => self.children.insert(inter),
                    x => panic!(
                        "Invalid intersection {:?} of {} and {} = {}",
                        x, self.cuboid, c, inter
                    ),
                }
            }
        }
    }
}

use on_off::OnOffForest;

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Step {
    position: bool,
    cuboid: Cuboid,
}

fn read_input(path: &str) -> Vec<Step> {
    let file = std::io::BufReader::new(File::open(path).unwrap());
    let r =
        Regex::new(r"(off|on) x=(-?\d+)..(-?\d+),y=(-?\d+)..(-?\d+),z=(-?\d+)..(-?\d+)").unwrap();
    let mut v = Vec::<Step>::new();
    for line_r in file.lines() {
        let line = line_r.unwrap();
        let cap = r.captures(&line).unwrap();
        v.push(Step {
            position: &cap[1] == "on",
            cuboid: Cuboid {
                x: Range::new(
                    cap[2].parse::<i64>().unwrap(),
                    cap[3].parse::<i64>().unwrap(),
                ),
                y: Range::new(
                    cap[4].parse::<i64>().unwrap(),
                    cap[5].parse::<i64>().unwrap(),
                ),
                z: Range::new(
                    cap[6].parse::<i64>().unwrap(),
                    cap[7].parse::<i64>().unwrap(),
                ),
            },
        });
    }
    v
}

fn main() {
    let args: Vec<String> = std::env::args().collect();

    let begin = Instant::now();

    let steps = read_input(&args[1]);

    let time_parsing = begin.elapsed();

    // Computing Part 1
    let mut part_1_set = OnOffForest::new();
    for Step { position, cuboid } in &steps {
        part_1_set.set(&cuboid.part1(), *position);
    }
    let result_part_1 = part_1_set.len();

    let end_time_part_1 = begin.elapsed();

    // Computing Part 2
    let mut part_2_set = OnOffForest::new();
    for Step { position, cuboid } in &steps {
        part_2_set.set(cuboid, *position);
    }
    let result_part_2 = part_2_set.len();

    let end_time_part_2 = begin.elapsed();

    println!(
        "Part 1: {} (in {:?})\nPart 2: {} (in {:?})\nTime in parsing: {:?}, total: {:?}",
        result_part_1,
        end_time_part_1 - time_parsing,
        result_part_2,
        end_time_part_2 - end_time_part_1,
        time_parsing,
        end_time_part_2
    );
}