/// Represents a hill on the map. Wraps the hill height and indicates
/// if it's a start, end, or just plain old hill.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
enum Hill {
    Start(u8),
    End(u8),
    Hill(u8),
}

/// Convert characters to `Hill`s
impl From<char> for Hill {
    fn from(value: char) -> Self {
        match value {
            'S' => Hill::Start(0),
            'E' => Hill::End(25),
            c if c.is_ascii_lowercase() => Hill::Hill(value as u8 - b'a'),
            _ => unreachable!(),
        }
    }
}

impl Hill {
    // Pull the height from a hill
    fn height(&self) -> u8 {
        match self {
            Hill::Start(h) => *h,
            Hill::End(h) => *h,
            Hill::Hill(h) => *h,
        }
    }

    // Indicate whether the `other` hill can be reached from the
    // current hill, considering elevation only.
    fn can_reach(&self, other: &Hill) -> bool {
        // From the current hill, we can reach hills that are at most one
        // elevation level above the hill we're on.
        other.height().saturating_sub(self.height()) <= 1
    }
}

// Type alias we'll use to refer to hills that can be reached from the current hill
type Neighbors = [Option<(usize, usize)>; 4];

/// Represents a map of all the hills in the area. Includes the two-dimensional
/// listing of hills, the positions of the starting hill and the end hill, and
/// a hashmap that will serve as an adjacency list for hills and the neighbors
/// that can be reached from them.
struct HillMap {
    hills: Vec<Vec<Hill>>,
    graph: HashMap<(usize, usize), Neighbors>,
    start_at: (usize, usize),
    end_at: (usize, usize),
}

/// Convert the input string into a `HillMap`.
impl From<&str> for HillMap {
    fn from(value: &str) -> Self {
        // Start by building up the 2D vector of hills, in the same shape as the
        // characters in the input.
        let hills: Vec<Vec<_>> = value
            .lines()
            .map(|row| row.chars().map(Hill::from).collect())
            .collect();

        // Now we convert the vector of hills into a mapping we can use for a
        // nice graph algorithm (more easily). We'll precompute which neighbors
        // are reachable here to save processing later.
        let mut graph = HashMap::new();

        // Make sure we know the dimensions of the grid
        let last_row = hills.len().saturating_sub(1);
        let last_col = hills
            .first()
            .map(|r| r.len())
            .unwrap_or_default()
            .saturating_sub(1);

        // Prepare to identify the start and end locations
        let mut start_at = (0, 0);
        let mut end_at = (0, 0);

        // For each row and column in our vector of hills...
        for (row_idx, row) in hills.iter().enumerate() {
            for (col_idx, hill) in row.iter().enumerate() {
                // Create and fill in the array of neighbors in order of direction
                // from up, left, down, and right. I'm using arrays here because I
                // believe in my heart that arrays are more efficient that vectors,
                // and I won't be convinced otherwise! (today) We're doing our
                // bounds checking here as well, just to save on possible edge cases
                // later on.
                let mut neighbors = [None; 4];
                if row_idx > 0 && hill.can_reach(&hills[row_idx - 1][col_idx]) {
                    neighbors[0] = Some((row_idx - 1, col_idx));
                }
                if col_idx > 0 && hill.can_reach(&hills[row_idx][col_idx - 1]) {
                    neighbors[1] = Some((row_idx, col_idx - 1));
                }
                if row_idx < last_row && hill.can_reach(&hills[row_idx + 1][col_idx]) {
                    neighbors[2] = Some((row_idx + 1, col_idx));
                }
                if col_idx < last_col && hill.can_reach(&hills[row_idx][col_idx + 1]) {
                    neighbors[3] = Some((row_idx, col_idx + 1));
                }

                // When we encounter the start and end hills, we mark those as special.
                if let Hill::Start(_) = hill {
                    start_at = (row_idx, col_idx);
                }
                if let Hill::End(_) = hill {
                    end_at = (row_idx, col_idx);
                }
                graph.insert((row_idx, col_idx), neighbors);
            }
        }

        // All done!
        HillMap {
            hills,
            graph,
            start_at,
            end_at,
        }
    }
}

const INPUT: &str = include_str!("../../input/12/input.txt");

/// Parse that input!
fn read() -> HillMap {
    HillMap::from(INPUT)
}

use core::cmp::Reverse;
use std::collections::{BinaryHeap, HashMap};

/// Solve Day 12, Part 1
fn solve(input: &HillMap) -> u32 {
    // Starting at the start hill, count the number of steps to the end hill
    // with an implementation of Dijkstra's algorithm.
    let start_at = input.start_at;
    input.shortest_path_to_summit(start_at).unwrap()
}

impl HillMap {
    /// Dijkstra's Algorithm!!!
    fn shortest_path_to_summit(&self, start_at: (usize, usize)) -> Option<u32> {
        // The 'open set': the hills we know how to travel to, but don't
        // know how to travel _from_ yet. You can think of this like the expanding
        // outer edge of our search space, if that helps. Because it's a binary
        // heap (we're using as a _min_ binary heap), the next hill to be fetched
        // will always be the one with the shortest travel time found so far.
        let mut open = BinaryHeap::from([(Reverse(0), start_at)]);

        // Maintain a listing of the shortest number of steps to each hill we've
        // traveled to. It's the shortest number of steps _so far_, it's possible
        // to update these if a shorter path is found.
        let mut steps = HashMap::from([(start_at, 0)]);

        // So long as there are hills left to climb...
        while let Some((_, pos)) = open.pop() {
            // Check the hill we're currently on. If it's the end, then just return
            // the number of steps it took us to get here.
            let (row, col) = pos;
            if pos == self.end_at {
                return steps.get(&pos).copied();
            }

            // Otherwise, see if this hill has any neighbors we can reach. If not,
            // skip it and move on to the next hill in our 'open set'.
            let Some(neighbors) = self.graph.get(&pos) else { continue; };

            // For each direction where there might be a neighbor...
            for maybe_neighbor in neighbors {
                // If there's no reachable neighbor, try the next direction.
                let Some(neighbor) = maybe_neighbor else { continue; };

                // Otherwise, calculate how many steps it will take to get to that
                // neighbor from the path you're currently on. That is, one more step
                // than it took to get to the current hill.
                let next_steps: u32 = steps.get(&pos).unwrap() + 1;

                // Check how many steps are in the current shortest path to that neighbor
                let curr_steps: u32 = *steps.get(neighbor).unwrap_or(&u32::MAX);

                // If we've already found a shorter way to get there, we can just
                // move on.
                if next_steps >= curr_steps {
                    continue;
                }

                // If we're on the shortest path, then add the neighbor to the open
                // set and record the number of steps
                open.push((Reverse(next_steps), *neighbor));
                steps.insert(*neighbor, next_steps);
            }
        }

        None
    }
}

use core::cmp::Reverse;
use std::cmp::min;
use std::collections::{BinaryHeap, HashMap};

/// Solve Day 12, Part 2
fn solve(input: &HillMap) -> u32 {
    // Turns out we need to 'invert' our `HillMap` in order to efficiently find the
    // shortest path to _any_ hill with a height of 0.
    let descent_map = DescentMap::from(input);

    // Get the number of steps from the summit to _every_ single hill in
    // the jungle!
    let steps_to_short_hills = descent_map.shortest_paths_from_summit();

    // Check each hill to see if it's a short hill, and if it is, check to see if
    // it's the shortest path to a short hill found so far. If so, record it!
    let mut shortest_path = u32::MAX;
    for (pos, steps_to_pos) in steps_to_short_hills.iter() {
        let (row, col) = *pos;
        let Hill::Hill(0) = descent_map.hills[row][col] else { continue; };
        shortest_path = min(shortest_path, *steps_to_pos);
    }

    // Return the shortest path to a short hill
    shortest_path
}

// Type alias we'll use here to refer to the hills that can reach the current hill
type Neighbors = [Option<(usize, usize)>; 4];

// Very much like the `HillMap`. The biggest difference is that now `graph` represents
// relationships between hills that can be moved _to_ and the hills that can reach
// them (the reverse of the relationship for `HillMap`).
struct DescentMap {
    hills: Vec<Vec<Hill>>,
    graph: HashMap<(usize, usize), Neighbors>,
    summit: (usize, usize),
}

// Produce a `DescentMap` from a reference to a `HillMap`.
impl From<&HillMap> for DescentMap {
    fn from(hill_map: &HillMap) -> Self {
        // We need to invert the graph, so that we can essentially walk backwards
        // starting from the summit (our previous end point) down to all those
        // short hills.
        let mut graph: HashMap<(usize, usize), Neighbors> = HashMap::new();

        // For each entry in the `HillMap`s graph...
        for (pos, neighbors) in hill_map.graph.iter() {
            // For each neighbor in the entry's list of neighbors (skipping the empty
            // spaces in the neighbor array)
            for neighbor in neighbors.iter().flatten() {
                // Yeah, this is a bit of a gnarly iterator chain. Here's what's going
                // on: We're checking the entry in our inverted `graph` where the
                // neighbor is the key, creating an entry with an empty set of
                // neighbors if the neighbor doesn't have an entry yet. Then, for each
                // slot in the value array for `neighbor`, find the first index that
                // doesn't have a value yet and put `pos` there. This 'inverts' the
                // relationships by making `neighbor` the key and adding `pos` as one
                // of the positions from which `neighbor` can be reached.
                graph
                    .entry(*neighbor)
                    .or_default()
                    .iter_mut()
                    .filter(|slot| slot.is_none())
                    .take(1)
                    .for_each(|slot| *slot = Some(*pos));
            }
        }

        // Copy the `hills` and `end_at` fields from the `HillMap`
        let hills = hill_map.hills.to_vec();
        let summit = hill_map.end_at;

        // Return the new `DescentMap` with the inverted graph.
        DescentMap {
            hills,
            graph,
            summit,
        }
    }
}

impl DescentMap {
    /// Identify and return the minimum number of steps every other hill is from
    /// the summit as a HashMap where the keys are hill positions and the values
    /// are the number of steps from the summit.
    fn shortest_paths_from_summit(&self) -> HashMap<(usize, usize), u32> {
        // The procedure here is the same Dijkstra's algorithm from part one, just
        // walking down from the summit instead of up from the start space.
        let start_at = self.summit;
        let mut open = BinaryHeap::from([(Reverse(0), start_at)]);
        let mut steps = HashMap::from([(start_at, 0)]);

        // While there are still hills to explore...
        while let Some((_, pos)) = open.pop() {
            // No need for an early return here, we want to find a path to _all_ the
            // other hills.

            // As before, we check all the neighbors and any time we're able to
            // reach that neighbor by the shortest path found so far, we add that
            // neighbor to the open set.
            let Some(neighbors) = self.graph.get(&pos) else { continue; };
            for maybe_neighbor in neighbors {
                let Some(neighbor) = maybe_neighbor else { continue; };
                let next_steps: u32 = steps.get(&pos).unwrap() + 1;
                let curr_steps: u32 = *steps.get(neighbor).unwrap_or(&u32::MAX);
                if next_steps >= curr_steps {
                    continue;
                }
                open.push((Reverse(next_steps), *neighbor));
                steps.insert(*neighbor, next_steps);
            }
        }

        // Returns a mapping of the fewest steps to every hill from the summit
        steps
    }
}