#[path = "../lib.rs"]
mod lib;

// const SIZE: usize = 6 + 1;
// const N: usize = 12;
const SIZE: usize = 70 + 1;
const N: usize = 1024;

fn parse_input() -> Vec<(usize, usize)> {
    return lib::iter_input()
        .map(|line| {
            let (sx, sy) = line.split_once(',').unwrap();
            let x = sx.parse::<usize>().unwrap();
            let y = sy.parse::<usize>().unwrap();
            return (x, y);
        })
        .collect();
}

fn get_path(map: &[[usize; SIZE]; SIZE], n: usize) -> usize {
    let mut paths = [[usize::MAX; SIZE]; SIZE];
    let mut queue = vec![(SIZE - 1, SIZE - 1)];
    paths[SIZE - 1][SIZE - 1] = 0;

    while let Some((x, y)) = queue.pop() {
        let value = paths[y][x] + 1;

        if x > 0 && map[y][x - 1] >= n && value < paths[y][x - 1] {
            paths[y][x - 1] = value;
            queue.push((x - 1, y));
        }

        if x < SIZE - 1 && map[y][x + 1] >= n && value < paths[y][x + 1] {
            paths[y][x + 1] = value;
            queue.push((x + 1, y));
        }

        if y > 0 && map[y - 1][x] >= n && value < paths[y - 1][x] {
            paths[y - 1][x] = value;
            queue.push((x, y - 1));
        }

        if y < SIZE - 1 && map[y + 1][x] >= n && value < paths[y + 1][x] {
            paths[y + 1][x] = value;
            queue.push((x, y + 1));
        }

        queue.sort_by_key(|(x, y)| x + y);
    }

    return paths[0][0];
}

fn binary_search(map: &[[usize; SIZE]; SIZE]) -> usize {
    let mut n1 = N;
    let mut n2 = n1 * 2;

    while get_path(&map, n2) != usize::MAX {
        n1 *= 2;
        n2 *= 2;
    }

    while n2 > n1 + 1 {
        let n = (n1 + n2) / 2;
        if get_path(&map, n) == usize::MAX {
            n2 = n;
        } else {
            n1 = n;
        }
    }

    return n1;
}

fn main() {
    let input = parse_input();

    let mut map = [[usize::MAX; SIZE]; SIZE];
    for (i, (x, y)) in input.iter().enumerate() {
        map[*y][*x] = i;
    }

    println!("part1: {}", get_path(&map, N));

    let (x, y) = input[binary_search(&map)];
    println!("part2: {},{}", x, y);
}