2022 Day 12

use std::env;
use std::io::{self, prelude::*, BufReader};
use std::fs::File;
use std::collections::{HashMap,HashSet};

use std::collections::BinaryHeap;
use std::cmp::Ordering;

use point2d::point2d::Point2D;

fn elevation(ch: char) -> i64 {
    match ch {
        'a'..='z' => { ch as i64 - 96 },
        'S'=> { 1  },
        'E'=> { 26 },
        _ => panic!("Unknown character: {}", ch),
    }
}

#[derive(PartialEq,Eq)]
struct Path {
    pt: Point2D,
    steps: i64,
}
impl Ord for Path {
    fn cmp(&self, other: &Self) -> Ordering {
        other.steps.cmp(&self.steps)
    }
}
impl PartialOrd for Path {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(other.steps.cmp(&self.steps))
    }
}

fn neighbor_addresses(pt: &Point2D) -> Vec<Point2D> {
    vec![Point2D { x: pt.x  , y: pt.y-1 },  // up
         Point2D { x: pt.x+1, y: pt.y   },  // right
         Point2D { x: pt.x  , y: pt.y+1 },  // down
         Point2D { x: pt.x-1, y: pt.y   }]  // left
}

fn shortest_path(map: &HashMap<Point2D,i64>, start: Point2D, end: Point2D) -> i64 {

    // Explore
    let mut visited: HashSet<Point2D> = HashSet::new();
    let mut heap: BinaryHeap<Path> = BinaryHeap::new();
    heap.push(Path{pt: start, steps: 0});
    while heap.len() > 0 {

        let path = heap.pop().unwrap();
        let (now,current_steps) = (path.pt, path.steps);
        let current_elevation = map.get(&now).unwrap();

        'neighbor_loop: for neighbor in neighbor_addresses(&now) {

            // Determine if visitable
            let new_elev = match map.get(&neighbor) {
                Some(e) => e,
                None => { continue 'neighbor_loop; }, // off the map
            };
            if new_elev > &(current_elevation + 1) { continue 'neighbor_loop; }

            // Check already visited
            if visited.get(&neighbor).is_some() { continue 'neighbor_loop; }
            visited.insert(neighbor);

            // New steps
            let new_steps = current_steps + 1;

            // Found the end
            if neighbor == end { return new_steps; }
            heap.push(Path{pt: neighbor, steps: new_steps});
        }
    }
    i64::MAX
}

fn solve(input: &str) -> io::Result<()> {
    let file = File::open(input).expect("Input file not found.");
    let reader = BufReader::new(file);

    // Input
    let input: Vec<String> = match reader.lines().collect() {
        Err(err) => panic!("Unknown error reading input: {}", err),
        Ok(result) => result,
    };

    // Build map
    let mut elev_map: HashMap<Point2D,i64> = HashMap::new();
    let mut start = Point2D {x: 0, y: 0 };
    let mut end = Point2D {x: 0, y: 0 };
    let mut possible_starts: Vec<Point2D> = Vec::new();
    for (y,line) in input.iter().enumerate() {
        for (x,elev_ch) in line.chars().enumerate() {
            let pt = Point2D { x: x as i64, y: y as i64 };
            elev_map.insert(pt, elevation(elev_ch));
            // Identify start and end points
            match elev_ch {
                'a' => possible_starts.push(pt),
                'S' => start = pt,
                'E' => end   = pt,
                _ => {},
            }
        }
    }

    // Part 1
    let part1 = shortest_path(&elev_map.clone(), start, end);
    println!("Part 1: {part1}"); // 380

    // Part 2
    let best = possible_starts.iter().map(|s| shortest_path(&elev_map,*s,end)).min().unwrap();
    println!("Part 2: {best}"); // 375

    Ok(())
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    solve(&filename).unwrap();
}