use std::cmp::Ordering;
use std::collections::BinaryHeap;
use std::collections::HashMap;
use std::collections::HashSet;
use std::error::Error;
use std::fs::File;
use std::io::{self, BufRead};
use std::vec::Vec;

fn get_risk(x: i32, y: i32, map: &Vec<Vec<u32>>) -> Option<u32> {
    let tw = map[0].len() as i32;
    let th = map.len() as i32;
    let mw = tw * 5;
    let mh = th * 5;

    if y >= 0 && y < mh as i32 && x >= 0 && x < mw as i32 {
        let tile_x = x / tw;
        let tile_y = y / th;
        let mx = x % tw;
        let my = y % th;

        let mut risk = map[my as usize][mx as usize] + tile_x as u32 + tile_y as u32;
        while risk > 9 {
            risk -= 9;
        }

        Some(risk)
    } else {
        None
    }
}

#[derive(Copy, Clone, Eq, PartialEq, Debug)]
struct Point {
    risk: u32,
    x: i32,
    y: i32,
}

impl Ord for Point {
    fn cmp(&self, other: &Self) -> Ordering {
        other
            .risk
            .cmp(&self.risk)
            .then_with(|| self.x.cmp(&other.x))
            .then_with(|| self.y.cmp(&other.y))
    }
}

// `PartialOrd` needs to be implemented as well.
impl PartialOrd for Point {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

fn do_the_dijkstra(
    start_x: i32,
    start_y: i32,
    target_x: i32,
    target_y: i32,
    map: &Vec<Vec<u32>>,
) -> u32 {
    let mut unexplored: HashSet<(i32, i32)> = HashSet::new();

    let mut path_risk: HashMap<(i32, i32), u32> = HashMap::new();
    path_risk.insert((start_x, start_y), 0);

    let mut heap: BinaryHeap<Point> = BinaryHeap::new();
    heap.push(Point {
        x: start_x,
        y: start_y,
        risk: 0,
    });

    for x in 0..target_x + 1 {
        for y in 0..target_y + 1 {
            unexplored.insert((x as i32, y as i32));
        }
    }

    while !unexplored.is_empty() {
        let point = heap.pop().unwrap();

        let cur_node = (point.x, point.y);
        let cur_risk = point.risk;

        if cur_risk > path_risk[&cur_node] {
            continue;
        }

        println!("{:?} {}", cur_node, unexplored.len());

        unexplored.remove(&cur_node);

        if cur_node.0 == target_x && cur_node.1 == target_y {
            println!("Found my target!");
            return cur_risk;
        }

        for (dx, dy) in [(1, 0), (0, 1), (-1, 0), (0, -1)] {
            let neighboor = (cur_node.0 + dx, cur_node.1 + dy);
            if let Some(enter_risk) = get_risk(neighboor.0, neighboor.1, &map) {
                let alt_risk = path_risk[&cur_node] + enter_risk;
                if !path_risk.contains_key(&neighboor) {
                    path_risk.insert(neighboor, alt_risk);
                    heap.push(Point {
                        x: neighboor.0,
                        y: neighboor.1,
                        risk: alt_risk,
                    });
                } else if alt_risk < path_risk[&neighboor] {
                    path_risk.insert(neighboor, alt_risk);
                    heap.push(Point {
                        x: neighboor.0,
                        y: neighboor.1,
                        risk: alt_risk,
                    });
                }
            }
        }
    }

    return 0;
}

fn main() -> Result<(), Box<dyn Error>> {
    let file = File::open("inputs/day15.txt")?;
    let map: Vec<Vec<u32>> = io::BufReader::new(file)
        .lines()
        .map(|l| {
            l.unwrap()
                .chars()
                .map(|c| c.to_string().parse().unwrap())
                .collect()
        })
        .collect();

    let target_x = map[0].len() as i32 - 1;
    let target_y = map.len() as i32 - 1;

    let answer1 = do_the_dijkstra(0, 0, target_x, target_y, &map);

    let target2_x = (map[0].len() * 5) as i32 - 1;
    let target2_y = (map.len() * 5) as i32 - 1;

    let answer2 = do_the_dijkstra(0, 0, target2_x, target2_y, &map);

    println!("Answer1: {}", answer1);

    println!("Answer2: {}", answer2);

    Ok(())
}