use std::{collections::HashMap, hash::Hash, vec};

use advent_of_code::{
    find_character,
    strings::{convert_to_array, line_to_char},
    IntMul, Kartesian, Map, KD,
};
use advent_of_code_macros::include_aoc;

include_aoc!(DATA, 2024, 20);

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
struct Progress {
    step: u32,
    pos: Kartesian<usize>,
}

fn get_uncheated_course(map: &Map<char>) -> Vec<Progress> {
    let mut course = Vec::new();
    let mut position = Progress {
        pos: find_character(&map, 'S'),
        step: 0,
    };
    course.push(position);
    let mut lastdir = KD::Top;
    let mut dir;
    'raceloop: loop {
        dir = lastdir;
        loop {
            let newpos = position.pos.move_dir(dir.vector(), dir).unwrap();
            if course.iter().filter(|x| x.pos == newpos).count() != 0 {
                dir = dir.clockwise(false);
                continue;
            }
            let dest = map.get(newpos).unwrap();
            match dest {
                '.' | 'E' => {
                    position = Progress {
                        pos: newpos,
                        step: position.step + 1,
                    };
                    course.push(position);
                    lastdir = dir;
                    if dest == '.' {
                        break;
                    } else {
                        break 'raceloop;
                    }
                },
                _ => dir = dir.clockwise(false),
            }
        }
    }
    course
}

fn cheat(map: &Map<char>, course: &Vec<Progress>, length: usize) -> Vec<(Kartesian<usize>, Kartesian<usize>)> {
    let mut cheats = Vec::new();
    for i in 0..course.len() {
        let start = course[i];
        loop {

        }
    }
    cheats
}

fn main() {
    let map = Map::from(convert_to_array::<_, _, '\n'>(DATA, line_to_char));
    let course = get_uncheated_course(&map);
    print!("{}", map);
    println!("The uncheated course needs {} Picoseconds", course.last().unwrap().step);
    let mut cheats = Vec::new();
    for i in 0..course.len() - 1 {
        let current = course[i];
        for dir in KD::iter(false, false, true) {
            let wall = current.pos.move_dir(dir.vector(), dir).unwrap();
            if map.get(wall) != Some('#') {
                continue;
            }
            let vector = dir.vector().mul(2_usize);
            let newpos = match current.pos.move_dir_max(vector, dir, map.size()) {
                None => continue,
                Some(x) => x,
            };
            if map.get(newpos) != Some('#') {
                let possible_cheat = course.iter().filter(|x| x.pos == newpos).next().unwrap();
                if possible_cheat.step > current.step {
                    cheats.push((possible_cheat.step - current.step - 2, wall));
                }
            }
        }
    }
    let mut counter = HashMap::new();
    for cheat in cheats.clone() {
        if !counter.contains_key(&cheat.0) {
            counter.insert(cheat.0, 0_u32);
        }
        *counter.get_mut(&cheat.0).unwrap() += 1_u32;
    }
    let mut cs: Vec<_> = counter.iter().collect();
    cs.sort();
    println!("Found {} cheats that save more than 100 picoseconds", cs.iter().filter(|x| *x.0 >= 100).map(|x| *x.1).sum::<u32>());
}

#[cfg(test)]
mod test {
    use super::*;
}