use nom::{
    bytes::complete::tag,
    character::complete::{i32, line_ending},
    combinator::map,
    multi::separated_list1,
    sequence::tuple,
    IResult,
};
use std::{collections::BTreeSet, fs};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let input = fs::read_to_string("inputs/day_18.txt")?;
    let voxels = Voxels::parser(&input).unwrap().1;
    dbg!(voxels.naive_surface_area());
    dbg!(voxels.exterior_surface_area());

    Ok(())
}

#[derive(Debug, Clone)]
struct Voxels(BTreeSet<Point3d>);

#[derive(Debug, Default, Clone, PartialEq, Eq, PartialOrd, Ord)]
struct Point3d {
    x: i32,
    y: i32,
    z: i32,
}

impl Voxels {
    fn parser(input: &str) -> IResult<&str, Self> {
        map(separated_list1(line_ending, Point3d::parser), |vox| {
            Voxels(vox.into_iter().collect())
        })(input)
    }

    fn naive_surface_area(&self) -> usize {
        let units = Point3d::units();
        self.0
            .iter()
            .flat_map(|v| units.iter().map(move |u| v + u))
            .filter(|v| !self.0.contains(v))
            .count()
    }

    fn exterior_surface_area(&self) -> usize {
        let units = Point3d::units();
        let mut known_internal: BTreeSet<Point3d> = BTreeSet::new();
        let known_external = self.bounds();

        self.0
            .iter()
            .flat_map(|v| units.iter().map(move |u| v + u))
            .filter(|v| !self.0.contains(v))
            .filter(|v| {
                if known_internal.contains(v) {
                    return false;
                }

                let mut flooded: BTreeSet<Point3d> = BTreeSet::new();
                let mut frontier: BTreeSet<Point3d> = BTreeSet::new();
                flooded.insert(v.clone());
                frontier.insert(v.clone());
                let mut is_internal = true;
                while is_internal && frontier.len() > 0 {
                    let mut next_frontier = BTreeSet::new();
                    for front in &frontier {
                        for unit in &units {
                            let adjacent = front + unit;
                            if !self.0.contains(&adjacent) && !flooded.contains(&adjacent) {
                                if known_external.contains(&adjacent) {
                                    is_internal = false;
                                }
                                flooded.insert(adjacent.clone());
                                next_frontier.insert(adjacent);
                            }
                        }
                    }
                    frontier = next_frontier;
                }
                if is_internal {
                    known_internal.append(&mut flooded);
                }

                !is_internal
            })
            .count()
    }

    fn bounds(&self) -> BTreeSet<Point3d> {
        let min_x = self.0.iter().map(|v| v.x).min().unwrap_or(0) - 1;
        let max_x = self.0.iter().map(|v| v.x).max().unwrap_or(0) + 1;
        let min_y = self.0.iter().map(|v| v.y).min().unwrap_or(0) - 1;
        let max_y = self.0.iter().map(|v| v.y).max().unwrap_or(0) + 1;
        let min_z = self.0.iter().map(|v| v.z).min().unwrap_or(0) - 1;
        let max_z = self.0.iter().map(|v| v.z).max().unwrap_or(0) + 1;

        let mut result = BTreeSet::new();
        for x in [min_x, max_x] {
            for y in [min_y, max_y] {
                for z in [min_z, max_z] {
                    result.insert(Point3d { x, y, z });
                }
            }
        }
        result
    }
}

impl Point3d {
    fn parser(input: &str) -> IResult<&str, Self> {
        map(
            tuple((i32, tag(","), i32, tag(","), i32)),
            |(x, _, y, _, z)| Point3d { x, y, z },
        )(input)
    }

    fn units() -> Vec<Point3d> {
        vec![
            Point3d {
                x: -1,
                ..Point3d::default()
            },
            Point3d {
                x: 1,
                ..Point3d::default()
            },
            Point3d {
                y: -1,
                ..Point3d::default()
            },
            Point3d {
                y: 1,
                ..Point3d::default()
            },
            Point3d {
                z: -1,
                ..Point3d::default()
            },
            Point3d {
                z: 1,
                ..Point3d::default()
            },
        ]
    }
}

impl ::core::ops::Add<&Point3d> for &Point3d {
    type Output = Point3d;
    fn add(self, rhs: &Point3d) -> Point3d {
        Point3d {
            x: self.x.add(rhs.x),
            y: self.y.add(rhs.y),
            z: self.z.add(rhs.z),
        }
    }
}