use std::{cmp::Ordering, collections::HashMap, u32};

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

include_aoc!(DATA 2024 16);

const START: Option<char> = Some('S');
const WALL: Option<char> = Some('#');
const END: Option<char> = Some('E');
const SPACE: Option<char> = Some('.');

fn new_score(old_score: u32, old: KD, new: KD) -> u32 {
    old_score
        + if new == old {
            1
        } else if old == new.neg() {
            2001
        } else {
            1001
        }
}

fn sorter(a: &(Kartesian<usize>, KartesianDirection, u32), b: &(Kartesian<usize>, KartesianDirection, u32)) -> Ordering {
    a.2.cmp(&b.2).reverse()
}

fn search_end(map: &Map<char>, startpos: Kartesian<usize>, last_dir: KartesianDirection) -> u32 {
    let mut posmap: HashMap<Kartesian<usize>, u32> = HashMap::new();
    let mut branches = Vec::with_capacity(200);
    branches.push((startpos, last_dir, 0));
    let mut vmap = map.clone();
    let mut best = u32::MAX;
    loop {
        let (newpos, old_dir, score) = match branches.pop() {
            Some(b) => b,
            None => break,
        };
        if !posmap.contains_key(&newpos) {
            posmap.insert(newpos, score);
        } else {
            if score > *posmap.get(&newpos).unwrap() {
                continue;
            }
            posmap.insert(newpos, score);
        }
        println!("moved {} with increased score {}", old_dir, score);
        vmap.set(
            newpos,
            match old_dir {
                KartesianDirection::Left => '←',
                KartesianDirection::Top => '↑',
                KartesianDirection::Right => '→',
                KartesianDirection::Bottom => '↓',
                _ => unreachable!(),
            },
        );
        for dir in KD::iter(false, false, true) {
            let after_move = newpos.move_dir(dir.vector(), dir).unwrap();
            match map.get(after_move) {
                WALL => {},
                END => {
                    if best > new_score(score, old_dir, dir) {
                        best = new_score(score, old_dir, dir);
                    }
                    break;
                },
                SPACE | START => {
                    let added = new_score(score, old_dir, dir);
                    branches.push((after_move, dir, added));
                },
                _ => unreachable!(),
            }
        }
        branches.sort_by(sorter);
    }
    print!("{}", vmap);
    best
}

fn main() {
    let map = Map::from(convert_to_array::<_, _, '\n'>(DATA, line_to_char));
    //println!("Startmap: \n{}", map);
    let deer = find_character(&map, 'S');
    let best = search_end(&map, deer, KartesianDirection::East);
    println!("Best Score is: {}", best)
}

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