Day 24: Blizzard Basin

use std::env;
use std::io::{self, prelude::*, BufReader};
use std::fs::File;
use std::collections::HashSet;
use std::collections::VecDeque;
use std::collections::BinaryHeap;
use std::cmp::Ordering;

use point2d::point2d::Point2D;

#[derive(Debug,Copy,Clone,Hash,Eq,PartialEq)]
struct Blizzard {
    loc: Point2D,
    dir: BlizzardDirection,
}

#[derive(Debug,Copy,Clone,Hash,Eq,PartialEq)]
enum BlizzardDirection {
    Up,
    Down,
    Left,
    Right,
}
impl From<char> for BlizzardDirection {
    fn from(c: char) -> Self {
        match c {
            '^' => Self::Up,
            'v' => Self::Down,
            '<' => Self::Left,
            '>' => Self::Right,
            _ => panic!("Unexpected blizzard direction character: {c}"),
        }
    }
}

#[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(start: &Point2D, waypoints: &VecDeque<Point2D>, xmax: i64, ymax: i64, blizzards: &Vec<Blizzard>) -> i64 {

    // Prepare
    let mut ends = waypoints.clone();
    let mut end = ends.pop_front().unwrap();

    // Explore
    let mut heap: BinaryHeap<Path> = BinaryHeap::new();
    let mut seen: HashSet<(Point2D,i64)> = HashSet::new();
    heap.push(Path {pt: *start, steps: 0});
    'heap_lp: while let Some(path) = heap.pop() {

        // Current properties
        let (pt_now,time_now) = (path.pt,path.steps);

        // Determine future properties
        let new_time = time_now + 1;
        let new_blizzards = blizzards_at_time(&blizzards,new_time,xmax,ymax);

        // Consider waiting on this square IF blizzard will not be here next step
        if new_blizzards.iter().filter(|b| b.loc == pt_now).count() == 0 {
            if seen.insert((pt_now,new_time)) {
                heap.push(Path { pt: pt_now, steps: new_time });
            }
        }

        'n_loop: for n in neighbor_addresses(&pt_now) {

            // Check point is a waypoint, and check for next waypoint
            if n == end {
                if ends.len() > 0 {
                    end = ends.pop_front().unwrap();
                    heap.clear();
                    seen.clear();
                    heap.push(Path {pt: n, steps: new_time });
                    continue 'heap_lp;
                } else {
                    return new_time;
                }
           }

            // Check point is inside the walls
            if n.x <= 0 || n.x > xmax { continue 'n_loop; }
            if n.y <= 0 || n.y > ymax { continue 'n_loop; }

            // Check point will not be an active blizzard
            if new_blizzards.iter().filter(|b| b.loc == n).count() == 0 {
                if seen.insert((n,new_time)) {
                    heap.push(Path { pt: n, steps: new_time });
                }
            }
        }

    }
    i64::MAX
}

fn blizzards_at_time(blizzards: &Vec<Blizzard>, time: i64, xmax: i64, ymax: i64) -> Vec<Blizzard> {
    let mut adj_blizzards = blizzards.clone();
    for mut blizz in &mut adj_blizzards {
        match blizz.dir {
            BlizzardDirection::Up    => { blizz.loc.y = 1 + ((blizz.loc.y - 1 - time).rem_euclid(ymax)); },
            BlizzardDirection::Down  => { blizz.loc.y = 1 + ((blizz.loc.y - 1 + time).rem_euclid(ymax)); },
            BlizzardDirection::Left  => { blizz.loc.x = 1 + ((blizz.loc.x - 1 - time).rem_euclid(xmax)); },
            BlizzardDirection::Right => { blizz.loc.x = 1 + ((blizz.loc.x - 1 + time).rem_euclid(xmax)); },
        }
    }
    adj_blizzards
}

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 blizzard map
    let mut blizzards: Vec<Blizzard> = Vec::new();
    let mut start = Point2D { x: 0, y: 0 };
    let mut end = start;
    for (y,line) in input.iter().enumerate() {
        for (x,ch) in line.chars().enumerate() {
            let pt = Point2D { x: x as i64, y: y as i64 };
            if ch == '.' && y == 0 { start = pt; }
            if ch == '.' && y == input.len()-1 { end = pt; }
            match ch {
                '>' | '<' | '^' | 'v' => blizzards.push(Blizzard { loc: pt, dir: BlizzardDirection::from(ch) }),
                '.' | '#' => {},
                _ => panic!("Unexpected character: {ch}"),
            }
        }
    }
    let (xmax,ymax) = (end.x,end.y-1);

    // Part 1
    let mut waypoints: VecDeque<Point2D> = VecDeque::new();
    waypoints.push_front(end);
    let part1 = shortest_path(&start,&waypoints,xmax,ymax,&blizzards);
    println!("Part 1: {part1}"); // 334

    // Part 2
    let mut waypoints: VecDeque<Point2D> = VecDeque::new();
    waypoints.push_front(end);
    waypoints.push_front(start);
    waypoints.push_front(end);
    let part2 = shortest_path(&start,&waypoints,xmax,ymax,&blizzards);
    println!("Part 2: {part2}"); // 934

    Ok(())
}

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