use nom::{
    character::complete::{line_ending, satisfy},
    combinator::map,
    multi::{many1, separated_list1},
    IResult,
};
use std::{
    collections::{BTreeMap, BTreeSet},
    fs,
};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let input = fs::read_to_string("inputs/day_12.txt")?;
    let map = HeightMap::parser(&input).unwrap().1;

    let distance_map = MapExploration::explore(&map);

    dbg!(distance_map.distance_to.get(&map.start));

    let min_distance_start = map
        .heights
        .iter()
        .enumerate()
        .flat_map(|(y, row)| {
            row.iter()
                .enumerate()
                .filter(|(_x, height)| **height == 0)
                .map(move |(x, _)| Point { x, y })
        })
        .filter_map(|p| distance_map.distance_to.get(&p))
        .min();
    dbg!(min_distance_start);

    Ok(())
}

#[derive(Debug, Clone)]
struct HeightMap {
    heights: Vec<Vec<u8>>,
    start: Point,
    end: Point,
}

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

impl HeightMap {
    fn parser(input: &str) -> IResult<&str, Self> {
        map(
            separated_list1(line_ending, many1(satisfy(|c| c.is_ascii_alphabetic()))),
            |height_chars| {
                let mut start = Point::default();
                let mut end = Point::default();
                let mut heights = Vec::new();
                for y in 0..height_chars.len() {
                    let mut new_row = Vec::new();
                    for x in 0..height_chars[y].len() {
                        let height = match height_chars[y][x] {
                            'S' => {
                                start = Point { x, y };
                                0
                            }
                            'E' => {
                                end = Point { x, y };
                                25
                            }
                            a if a.is_ascii_lowercase() => height_chars[y][x] as u8 - b'a',
                            a => panic!("Unexpected character {}", a),
                        };
                        new_row.push(height);
                    }
                    heights.push(new_row);
                }

                HeightMap {
                    heights,
                    start,
                    end,
                }
            },
        )(input)
    }

    fn adjacent_to(&self, p: &Point) -> Vec<Point> {
        let current_height = self
            .heights
            .get(p.y)
            .and_then(|row| row.get(p.x))
            .cloned()
            .unwrap_or(0);

        p.adjacent()
            .into_iter()
            .filter(|other_p| {
                let other_height = self
                    .heights
                    .get(other_p.y)
                    .and_then(|row| row.get(other_p.x));

                match other_height {
                    None => false,
                    Some(&other_height) => other_height + 1 >= current_height,
                }
            })
            .collect()
    }
}

impl Point {
    fn adjacent(&self) -> Vec<Point> {
        let mut result = Vec::new();
        if self.x > 0 {
            result.push(Point {
                x: self.x - 1,
                y: self.y,
            });
        }
        if self.x < usize::MAX {
            result.push(Point {
                x: self.x + 1,
                y: self.y,
            });
        }
        if self.y > 0 {
            result.push(Point {
                x: self.x,
                y: self.y - 1,
            });
        }
        if self.y < usize::MAX {
            result.push(Point {
                x: self.x,
                y: self.y + 1,
            });
        }
        result
    }
}

struct MapExploration {
    distance_to: BTreeMap<Point, u32>,
}

impl MapExploration {
    fn explore(map: &HeightMap) -> MapExploration {
        let mut frontier = BTreeSet::new();
        let mut distance_to = BTreeMap::new();
        let mut distance = 0;

        distance_to.insert(map.end.clone(), distance);
        frontier.insert(map.end.clone());

        while !frontier.is_empty() {
            let mut next_frontier = BTreeSet::new();
            distance += 1;

            for frontier_point in frontier {
                for adjacent_point in map.adjacent_to(&frontier_point) {
                    if !distance_to.contains_key(&adjacent_point) {
                        distance_to.insert(adjacent_point.clone(), distance);
                        next_frontier.insert(adjacent_point);
                    }
                }
            }

            frontier = next_frontier;
        }

        MapExploration { distance_to }
    }
}