mod utils;
use std::collections::BinaryHeap;

use utils::read_input;

fn main() {
    let input = read_input();

    let width = input.lines().next().unwrap().len();
    let height = input.lines().count();
    let mut heights = vec![0; width * height];

    let mut start = (0, 0);
    let mut end = (0, 0);

    for (y, line) in input.lines().enumerate() {
        for (x, c) in line.chars().enumerate() {
            let val = if c == 'S' {
                start = (x as isize, y as isize);
                0
            } else if c == 'E' {
                end = (x as isize, y as isize);
                25
            } else {
                c.to_ascii_lowercase() as isize - 97
            };
            heights[(y * width) + x] = val;
        }
    }

    let cost = pathfind(&heights, width, end);

    println!("Part 1: {:?}", cost[pos_to_index(&start, width)]);
    println!(
        "Part 2: {:?}",
        (0..height as isize)
            .map(|y| (0..width as isize)
                .map(|x| pos_to_index(&(x, y), width))
                .filter(|idx| heights[*idx] == 0)
                .map(|idx| cost[idx])
                .min()
                .unwrap())
            .min()
            .unwrap()
    )
}

type HeightMap = Vec<isize>;
type Pos = (isize, isize);

fn pathfind(heights: &HeightMap, width: usize, end: Pos) -> Vec<usize> {
    let mut min_cost = vec![usize::MAX; heights.len()];
    let mut frontier: BinaryHeap<GraphPos> = BinaryHeap::new();
    frontier.push(GraphPos { pos: end, moves: 0 });
    while let Some(curr) = frontier.pop() {
        let idx = pos_to_index(&curr.pos, width);
        if curr.moves >= min_cost[idx] {
            continue;
        } else {
            min_cost[idx] = curr.moves;
        }

        for neighbour in CanReach::new(heights, width, curr.pos) {
            frontier.push(GraphPos {
                pos: neighbour,
                moves: curr.moves + 1,
            })
        }
    }

    min_cost
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct GraphPos {
    pos: Pos,
    moves: usize,
}

impl PartialOrd for GraphPos {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        self.moves.partial_cmp(&other.moves).map(|x| x.reverse())
    }
}

impl Ord for GraphPos {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.moves.cmp(&other.moves).reverse()
    }
}

struct CanReach<'a> {
    heights: &'a HeightMap,
    curr: Pos,
    step: usize,
    width: usize,
}

impl<'a> CanReach<'a> {
    fn new(heights: &'a HeightMap, width: usize, pos: Pos) -> Self {
        CanReach {
            heights,
            curr: pos,
            step: 0,
            width,
        }
    }
}
impl Iterator for CanReach<'_> {
    type Item = Pos;

    fn next(&mut self) -> Option<Self::Item> {
        let (curr_x, curr_y) = self.curr;
        loop {
            let (x, y) = match self.step {
                0 => (curr_x + 1, curr_y),
                1 => (curr_x - 1, curr_y),
                2 => (curr_x, curr_y + 1),
                3 => (curr_x, curr_y - 1),
                _ => break,
            };
            self.step += 1;

            if (x >= 0
                && x < self.width as isize
                && y >= 0
                && y < (self.heights.len() / self.width) as isize)
                && self.heights[pos_to_index(&(x, y), self.width)]
                    >= self.heights[pos_to_index(&(curr_x, curr_y), self.width)] - 1
            {
                return Some((x, y));
            }
        }
        None
    }
}

#[inline(always)]
fn pos_to_index(pos: &Pos, width: usize) -> usize {
    ((pos.1 * width as isize) + pos.0) as usize
}