/// Represents a 1x1x1 cube in 3D space
#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, Hash)]
struct Cube(i32, i32, i32);

// Just some convenience functions for working with Cubes
impl Cube {
    fn new(x: i32, y: i32, z: i32) -> Self {
        Cube(x, y, z)
    }

    fn inner(&self) -> (i32, i32, i32) {
        let Cube(x, y, z) = self;
        (*x, *y, *z)
    }
}

/// Convert a tuple of i32s into a Cube
impl From<(i32, i32, i32)> for Cube {
    fn from(value: (i32, i32, i32)) -> Self {
        let (x, y, z) = value;
        Cube(x, y, z)
    }
}

/// Module wrapping the parsing functions for today's puzzle input
mod parser {
    use super::*;
    use anyhow::{anyhow, Result};
    use nom::{
        branch::alt,
        bytes::complete::tag,
        character::complete::{i32, newline},
        combinator::map,
        multi::separated_list0,
        sequence::{terminated, tuple},
        Finish, IResult,
    };
    use std::collections::HashSet;

    /// Nom parser for ("5," || "5") -> 5i32
    fn number(s: &str) -> IResult<&str, i32> {
        alt((terminated(i32, tag(",")), i32))(s)
    }

    /// Nom parser for "1,2,3" -> (1, 2, 3)
    fn coordinates(s: &str) -> IResult<&str, (i32, i32, i32)> {
        // Using tuple instead of separated_list1 here because I want
        // to avoid allocating the Vec
        tuple((number, number, number))(s)
    }

    /// Nom parser for "1,2,3" -> Cube(1, 2, 3)
    fn cube(s: &str) -> IResult<&str, Cube> {
        map(coordinates, Cube::from)(s)
    }

    /// Parses a list of input lines into a list of Cubes
    fn cubes(s: &str) -> IResult<&str, Vec<Cube>> {
        separated_list0(newline, cube)(s)
    }

    /// Parses the input file into a HashSet of Cubes
    pub fn parse(s: &str) -> Result<HashSet<Cube>> {
        let (_, result) = cubes(s).finish().map_err(|e| anyhow!("{e}"))?;
        Ok(result.into_iter().collect::<HashSet<_>>())
    }
}

const INPUT: &str = include_str!("../../input/18/input.txt");

/// Parse that input!
fn read() -> HashSet<Cube> {
    parser::parse(INPUT).unwrap()
}

use std::collections::HashSet;
use std::ops::Add;

/// Solve Day 18, Part 1
fn solve(input: &HashSet<Cube>) -> u32 {
    let mut surface_area = 0;

    // For each cube in the input, look at each cube that shares
    // a face with it. For every one of those neighboring cubes that
    // is not lava, add one to the total surface area.
    for cube in input.iter() {
        for neighbor in cube.neighbors() {
            if !input.contains(&neighbor) {
                surface_area += 1;
            }
        }
    }

    surface_area
}

/// Represents an offset used to adjust a Cube location
#[derive(Debug, Clone, Copy)]
struct Offset(i32, i32, i32);

impl Offset {
    /// All the offsets of interest. Provides the offsets that will result
    /// in a Cube that shares a face with an existing Cube.
    const fn all() -> [Offset; 6] {
        [
            Offset(-1, 0, 0),
            Offset(1, 0, 0),
            Offset(0, -1, 0),
            Offset(0, 1, 0),
            Offset(0, 0, -1),
            Offset(0, 0, 1),
        ]
    }

    /// Convenience!
    fn new(x: i32, y: i32, z: i32) -> Self {
        Offset(x, y, z)
    }

    /// Convenience!
    fn inner(&self) -> (i32, i32, i32) {
        let Offset(x, y, z) = self;
        (*x, *y, *z)
    }
}

/// Allows for adding an Offset to a Cube to get a Cube offset from the original
impl Add<Offset> for Cube {
    type Output = Cube;

    fn add(self, offset: Offset) -> Self::Output {
        let (cx, cy, cz) = self.inner();
        let (ox, oy, oz) = offset.inner();
        let x = cx + ox;
        let y = cy + oy;
        let z = cz + oz;

        Cube::new(x, y, z)
    }
}

impl Cube {
    /// Get all the neighboring Cubes that share a face with this one.
    fn neighbors(&self) -> [Cube; 6] {
        let mut cubes = [Cube::default(); 6];
        let offsets = Offset::all();
        for (slot, offset) in cubes.iter_mut().zip(offsets.iter()) {
            *slot = *self + *offset;
        }
        cubes
    }
}

use std::collections::HashSet;
use std::ops::RangeInclusive;

/// Solve Day 18, Part 2
fn solve(input: &HashSet<Cube>) -> u32 {
    // Identify the bounding box that contains all the Cubes for the lava
    // plus at least one extra in each dimension.
    let bounds = input.get_bounds();

    // Adding up surface area, like before
    let mut surface_area = 0;

    // Prepare for a Depth-First Search through all the Cubes that are within
    // the bounding box but that _aren't_ lava. Each "air" cube that touches
    // a lava cube adds one to the total observed surface area.
    let mut stack = Vec::with_capacity(input.len() * 2);
    let mut seen = HashSet::with_capacity(input.len() * 2);

    // This isn't technically a corner of the bounding box or anything, but
    // I checked my input and there isn't any lava at this location. It really
    // doesn't matter _where_ you start the search, so long as it's a Cube
    // outside the lava blob.
    let start = Cube::new(0, 0, 0);
    stack.push(start);

    // So long as there are still Cubes outside the lava blob to check...
    while let Some(cube) = stack.pop() {
        // If the cube we're on has already been explored or it falls outside
        // the bounding box, skip it.
        if seen.contains(&cube) || !bounds.contains(&cube) {
            continue;
        }

        // If the cube we're on contains lava, then we add one to our surface area
        // and move on. We don't want to explore the lava-containing cubes.
        if input.contains(&cube) {
            surface_area += 1;
            continue;
        }

        seen.insert(cube);

        // For each cube that shares a face with the current Cube, if we haven't
        // explored it already, add it to the stack for later exploration.
        for neighbor in cube.neighbors() {
            if seen.contains(&neighbor) {
                continue;
            }
            stack.push(neighbor);
        }
    }

    surface_area
}

/// Represents the 3D range that contains all the air Cubes we want to explore,
/// encapsulating the lava Cubes.
struct Bounds(
    RangeInclusive<i32>,
    RangeInclusive<i32>,
    RangeInclusive<i32>,
);

/// This trait provides a convenient way to get the bounding box of
/// a HashSet of Cubes
trait GetBounds {
    fn get_bounds(&self) -> Bounds;
}

impl GetBounds for &HashSet<Cube> {
    /// Nothing fancy here. Identify the minimim and maximum values on each axis
    /// for all the lava-containing cubes, then set the bounding box to be one
    /// greater in each dimension. This leaves a one-wide gap around the lava
    /// blob that is OK to explore.
    fn get_bounds(&self) -> Bounds {
        let (mut min_x, mut max_x) = (0, 0);
        let (mut min_y, mut max_y) = (0, 0);
        let (mut min_z, mut max_z) = (0, 0);

        for cube in self.iter() {
            let (x, y, z) = cube.inner();
            min_x = min_x.min(x);
            max_x = max_x.max(x);
            min_y = min_y.min(y);
            max_y = max_y.max(y);
            min_z = min_z.min(z);
            max_z = max_z.max(z);
        }

        let x_range = (min_x - 1)..=(max_x + 1);
        let y_range = (min_y - 1)..=(max_y + 1);
        let z_range = (min_z - 1)..=(max_z + 1);

        Bounds(x_range, y_range, z_range)
    }
}

impl Bounds {
    /// Indicates whether a Cube lies within the Bounds
    fn contains(&self, cube: &Cube) -> bool {
        let (x, y, z) = cube.inner();
        let Bounds(x_range, y_range, z_range) = self;
        x_range.contains(&x) && y_range.contains(&y) && z_range.contains(&z)
    }
}