Untitled

pub fn solution(test: bool) -> ((usize, Duration), (usize, Duration)) {
    let lines;
    if test {
        lines = include_str!("../../../AdventOfCodeInputs/problem_inputs_2024/day_18_test.txt");
    } else {
        lines = include_str!("../../../AdventOfCodeInputs/problem_inputs_2024/day_18.txt");
    }
    (solve01(lines), solve02(lines))
}

fn solve01(lines: &str) -> (usize, Duration) {
    let now = Instant::now();
    let maze = Maze::from_str(lines, (71, 71), 1024);
    let start = (0, 0);
    let end = (maze.bounds.0 - 1, maze.bounds.1 - 1);
    let result = maze.find_shortest_path(start, end).unwrap();
    (result, now.elapsed())
}

fn solve02(lines: &str) -> (usize, Duration) {
    let now = Instant::now();
    let mut low = 1024;
    let mut high = lines.lines().count();
    let mut result = 0;

    while low <= high {
        let mid = (low + high) / 2;
        let maze = Maze::from_str(lines, (71, 71), mid);
        let start = (0, 0);
        let end = (maze.bounds.0 - 1, maze.bounds.1 - 1);

        if maze.find_shortest_path(start, end).is_some() {
            result = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    dbg!(lines.lines().nth(result));
    (0, now.elapsed())
}

type Pos = (isize, isize);
struct Maze {
    blocks: FxHashSet<Pos>,
    bounds: (isize, isize),
}

impl Maze {
    fn from_str(lines: &str, bounds: (isize, isize), bytes_to_count: usize) -> Self {
        let mut blocks = FxHashSet::default();
        for pos in lines.lines().take(bytes_to_count) {
            let (xstr, ystr) = pos.split_once(',').unwrap();
            let x = xstr.parse::<isize>().unwrap();
            let y = ystr.parse::<isize>().unwrap();
            blocks.insert((x, y));
        }
        Self { blocks, bounds }
    }

    fn find_shortest_path(&self, start: Pos, end: Pos) -> Option<usize> {
        let mut dist = FxHashSet::default();
        let mut heap = VecDeque::new();
        heap.push_back((0, start));

        while let Some((cost, pos)) = heap.pop_front() {
            if pos == end {
                return Some(cost);
            }

            if !dist.insert(pos) {
                continue;
            }

            for neighbour in self.get_neighbours(pos) {
                if !dist.contains(&neighbour) {
                    heap.push_back((cost + 1, neighbour));
                }
            }
        }

        None
    }

    fn get_neighbours(&self, pos: Pos) -> Vec<Pos> {
        let mut neighbours = Vec::new();
        let (x, y) = pos;
        for (dx, dy) in &[(0, 1), (0, -1), (1, 0), (-1, 0)] {
            let next = (x + dx, y + dy);
            if next.0 < 0 || next.1 < 0 || next.0 >= self.bounds.0 || next.1 >= self.bounds.1 {
                continue;
            }
            if self.blocks.contains(&next) {
                continue;
            }
            neighbours.push(next);
        }
        neighbours
    }
}