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

struct Blizzard {
    up: u128,
    right: u128,
    down: u128,
    left: u128,
}

struct Map {
    width: usize,
    height: usize,
    blizzards: Vec<Blizzard>,
}

fn get_input() -> Map {
    let mut blizzards = vec![];
    let mut line_len = 0;

    for (y, line) in lib::iter_input().skip(1).enumerate() {
        line_len = line.len();
        blizzards.push(Blizzard {
            up: 0,
            right: 0,
            down: 0,
            left: 0,
        });

        for (x, c) in line.chars().enumerate() {
            match c {
                '^' => blizzards[y].up |= 1 << (x - 1),
                '>' => blizzards[y].right |= 1 << (x - 1),
                'v' => blizzards[y].down |= 1 << (x - 1),
                '<' => blizzards[y].left |= 1 << (x - 1),
                '#' => {},
                '.' => {},
                _ => unreachable!(),
            }
        }
    }

    blizzards.pop();

    return Map {
        width: line_len - 2,
        height: blizzards.len(),
        blizzards: blizzards,
    };
}

fn shift(i: u128, n: usize, width: usize) -> u128 {
    let _n = n % width;
    return (i >> _n) | (i << (width - _n));
}

fn find_path(map: &Map, start: (usize, usize), end: (usize, usize), offset: usize) -> usize {
    let mut positions = vec![0; map.height];
    let mut i = offset;

    let mask = (1 << map.width) - 1;

    while positions[end.1] & (1 << end.0) == 0 {
        i += 1;
        let mut prev = 0;
        for y in 0..map.height {
            let curr = positions[y];
            let next = if y + 1 < map.height { positions[y + 1] } else { 0 };

            positions[y] = (
                curr
                | prev
                | next
                | (curr >> 1)
                | ((curr << 1) & mask)
                | if y == start.1 { 1 << start.0 } else { 0 }
            ) & !(
                map.blizzards[(y + i) % map.height].up
                | (shift(map.blizzards[y].right, (map.width - 1) * i, map.width) & mask)
                | map.blizzards[(y + (map.height - 1) * i) % map.height].down
                | (shift(map.blizzards[y].left, i, map.width) & mask)
            );

            prev = curr;
        }
    }
    return i + 1;
}

fn main() {
    let map = get_input();
    let start = (0, 0);
    let end = (map.width - 1, map.height - 1);

    let t1 = find_path(&map, start, end, 0);
    println!("part1: {}", t1);

    let t2 = find_path(&map, end, start, t1);
    let t3 = find_path(&map, start, end, t2);
    println!("part2: {}", t3);
}