use nalgebra::Point2;
use nom::{
    branch::alt,
    character::complete::{char, line_ending},
    combinator::{map, value},
    multi::{many1, separated_list1},
    IResult,
};
use std::{collections::HashSet, fs};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let input = fs::read_to_string("inputs/day_23.txt")?;
    let forest_map = ForestMap::parser(&input).unwrap().1;
    dbg!(forest_map.longest_end_path_length(true));
    dbg!(forest_map.longest_end_path_length(false));

    Ok(())
}

#[derive(Debug)]
struct ForestMap(Vec<Vec<ForestTile>>);

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum ForestTile {
    Wall,
    Open,
    SlopeUp,
    SlopeDown,
    SlopeLeft,
    SlopeRight,
}

#[derive(Debug, Clone)]
struct DecisionNode {
    explored: HashSet<Point2<usize>>,
    current: Point2<usize>,
}

impl ForestMap {
    fn parser(input: &str) -> IResult<&str, Self> {
        map(
            separated_list1(line_ending, many1(ForestTile::parser)),
            ForestMap,
        )(input)
    }

    fn find_end_paths(&self, slippery: bool) -> Vec<DecisionNode> {
        let start_point = Point2::new(1, 0);
        let end_point = Point2::new(self.0[0].len() - 2, self.0.len() - 1);

        let mut active_nodes = vec![DecisionNode {
            explored: HashSet::new(),
            current: start_point,
        }];
        active_nodes[0].explored.insert(start_point);
        let mut end_nodes = Vec::new();

        while let Some(node) = active_nodes.pop() {
            let all_adjacent = self.adjacent(&node.current, &node.explored, slippery);
            if all_adjacent.len() == 1 {
                let adjacent = all_adjacent[0];
                let mut new_node = node;
                new_node.explored.insert(adjacent);
                new_node.current = adjacent;

                if new_node.current == end_point {
                    end_nodes.push(new_node);
                } else {
                    active_nodes.push(new_node);
                }
            } else {
                for adjacent in all_adjacent {
                    let mut new_node = node.clone();
                    new_node.explored.insert(adjacent);
                    new_node.current = adjacent;

                    if new_node.current == end_point {
                        end_nodes.push(new_node);
                    } else {
                        active_nodes.push(new_node);
                    }
                }
            }
        }

        end_nodes
    }

    fn longest_end_path_length(&self, slippery: bool) -> usize {
        self.find_end_paths(slippery)
            .into_iter()
            .map(|path| path.path_length())
            .max()
            .unwrap()
    }

    fn adjacent(
        &self,
        p: &Point2<usize>,
        not_these: &HashSet<Point2<usize>>,
        slippery: bool,
    ) -> Vec<Point2<usize>> {
        let mut adjacent = Vec::with_capacity(4);
        let tile = self.at(p);

        if p.x > 0 && (!slippery || matches!(tile, ForestTile::Open | ForestTile::SlopeLeft)) {
            adjacent.push(Point2::new(p.x - 1, p.y));
        }
        if p.y > 0 && (!slippery || matches!(tile, ForestTile::Open | ForestTile::SlopeUp)) {
            adjacent.push(Point2::new(p.x, p.y - 1));
        }
        if p.x < self.0[p.y].len() - 1
            && (!slippery || matches!(tile, ForestTile::Open | ForestTile::SlopeRight))
        {
            adjacent.push(Point2::new(p.x + 1, p.y));
        }
        if p.y < self.0.len() - 1
            && (!slippery || matches!(tile, ForestTile::Open | ForestTile::SlopeDown))
        {
            adjacent.push(Point2::new(p.x, p.y + 1));
        }

        adjacent.retain(|adj_p| self.at(adj_p) != ForestTile::Wall && !not_these.contains(adj_p));
        adjacent
    }

    fn at(&self, p: &Point2<usize>) -> ForestTile {
        self.0[p.y][p.x]
    }
}

impl ForestTile {
    fn parser(input: &str) -> IResult<&str, Self> {
        alt((
            value(ForestTile::Wall, char('#')),
            value(ForestTile::Open, char('.')),
            value(ForestTile::SlopeUp, char('^')),
            value(ForestTile::SlopeDown, char('v')),
            value(ForestTile::SlopeLeft, char('<')),
            value(ForestTile::SlopeRight, char('>')),
        ))(input)
    }
}

impl DecisionNode {
    fn path_length(&self) -> usize {
        self.explored.len() - 1
    }
}