/// --- Part Two ---
///
/// As you walk up the hill, you suspect that the Elves will want to turn this into a hiking
/// trail. The beginning isn't very scenic, though; perhaps you can find a better starting point.
///
/// To maximize exercise while hiking, the trail should start as low as possible: elevation a. The
/// goal is still the square marked E. However, the trail should still be direct, taking the fewest
/// steps to reach its goal. So, you'll need to find the shortest path from any square at elevation
/// a to the square marked E.
///
/// Again consider the example from above:
///
/// ```
/// Sabqponm
/// abcryxxl
/// accszExk
/// acctuvwj
/// abdefghi
/// ```
///
/// Now, there are six choices for starting position (five marked a, plus the square marked S that
/// counts as being at elevation a). If you start at the bottom-left square, you can reach the goal
/// most quickly:
///
/// ```
/// ...v<<<<
/// ...vv<<^
/// ...v>E^^
/// .>v>>>^^
/// >^>>>>>^
/// ```
///
/// This path reaches the goal in only 29 steps, the fewest possible.
///
/// What is the fewest steps required to move starting from any square with elevation a to the
/// location that should get the best signal?
use clap::Parser;
use itertools::Itertools;
use pathfinding::prelude::bfs;

use std::fs::File;
use std::hash::{Hash, Hasher};
use std::io::prelude::*;
use std::io::BufReader;
use std::path::PathBuf;

const FILEPATH: &'static str = "examples/input.txt";

#[derive(Parser, Debug)]
#[clap(author, version, about, long_about = None)]
struct Cli {
    #[clap(short, long, default_value = FILEPATH)]
    file: PathBuf,
}

#[derive(Clone, Debug)]
struct Arena(Vec<Vec<Node>>);

#[derive(Copy, Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
struct Pos(usize, usize);

#[derive(Clone, Debug)]
struct Node {
    pos: Pos,
    value: char,
    connected: Vec<Pos>,
}

impl Node {
    fn new(pos: Pos, value: char) -> Self {
        Node {
            pos,
            value,
            connected: Vec::new(),
        }
    }
}

impl PartialEq for Node {
    fn eq(&self, other: &Self) -> bool {
        self.pos == other.pos
    }
}

impl Eq for Node {}

impl Hash for Node {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.pos.hash(state);
    }
}

impl Arena {
    fn get(&self, coords: Pos) -> &Node {
        &self.0[coords.0][coords.1]
    }

    fn get_mut(&mut self, coords: Pos) -> &mut Node {
        &mut self.0[coords.0][coords.1]
    }
}

fn is_connected(x: char, y: char) -> bool {
    let (x, y) = match (x, y) {
        ('S', _) => ('a', y),
        ('E', _) => ('z', y),
        (_, 'S') => (x, 'a'),
        (_, 'E') => (x, 'z'),
        _ => (x, y),
    };

    let (x, y) = (x as i8, y as i8);
    i8::abs(x - y) <= 1 || x > y
}

fn main() {
    let args = Cli::parse();

    let file = File::open(&args.file).unwrap();
    let reader = BufReader::new(file);

    let mut arena = Arena(Vec::new());
    let _ = reader
        .lines()
        .enumerate()
        .map(|(idx, l)| {
            l.unwrap()
                .chars()
                .enumerate()
                .map(|(idy, c)| Node::new(Pos(idx, idy), c))
                .collect_vec()
        })
        .scan(&mut arena, |arena, row| {
            arena.0.push(row);
            Some(())
        })
        .last();

    let xdim = arena.0.len();
    let ydim = arena.0[0].len();

    let mut lowest_pos = Vec::new();
    let mut end_pos = None;

    for idx in 0..xdim {
        for idy in 0..ydim {
            let node_val = arena.get(Pos(idx, idy)).value;

            match node_val {
                'a' | 'S' => lowest_pos.push(Pos(idx, idy)),
                'E' => end_pos = Some(Pos(idx, idy)),
                _ => (),
            }

            if idx != 0 {
                let up_idx = Pos(idx - 1, idy);
                if is_connected(node_val, arena.get(up_idx).value) {
                    arena.get_mut(Pos(idx, idy)).connected.push(up_idx);
                }
            }

            if idx != xdim - 1 {
                let down_idx = Pos(idx + 1, idy);
                if is_connected(node_val, arena.get(down_idx).value) {
                    arena.get_mut(Pos(idx, idy)).connected.push(down_idx);
                }
            }

            if idy != 0 {
                let left_idx = Pos(idx, idy - 1);
                if is_connected(node_val, arena.get(left_idx).value) {
                    arena.get_mut(Pos(idx, idy)).connected.push(left_idx);
                }
            }

            if idy != ydim - 1 {
                let right_idx = Pos(idx, idy + 1);
                if is_connected(node_val, arena.get(right_idx).value) {
                    arena.get_mut(Pos(idx, idy)).connected.push(right_idx);
                }
            }
        }
    }

    let end = arena.get(end_pos.unwrap());

    let res = lowest_pos
        .into_iter()
        .filter_map(|s| {
            let steps = bfs(
                &arena.get(s),
                |n| n.connected.iter().map(|&p| arena.get(p)),
                |&n| n == end,
            )?
            .len()
                - 1;
            Some(steps)
        })
        .min()
        .unwrap();
    println!("{res}");
}