use std::collections::HashSet;
use std::collections::HashMap;
use std::convert::TryInto;

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

const WIDTH: usize = 7;

struct Shape {
    blocks: Vec<(usize, usize)>,
    bottom: Vec<(usize, usize)>,
    left: Vec<(usize, usize)>,
    right: Vec<(usize, usize)>,
    width: usize,
    height: usize,
}

#[derive(Hash, PartialEq, Eq)]
struct CacheKey {
    move_i: usize,
    shape_i: usize,
    // not sure if 4 rows are enough to capture this, but hope it works, but at least its very probable
    top_rows: [[bool; WIDTH]; 4],
}

fn make_shape(blocks: Vec<(usize, usize)>) -> Shape {
    return Shape {
        blocks: blocks.clone(),
        bottom: blocks.iter().filter(|(x, y)| *y == 0 || !blocks.contains(&(*x, *y - 1))).map(|(x, y)| (*x, *y)).collect(),
        left: blocks.iter().filter(|(x, y)| *x == 0 || !blocks.contains(&(*x - 1, *y))).map(|(x, y)| (*x, *y)).collect(),
        right: blocks.iter().filter(|(x, y)| !blocks.contains(&(*x + 1, *y))).map(|(x, y)| (*x, *y)).collect(),
        width: blocks.iter().map(|(x, _)| *x).max().unwrap() + 1,
        height: blocks.iter().map(|(_, y)| *y).max().unwrap() + 1,
    };
}

fn get_input() -> Vec<bool> {
    let mut moves = vec![];
    for line in lib::iter_input() {
        for c in line.chars() {
            match c {
                '<' => moves.push(false),
                '>' => moves.push(true),
                _ => unreachable!(),
            }
        }
    }
    return moves;
}

#[allow(dead_code)]
fn render(covered: &HashSet<(usize, usize)>) {
    let height = covered.iter().map(|(_, y)| *y).max().unwrap() + 1;

    for y in (0..height + 3).rev() {
        for x in 0..WIDTH {
            if covered.contains(&(x, y)) {
                print!("#");
            } else {
                print!(".");
            }
        }
        print!("\n");
    }
    print!("\n");
}

fn part1(moves: &Vec<bool>, shapes: &[Shape; 5], n: usize) -> usize {
    let mut height = 0;
    let mut move_i = 0;
    let mut i = 0;
    let mut covered: HashSet<(usize, usize)> = HashSet::new();

    let mut cache = HashMap::new();
    let mut jump_height = 0;

    while i < n {
        let shape = &shapes[i % shapes.len()];
        let mut x = 2;
        let mut y = height;

        // PERF: for the first three steps there can bo no collisions
        for _ in 0..3 {
            if moves[move_i] {
                if x + shape.width < WIDTH {
                    x += 1;
                }
            } else {
                if x > 0 {
                    x -= 1;
                }
            }
            move_i = (move_i + 1) % moves.len();
        }

        loop {
            let move_right = moves[move_i];
            if move_right {
                if x + shape.width < WIDTH && shape.right.iter().all(|(xs, ys)| !covered.contains(&((x + *xs + 1, y + *ys)))) {
                    x += 1;
                }
            } else {
                if x > 0 && shape.left.iter().all(|(xs, ys)| !covered.contains(&((x + *xs - 1, y + *ys)))) {
                    x -= 1;
                }
            }
            move_i = (move_i + 1) % moves.len();

            if y > 0 && shape.bottom.iter().all(|(xs, ys)| !covered.contains(&((x + *xs, y + *ys - 1)))) {
                y -= 1;
            } else {
                break;
            }
        }

        covered.extend(shape.blocks.iter().map(|(xs, ys)| (x + xs, y + ys)));
        height = (y + shape.height).max(height);

        if jump_height == 0 {
            let cache_key = CacheKey {
                move_i: move_i,
                shape_i: i % shapes.len(),
                top_rows: (0..4).map(|x| {
                    return (0..WIDTH).map(|dy| {
                        return dy < height && covered.contains(&(x, height - 1 - dy));
                    }).collect::<Vec<bool>>().try_into().unwrap();
                }).collect::<Vec<[bool; WIDTH]>>().try_into().unwrap(),
            };

            if let Some((prior_i, prior_height)) = cache.get(&cache_key) {
                let di = i - prior_i;
                let dh = height - prior_height;
                let count = (n - i) / di;
                println!("jumped from {} to {} ({}x{})", i, i + di * count, di, count);
                i += di * count;
                jump_height =  dh * count;
            } else {
                cache.insert(cache_key, (i, height));
            }
        }

        // render(&covered);

        i += 1;
    }

    return height + jump_height;
}

fn main() {
    let moves = get_input();
    let shapes = [
        make_shape(vec![
            (0, 0),
            (1, 0),
            (2, 0),
            (3, 0),
        ]),
        make_shape(vec![
            (1, 1),
            (0, 1),
            (2, 1),
            (1, 0),
            (1, 2),
        ]),
        make_shape(vec![
            (0, 0),
            (1, 0),
            (2, 0),
            (2, 1),
            (2, 2),
        ]),
        make_shape(vec![
            (0, 0),
            (0, 1),
            (0, 2),
            (0, 3),
        ]),
        make_shape(vec![
            (0, 0),
            (1, 0),
            (0, 1),
            (1, 1),
        ]),
    ];

    println!("part1: {}", part1(&moves, &shapes, 2022));
    println!("part2: {}", part1(&moves, &shapes, 1000000000000));
}