extern crate advent_of_code_2018;
use advent_of_code_2018::*;

use std::error::Error;
use std::path::PathBuf;

use std::u32;
use std::collections::{HashMap, HashSet};

// cargo watch -cs "cargo run --release --bin day_22"

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
struct Position {
    x: u32,
    y: u32,
    equipment: u32 // 0 = nothing, 1 = torch, 2 = climbing
}

impl Position {
    fn adjacent(&self, map: &Vec<Vec<u32>>) -> Vec<(Position, u32)> {
        let all_adjacent = [
            (Position {
                x: self.x.saturating_sub(1),
                ..*self
            }, 1),
            (Position {
                y: self.y.saturating_sub(1),
                ..*self
            }, 1),
            (Position {
                x: self.x+1,
                ..*self
            }, 1),
            (Position {
                y: self.y+1,
                ..*self
            }, 1),
            (Position {
                equipment: (self.equipment+1)%3,
                ..*self
            }, 7),
            (Position {
                equipment: (self.equipment+2)%3,
                ..*self
            }, 7)
        ];
        all_adjacent.iter()
            .filter(|(p, _)| {
                let region = map[p.y as usize][p.x as usize];
                let out_of_bounds = self == p;
                let invalid_equipment = (region == 0 && p.equipment == 0) ||
                    (region == 1 && p.equipment == 1) ||
                    (region == 2 && p.equipment == 2);
                !out_of_bounds && !invalid_equipment
            })
            .cloned()
            .collect()
    }
}

fn main() -> Result<(), Box<Error>> {
    let input = &read_file(&PathBuf::from("inputs/22.txt"))?;

    let depth: u32 = input[0].trim_matches(|c: char| !c.is_numeric()).parse().unwrap();
    debug!(depth);
    let mut input_target_iter = input[1]
        .split(|c: char| !c.is_numeric())
        .filter(|s| !s.is_empty())
        .map(|s| s.parse::<u32>().unwrap());

    let target_x = input_target_iter.next().unwrap();
    let target_y = input_target_iter.next().unwrap();
    
    debug!((target_x, target_y));

    let mut map_width = target_x;
    let mut map_height = target_y;
    let mut map = build_map(map_width, map_height, depth, target_x, target_y);

    let risk: u32 = map.iter().take((target_y+1) as usize).map(|row| row.iter().take((target_x+1) as usize).sum::<u32>()).sum();
    debug!(risk);


    let mut distances = HashMap::new();
    let mut unexplored = HashSet::new();
    let initial = Position {
        x: 0,
        y: 0,
        equipment: 1
    };
    let target = Position {
        x: target_x,
        y: target_y,
        equipment: 1
    };
    distances.insert(initial, 0);
    unexplored.insert(initial);

    while !distances.contains_key(&target) || unexplored.contains(&target) {
        let (current, current_distance) = unexplored.iter()
            .map(|unexp| (unexp.clone(), distances.get(unexp).cloned().unwrap()))
            .min_by_key(|(_, d)| *d)
            .unwrap();

        if current.y+1 >= map_height {
            map_height *= 2;
            map = build_map(map_width, map_height, depth, target_x, target_y);
            debug!(map_height);
        }
        if current.x+1 >= map_width {
            map_width *= 2;
            map = build_map(map_width, map_height, depth, target_x, target_y);
            debug!(map_width);
        }

        for (adjacent, further) in current.adjacent(&map) {
            let distance = current_distance + further;
            let best_previous_distance = distances.get(&adjacent).cloned().unwrap_or(u32::MAX);
            if best_previous_distance > distance {
                distances.insert(adjacent, distance);
                unexplored.insert(adjacent);
            }
            
        }
        unexplored.remove(&current);
    }

    debug!(distances.get(&target));

    Ok(())
}


fn build_map(max_x: u32, max_y: u32, depth: u32, target_x: u32, target_y: u32) -> Vec<Vec<u32>> {
    let mut geologic_index: Vec<Vec<u32>> = Vec::new();
    let mut erosion_level: Vec<Vec<u32>> = Vec::new();
    let mut region_type: Vec<Vec<u32>> = Vec::new();

    for y in 0..max_y {
        let mut geologic_row = Vec::new();
        let mut erosion_row = Vec::new();
        let mut type_row = Vec::new();
        
        for x in 0..max_x {
            let index = match (x, y) {
                (0, 0) => 0,
                (x, y) if x == target_x && y == target_y => 0,
                (x, 0) => x*16807,
                (0, y) => y*48271,
                (x, y) => erosion_row[(x-1) as usize] * erosion_level[(y-1) as usize][x as usize]
            };
            let erosion = (index + depth) % 20183;
            let block_type = erosion % 3;
            
            geologic_row.push(index);
            erosion_row.push(erosion);
            type_row.push(block_type);
        }

        geologic_index.push(geologic_row);
        erosion_level.push(erosion_row);
        region_type.push(type_row);
    }
    region_type
}