use nalgebra::Point2;
use nom::{
    branch::alt,
    character::complete::{char, line_ending},
    combinator::{map, value},
    multi::{many1, separated_list1},
    IResult,
};
use std::{
    collections::{HashMap, 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;
    let slippery_forked_forest_map = forest_map.build_forked_map(true);
    let dry_forked_forest_map = forest_map.build_forked_map(false);

    dbg!(&slippery_forked_forest_map.longest_end_path_length());
    dbg!(&dry_forked_forest_map.longest_end_path_length());

    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>,
}

#[derive(Debug)]
struct ForkedForestMap {
    start: Point2<usize>,
    end: Point2<usize>,
    connections: HashMap<Point2<usize>, Vec<ForkConnection>>,
}

#[derive(Debug)]
struct ForkConnection {
    to: Point2<usize>,
    distance: usize,
}

#[derive(Debug, Clone)]
struct ForkedDecisionNode {
    explored_forks: HashSet<Point2<usize>>,
    current: Point2<usize>,
    current_len: usize,
}

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

    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]
    }

    fn build_forked_map(&self, slippery: bool) -> ForkedForestMap {
        let start = Point2::new(1, 0);
        let end = Point2::new(self.0[0].len() - 2, self.0.len() - 1);
        let mut forks = Vec::new();
        forks.push(start);
        forks.push(end);

        for y in 1..self.0.len() - 1 {
            for x in 1..self.0[y].len() - 1 {
                let p = Point2::new(x, y);
                if self.at(&p) != ForestTile::Wall {
                    let adjacent_count = self.adjacent(&p, &HashSet::new(), false).len();
                    if adjacent_count > 2 {
                        forks.push(p);
                    }
                }
            }
        }

        let mut connections = HashMap::new();

        for start_point in &forks {
            let mut active_nodes = vec![DecisionNode {
                explored: HashSet::new(),
                current: start_point.clone(),
            }];
            active_nodes[0].explored.insert(start_point.clone());

            let mut fork_connections = Vec::new();

            while let Some(node) = active_nodes.pop() {
                for adjacent in self.adjacent(&node.current, &node.explored, slippery) {
                    let mut new_node = node.clone();
                    new_node.explored.insert(adjacent);
                    new_node.current = adjacent;

                    if forks.contains(&new_node.current) {
                        fork_connections.push(ForkConnection {
                            to: new_node.current,
                            distance: new_node.path_length(),
                        });
                    } else {
                        active_nodes.push(new_node);
                    }
                }
            }

            connections.insert(start_point.clone(), fork_connections);
        }

        ForkedForestMap {
            start,
            end,
            connections,
        }
    }
}

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
    }
}

impl ForkedForestMap {
    fn longest_end_path_length(&self) -> usize {
        let mut active_nodes = vec![ForkedDecisionNode {
            explored_forks: HashSet::new(),
            current: self.start,
            current_len: 0,
        }];
        active_nodes[0].explored_forks.insert(self.start);
        let mut longest_end_path_length: Option<usize> = None;

        while let Some(node) = active_nodes.pop() {
            for adjacent in self.connections.get(&node.current).unwrap() {
                if !node.explored_forks.contains(&adjacent.to) {
                    let mut new_node = node.clone();
                    new_node.explored_forks.insert(adjacent.to);
                    new_node.current = adjacent.to;
                    new_node.current_len += adjacent.distance;

                    if new_node.current == self.end {
                        longest_end_path_length =
                            if let Some(current_longest) = longest_end_path_length {
                                Some(current_longest.max(new_node.current_len))
                            } else {
                                Some(new_node.current_len)
                            };
                    } else {
                        active_nodes.push(new_node);
                    }
                }
            }
        }

        longest_end_path_length.unwrap()
    }
}