use std::collections::VecDeque;

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

fn parse_input() -> (Vec<Vec<bool>>, usize, usize) {
    let mut rocks = vec![];
    let mut x0 = 0;
    let mut y0 = 0;

    for (y, line) in lib::iter_input().enumerate() {
        let mut row = vec![];
        for (x, b) in line.bytes().enumerate() {
            match b {
                b'.' => { row.push(false) }
                b'#' => { row.push(true) }
                b'S' => {
                    row.push(false);
                    x0 = x;
                    y0 = y;
                }
                _ => unreachable!(),
            };
        }
        rocks.push(row);
    }
    return (rocks, x0, y0);
}

fn flood(rocks: &Vec<Vec<bool>>, x0: usize, y0: usize, factor: usize) -> Vec<Vec<usize>> {
    let n = rocks.len();
    let mut distance = vec![vec![usize::MAX; n * factor]; n * factor];
    let mut queue = VecDeque::new();

    let offset = n * (factor / 2);
    queue.push_back((x0 + offset, y0 + offset));
    distance[y0 + offset][x0 + offset] = 0;

    while let Some((x, y)) = queue.pop_front() {
        let mut neighbors = vec![];

        if x > 0 {
            neighbors.push((x - 1, y));
        }
        if x + 1 < n * 5 {
            neighbors.push((x + 1, y));
        }
        if y > 0 {
            neighbors.push((x, y - 1));
        }
        if y + 1 < n * 5 {
            neighbors.push((x, y + 1));
        }

        let v = distance[y][x] + 1;
        for (xx, yy) in neighbors.iter() {
            if !rocks[*yy % n][*xx % n] && distance[*yy][*xx] > v {
                distance[*yy][*xx] = v;
                queue.push_back((*xx, *yy));
            }
        }
    }

    return distance;
}

fn count(distance: &Vec<Vec<usize>>, steps: usize) -> usize {
    let mut count = 0;
    for y in 0..distance.len() {
        for x in 0..distance[0].len() {
            if distance[y][x] <= steps && distance[y][x] % 2 == steps % 2 {
                count += 1;
            }
        }
    }
    return count;
}

fn quad(c1: usize, c2: usize, c3: usize, k: usize) -> usize {
    let a = (c3 - 2 * c2 + c1) / 2;
    let c = c1;
    let b = c2 - a - c;
    return a * k * k + b * k + c;
}

fn main() {
    let (rocks, x0, y0) = parse_input();
    assert!(rocks.len() == rocks[0].len());
    let distance = flood(&rocks, x0, y0, 5);

    println!("part1: {}", count(&distance, 64));

    // I originally thought that the prism just repeats.
    // Reddit told me to do quadratic interpolation instead and it worked.
    let steps = 26_501_365;
    let n = rocks.len();
    assert!(steps % n == n / 2);
    let c1 = count(&distance, n / 2);
    let c2 = count(&distance, n + n / 2);
    let c3 = count(&distance, 2 * n + n / 2);
    println!("part2: {}", quad(c1, c2, c3, steps / n));
}