use itertools::Itertools;
use std::cmp::Ordering;
use std::collections::HashSet;
use std::ops::{Add, AddAssign};

/// Represents a point on the 2D grid where the rocks are
#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, Hash)]
struct Point(u32, u32);

/// An offset to a point, used to adjust `Point`s
#[derive(Debug, Default, Clone, Copy)]
struct Offset(i32, i32);

impl Point {
    /// Calculate the unit offset from one `Point` to another. This represents
    /// the incremental step that, if taken repeatedly, will take you from
    /// `other` to `self`.
    fn offset_from(&self, other: &Self) -> Offset {
        let Point(x1, y1) = self;
        let Point(x2, y2) = other;
        match (x1.cmp(x2), y1.cmp(y2)) {
            (Ordering::Less, Ordering::Less) => Offset(-1, -1),
            (Ordering::Less, Ordering::Equal) => Offset(-1, 0),
            (Ordering::Less, Ordering::Greater) => Offset(-1, 1),
            (Ordering::Equal, Ordering::Less) => Offset(0, -1),
            (Ordering::Equal, Ordering::Equal) => Offset(0, 0),
            (Ordering::Equal, Ordering::Greater) => Offset(0, 1),
            (Ordering::Greater, Ordering::Less) => Offset(1, -1),
            (Ordering::Greater, Ordering::Equal) => Offset(1, 0),
            (Ordering::Greater, Ordering::Greater) => Offset(1, 1),
        }
    }
}

/// Implementation to allow adding an `Offset` to a `Point` to
/// move the `Point` in 2D space.
impl Add<Offset> for Point {
    type Output = Point;

    fn add(self, rhs: Offset) -> Self::Output {
        let Point(px, py) = self;
        let Offset(ox, oy) = rhs;
        let x = px.saturating_add_signed(ox);
        let y = py.saturating_add_signed(oy);
        Point(x, y)
    }
}

/// Module wrapping the input parser to parse lines from the input.
mod parser {
    use super::*;
    use anyhow::{anyhow, Result};
    use nom::{
        bytes::complete::tag,
        character::complete::{newline, u32},
        multi::separated_list1,
        sequence::separated_pair,
        Finish, IResult,
    };

    /// Nom parser for "15,30" -> Point(15, 30)
    fn point(s: &str) -> IResult<&str, Point> {
        let (s, (first, second)) = separated_pair(u32, tag(","), u32)(s)?;
        Ok((s, Point(first, second)))
    }

    /// Nom parser to convert a list like
    /// "15,30 -> 15,45" -> [Point(15, 30), Point(15, 45)]
    fn point_list(s: &str) -> IResult<&str, Vec<Point>> {
        separated_list1(tag(" -> "), point)(s)
    }

    /// Nom parser to convert all lines to a list of lists of `Point`s
    fn point_lists(s: &str) -> IResult<&str, Vec<Vec<Point>>> {
        separated_list1(newline, point_list)(s)
    }

    /// Parse the input file into a list of lists of `Point`s
    pub fn parse(s: &str) -> Result<Vec<Vec<Point>>> {
        let (_, result) = point_lists(s).finish().map_err(|e| anyhow!("{e}"))?;
        Ok(result)
    }
}

/// A struct to house everything we need to iterate one space on the 2D grid
/// at a time to follow a line of rocks, given by a start and end `Point`.
/// We'll use this iterator to produce all the `Point`s containing rocks
/// between `start` and `end`.
struct RockLineIter {
    start: Point,        // The point where the rock line starts
    end: Point,          // The point where the rock line ends
    offset: Offset,      // The incremental change from `start` to `end`
    next: Option<Point>, // The next item to return from this iterator
}

/// A trait for a pair of points to implement to produce a list of rocky points
/// in the line from one point to another.
trait RockLine {
    fn rock_line(self) -> RockLineIter;
}

/// Take a pair of points and return a `RockLineIter`.
impl RockLine for (Point, Point) {
    fn rock_line(self) -> RockLineIter {
        let (start, end) = self;
        let offset = end.offset_from(&start);
        RockLineIter {
            start,
            end,
            offset,
            next: Some(start), // The first point returned is the start
        }
    }
}

/// Let `RockLineIter` be used for iteration! Produces all the points containing
/// rocks from `start` to `end`.
impl Iterator for RockLineIter {
    type Item = Point;

    fn next(&mut self) -> Option<Self::Item> {
        match self.next {
            None => None, // This is how we know when `RockLineIter` is empty
            Some(current) => {
                // If we're currently on the end point, then we've emptied the
                // iterator. Otherwise, the next point returned will be the
                // current point plus the offset.
                self.next = if current == self.end {
                    None
                } else {
                    Some(current + self.offset)
                };

                Some(current)
            }
        }
    }
}

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

/// Parse the input!
pub fn read() -> HashSet<Point> {
    // List of lists of `Point`s, basically the input file
    let point_lists = parser::parse(INPUT).unwrap();

    // The set of points that contain obstacles (rocks)
    let mut obstacles = HashSet::new();

    // For each list of `Point`s...
    for point_list in point_lists {
        // For each pair of points in that list...
        for point_pair in point_list.into_iter().tuple_windows::<(_, _)>() {
            // For each "rocky" point in the line of rocks...
            for rock_point in point_pair.rock_line() {
                // Add that rock point to the set of obstacles
                obstacles.insert(rock_point);
            }
        }
    }

    // Return our set of points that sand can't cross
    obstacles
}

use std::collections::HashSet;

/// Solve Day 14, Part 1
fn solve(input: &HashSet<Point>) -> u32 {
    // Turn that set of impassable points into a `CaveMap`
    let mut cave_map = CaveMap::new(input.clone());

    // We'll drop up to 10K grains of sand. This is overkill, but I'd rather
    // use a `for` loop here instead of a `loop`. Mostly so I have the grain
    // number in the loop without maintaining a separate variable and mutating
    // it each loop.
    for grains in 1..10_000 {
        // When we find the first grain of sand that falls into the infinite
        // abyss, we stop and return the current grain count minus one as
        // the number of grains _before_ this poor soul was lost to the void.
        if let GrainStatus::LostToTheAbyss = cave_map.add_sand() {
            return (grains - 1);
        }
    }

    // If we ever get here, something has gone horribly wrong
    unreachable!()
}

/// This enum represents the status of a grain of sand flowing down from the
/// ceiling. May represent the result of a single step or the entire flow of
/// that grain from start to finish.
#[derive(Debug)]
enum GrainStatus {
    MovedTo(Point),
    StoppedAt(Point),
    LostToTheAbyss,
}

/// Represents the map of our cave. We're keeping up with a set of the points in
/// space that sand can't flow through in `obstacles`, the point where the sand
/// enters the map in `entrypoint`, and the y-index of the lowest point containing
/// rock in `depth`. Past that is the timeless void.
#[derive(Debug, Clone)]
struct CaveMap {
    obstacles: HashSet<Point>,
    entrypoint: Point,
    depth: u32,
}

impl CaveMap {
    /// Create a new `CaveMap` from a set of points representing impassable points
    /// in the cave (for sand).
    fn new(obstacles: HashSet<Point>) -> Self {
        // Find the lowest y-coordinate for any rock
        let depth = obstacles
            .iter()
            .map(|point| point.1)
            .max()
            .unwrap_or_default();

        // Could have been a constant...
        let entrypoint = Point(500, 0);

        CaveMap {
            obstacles,
            entrypoint,
            depth,
        }
    }

    /// Add one grain of sand to the map and follow it as it flows down. Returns
    /// the final status of the grain.
    fn add_sand(&mut self) -> GrainStatus {
        let mut sand = self.entrypoint; // Sand flows in from here

        // Infinite loop!!! It'll stop eventually (we hope).
        loop {
            // Try to flow the grain of sand down one step
            let sand_flow = self.try_move_sand(sand);

            // Do different things depending on what happened when the grain of sand
            // attempted to move down one step.
            match sand_flow {
                // If the grain moved to a new point, update the grain and keep going
                GrainStatus::MovedTo(point) => sand = point,

                // If the grain stopped moving, add it as an obstacle to the cave
                // and break the loop, returning this final status of the grain.
                GrainStatus::StoppedAt(point) => {
                    self.obstacles.insert(point);
                    break sand_flow;
                }

                // If the grain of sand is now tumbling through the dark, slowly
                // forgetting what the sun looks like, break the loop and return
                // this depressing (for the grain of sand) result.
                GrainStatus::LostToTheAbyss => break sand_flow,
            }
        }
    }

    /// Try to move a grain of sand from it's current position downwards.
    fn try_move_sand(&self, sand: Point) -> GrainStatus {
        // A grain of sand can try to move down, down-left, and down-right, in
        // that order.
        let offsets = [Offset(0, 1), Offset(-1, 1), Offset(1, 1)];

        // Try each step in order...
        for offset in offsets {
            // The position that we want the grain of sand to take
            let try_pos = sand + offset;

            // If there's an obstacle there, then try moving another direction
            if self.obstacles.contains(&try_pos) {
                continue;
            }

            // If we're at the y-coordinate representing the depth, then we know
            // there is no hope for the grain of sand and it will spin down into
            // darkness. Return this status.
            if sand.1 >= self.depth {
                return GrainStatus::LostToTheAbyss;
            }

            // If the grain were able to move to the new position, return that result.
            return GrainStatus::MovedTo(try_pos);
        }

        // If all three directions were tried and failed, this grain can go no
        // further. Return that status.
        GrainStatus::StoppedAt(sand)
    }
}

use std::collections::{HashSet, VecDeque};

/// Solve Day 14, Part 2
fn solve(input: &Input) -> Output {
    // Turn that set of impassable points into a `CaveMap`
    let cave_map = CaveMap::new(input.clone());

    // Now turn that `CaveMap` into a `FillMap` to determine how
    // much sand it takes to fill the pile.
    let mut fill_map = FillMap::from(cave_map);

    // Pour sand into the cave until it fills up to the entrypoint
    // and report the number of grains it took to do so.
    fill_map.sand_capacity().into()
}

/// A slight variation on the `CaveMap`. Mostly using a new struct for different
/// behaviors more than different data types.
#[derive(Debug, Clone)]
struct FillMap {
    obstacles: HashSet<Point>,
    entrypoint: Point,
    depth: u32,
}

impl FillMap {
    /// Unpack a `CaveMap` into a `FillMap`
    fn from(grid_map: CaveMap) -> Self {
        // Get the attributes from the `CaveMap`
        let CaveMap {
            obstacles,
            entrypoint,
            depth,
        } = grid_map;

        // Adjust the depth to represent the floor. Hey, look, there's that grain of
        // sand we thought was gone forever, breathing a huge sigh of relief. Good
        // for him!
        let depth = depth + 2;

        // Now it's a `FillMap`!
        FillMap {
            obstacles,
            entrypoint,
            depth,
        }
    }

    /// From a given Point, return an array indicating which points a grain of sand
    /// can flow into (e.g., that aren't blocked by an obstacle or the floor).
    fn get_neighbors(&self, point: Point) -> [Option<Point>; 3] {
        // The same three potential moves as the first part
        let offsets = [Offset(0, 1), Offset(-1, 1), Offset(1, 1)];

        // Array to hold the neighbors that can be moved to
        let mut neighbors = [None; 3];

        // For each possible offset...
        for (idx, offset) in offsets.iter().enumerate() {
            // The position we might move to.
            let try_pos = point + *offset;

            // If there's an obstacle there, skip it. Can't move there.
            if self.obstacles.contains(&try_pos) {
                continue;
            }

            // If there's floor there, skip it. Can't move there.
            if try_pos.1 >= self.depth {
                continue;
            }

            // Otherwise, we can move there. Add this point to our neighbors array.
            neighbors[idx] = Some(try_pos);
        }

        // Return the list of neighbors
        neighbors
    }

    /// Calculate the number of sand grains it'll take to fill in the pile and
    /// block off the entrypoint. Using Dijkstra's Algorithm! Nah, just kidding,
    /// it's a breadth-first search.
    fn sand_capacity(&self) -> u32 {
        let mut queue = VecDeque::from([self.entrypoint]);
        let mut visited = HashSet::new();
        let mut counted = 0; // Keep up with the number of grains

        // So long as we've got positions to try moving _from_...
        while let Some(point) = queue.pop_back() {
            // If we've visited this space before, skip it. Been here, done that.
            if visited.contains(&point) {
                continue;
            }
            visited.insert(point); // Mark `point` as visited
            counted += 1; // Count this grain of sand

            // For each reachable neighbor point from the current point
            for neighbor in self.get_neighbors(point).iter().flatten() {
                // If we've visited that point before, skip it.
                if visited.contains(neighbor) {
                    continue;
                }

                // Add that point to the list of points to visit
                queue.push_front(*neighbor);
            }
        }

        counted // Return the number of grains of sand we counted
    }
}