use std::collections::HashSet;
use std::collections::HashMap;

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

enum Dir { North, East, South, West }

const DIRS: [Dir; 4] = [Dir::North, Dir::South, Dir::West, Dir::East];

fn get_input() -> HashSet<(i64, i64)> {
    let mut elves = HashSet::new();
    for (y, line) in lib::iter_input().enumerate() {
        for (x, c) in line.chars().enumerate() {
            if c == '#' {
                elves.insert((x as i64, y as i64));
            }
        }
    }
    return elves;
}

fn propose_move(elves: &HashSet<(i64, i64)>, x: i64, y: i64, offset: usize) -> (i64, i64) {
    if !(
        elves.contains(&(x, y - 1))
        || elves.contains(&(x + 1, y - 1))
        || elves.contains(&(x + 1, y))
        || elves.contains(&(x + 1, y + 1))
        || elves.contains(&(x, y + 1))
        || elves.contains(&(x - 1, y + 1))
        || elves.contains(&(x - 1, y))
        || elves.contains(&(x - 1, y - 1))
    ) {
        return (x, y);
    }

    for dir_i in 0..4 {
        match DIRS[(dir_i + offset) % 4] {
            Dir::North => {
                if !(elves.contains(&(x - 1, y - 1)) || elves.contains(&(x, y - 1)) || elves.contains(&(x + 1, y - 1))) {
                    return (x, y - 1);
                }
            },
            Dir::East => {
                if !(elves.contains(&(x + 1, y - 1)) || elves.contains(&(x + 1, y)) || elves.contains(&(x + 1, y + 1))) {
                    return (x + 1, y);
                }
            },
            Dir::South => {
                if !(elves.contains(&(x - 1, y + 1)) || elves.contains(&(x, y + 1)) || elves.contains(&(x + 1, y + 1))) {
                    return (x, y + 1);
                }
            },
            Dir::West => {
                if !(elves.contains(&(x - 1, y - 1)) || elves.contains(&(x - 1, y)) || elves.contains(&(x - 1, y + 1))) {
                    return (x - 1, y);
                }
            },
        }
    }
    return (x, y);
}

fn do_round(elves: &mut HashSet<(i64, i64)>, offset: usize) -> bool {
    let mut proposals: HashMap<(i64, i64), Vec<(i64, i64)>> = HashMap::new();
    let mut changed = false;

    for pos in elves.iter() {
        let proposal = propose_move(elves, pos.0, pos.1, offset);
        if proposal != *pos {
            proposals.entry(proposal)
                .and_modify(|v| v.push(*pos))
                .or_insert(vec![*pos]);
        }
    }

    for (new, olds) in proposals.iter() {
        if olds.len() == 1 {
            elves.remove(&olds[0]);
            elves.insert(*new);
            changed = true;
        }
    }

    return changed;
}

fn main() {
    let mut elves = get_input();

    for i in 0.. {
        let changed = do_round(&mut elves, i);

        if i + 1 == 10 {
            let x1 = elves.iter().map(|(x, _)| x).min().unwrap();
            let y1 = elves.iter().map(|(_, y)| y).min().unwrap();
            let x2 = elves.iter().map(|(x, _)| x).max().unwrap();
            let y2 = elves.iter().map(|(_, y)| y).max().unwrap();

            let score = (x2 + 1 - x1) * (y2 + 1 - y1) - elves.len() as i64;
            println!("part1: {}", score);
        }
        if !changed {
            println!("part2: {}", i + 1);
            break;
        }
    }
}