adventofcode/days/2024/18.rs

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

use advent_of_code::{
    strings::{convert_to_array, parsenumber},
    Kartesian, Map, ToCoords, KD,
};
use advent_of_code_macros::include_aoc;
use log::*;

include_aoc!(DATA 2024 18);

const HEIGHT: usize = 71;
const WIDTH: usize = HEIGHT;
const BLOCKS: usize = 1024;

fn get_coords(line: &str) -> Kartesian<usize> {
    let (y, x) = line.split_once(',').unwrap();
    Kartesian::<u32>::new(parsenumber(x), parsenumber(y)).to_coords()
}

#[inline]
fn i_to_c(i: usize) -> char {
    match i % 10 {
        1 => '1',
        2 => '2',
        3 => '3',
        4 => '4',
        5 => '5',
        6 => '6',
        7 => '7',
        8 => '8',
        9 => '9',
        0 => '0',
        _ => unreachable!(),
    }
}

#[derive(Debug, Default, Clone, Ord, Copy)]
struct Node {
    coords: Kartesian<usize>,
    score: usize,
    parent: Kartesian<usize>,
}

impl PartialEq for Node {
    fn eq(&self, other: &Self) -> bool {
        self.coords.eq(&other.coords)
    }
}
impl Eq for Node {}

impl PartialOrd for Node {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        match self.score.partial_cmp(&other.score) {
            Some(Ordering::Equal) => self.coords.partial_cmp(&other.coords),
            x => x,
        }
    }
}

fn astar_search<const WALL: char>(mut map: Map<char>, start_pos: Kartesian<usize>, dest_pos: Kartesian<usize>) -> Option<usize> {
    let maximum = map.size();
    let mut nodelist = HashMap::with_capacity(maximum.x * maximum.y);
    let start = Node {
        coords: start_pos,
        score: 0,
        parent: start_pos,
    };
    let mut destination = Node {
        coords: dest_pos,
        score: maximum.x * maximum.y,
        parent: dest_pos,
    };
    nodelist.insert(start_pos, start);
    let mut open = vec![start_pos];
    let (mut node, mut nodepos, mut coords);
    loop {
        nodepos = match open.pop() {
            None => {
                debug!("Out of possible nodes");
                break;
            },
            Some(x) => x,
        };
        node = *nodelist.get(&nodepos).unwrap();
        for dir in KD::iter(false, false, true) {
            coords = match nodepos.move_dir_max(dir.vector(), dir, maximum) {
                None => continue,
                Some(x) => {
                    if map.get(x) == Some(WALL) {
                        continue;
                    }
                    x
                },
            };
            let newnode = match nodelist.get_mut(&coords) {
                None => {
                    let newnode = Node {
                        coords,
                        score: node.score + 1,
                        parent: node.coords,
                    };
                    map.set(coords, i_to_c(node.score + 1));
                    open.insert(0, newnode.coords);
                    nodelist.insert(coords, newnode);
                    nodelist.get_mut(&coords).unwrap()
                },
                Some(node) => node,
            };
            if newnode.score > node.score + 1 {
                debug!("Overwriting score {} > {}: {:?}", newnode.score, node.score + 1, newnode);
                newnode.parent = node.coords;
                newnode.score = node.score + 1;
            }
            if newnode.coords == destination.coords && newnode.score < destination.score {
                destination.parent = newnode.parent;
                destination.score = newnode.score
            }
        }
        open.sort();
        if open.len() > 300 {
            println!("{:#?}", open);
            break;
        }
        debug!("Open coords: {}\n{}", open.len(), map);
    }
    if destination.parent == dest_pos {
        None
    } else {
        Some(destination.score)
    }
}

fn main() {
    let blocks = convert_to_array::<_, _, '\n'>(DATA, get_coords);
    let mut corrupted = blocks.iter().cloned();
    let mut map = Map::<char>::empty(HEIGHT, WIDTH);
    let mut fallen = 0;
    map.replace_default('.');
    while let Some(coord) = corrupted.next() {
        fallen += 1;
        map.set(coord, '#');
        if fallen == BLOCKS {
            break;
        }
    }
    println!("Minimum Steps: {}", astar_search::<'#'>(map.clone(), map.size() - Kartesian::new(1, 1), Kartesian::default()).unwrap());
    while let Some(coord) = corrupted.next() {
        map.set(coord, '#');
        if astar_search::<'#'>(map.clone(), map.size() - Kartesian::new(1, 1), Kartesian::default()).is_none() {
            println!("First Block is: {},{}", coord.y, coord.x);
            break;
        }
    }
}

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