use nom::{
    branch::alt,
    bytes::complete::tag,
    character::complete::line_ending,
    combinator::{map, value},
    multi::{many1, separated_list1},
    IResult,
};
use std::{
    collections::{BTreeMap, BTreeSet, VecDeque},
    fs,
};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let input = fs::read_to_string("inputs/day_23_test.txt")?;
    let mut elves = ElfMap::parser(&input).unwrap().1;

    dbg!(&elves);
    for _ in 0..10 {
        elves.process_round();
        dbg!(&elves);
    }

    dbg!(elves.count_empty_ground());

    Ok(())
}

#[derive(Debug, Clone)]
struct ElfMap {
    elves: BTreeSet<Point>,
    check_order: VecDeque<Direction>,
}

#[derive(Debug, Default, Clone, PartialEq, Eq, PartialOrd, Ord)]
struct Point {
    y: i64,
    x: i64,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
enum Direction {
    North,
    South,
    West,
    East,
}

impl ElfMap {
    fn parser(input: &str) -> IResult<&str, Self> {
        map(
            separated_list1(
                line_ending,
                map(
                    many1(alt((value(true, tag("#")), value(false, tag("."))))),
                    |row| {
                        row.into_iter()
                            .enumerate()
                            .filter_map(|(x, occupied)| occupied.then_some(x as i64))
                            .collect::<Vec<i64>>()
                    },
                ),
            ),
            |rows| {
                let elves = rows
                    .into_iter()
                    .enumerate()
                    .flat_map(|(y, row)| row.into_iter().map(move |x| Point { x, y: y as i64 }))
                    .collect();
                ElfMap {
                    elves,
                    check_order: [
                        Direction::North,
                        Direction::South,
                        Direction::West,
                        Direction::East,
                    ]
                    .into(),
                }
            },
        )(input)
    }

    fn process_round(&mut self) {
        // key is destination!
        let mut elf_moves: BTreeMap<Point, Point> = BTreeMap::new();
        let mut conflict_moves: BTreeSet<Point> = BTreeSet::new();

        // phase 1: figure out where each elf wants to move
        for elf in &self.elves {
            if let Some(destination) = self.find_elf_move(&elf) {
                if elf_moves.contains_key(&destination) {
                    elf_moves.remove(&destination);
                    conflict_moves.insert(destination);
                } else if !conflict_moves.contains(&destination) {
                    elf_moves.insert(destination, elf.clone());
                }
            }
        }

        // phase 2: move the elves
        for (dest, src) in elf_moves {
            self.elves.remove(&src);
            self.elves.insert(dest);
        }

        let rotate = self
            .check_order
            .pop_front()
            .expect("Where did the directions go?");
        self.check_order.push_back(rotate);
    }

    fn find_elf_move(&self, elf: &Point) -> Option<Point> {
        let all_adjacent = elf.adjacent(None);
        let any_adjacent_elves = all_adjacent.into_iter().any(|p| self.elves.contains(&p));
        if !any_adjacent_elves {
            None
        } else {
            self.check_order
                .iter()
                .filter_map(|dir| {
                    let adjacent = elf.adjacent(Some(*dir));
                    let any_adjacent_elves = adjacent.iter().any(|p| self.elves.contains(p));
                    if !any_adjacent_elves {
                        Some(adjacent[1].clone())
                    } else {
                        None
                    }
                })
                .next()
        }
    }

    fn count_empty_ground(&self) -> i64 {
        let mut min_x = 0;
        let mut min_y = 0;
        let mut max_x = 0;
        let mut max_y = 0;
        for elf in &self.elves {
            min_x = min_x.min(elf.x);
            min_y = min_y.min(elf.y);
            max_x = max_x.max(elf.x);
            max_y = max_y.max(elf.y);
        }

        let all_ground = (max_x - min_x + 1) * (max_y - min_y + 1);
        let covered_ground = self.elves.len() as i64;
        all_ground - covered_ground
    }
}

impl Point {
    fn adjacent(&self, direction: Option<Direction>) -> Vec<Point> {
        let (y_range, x_range) = match direction {
            None => ((-1..=1), (-1..=1)),
            Some(Direction::North) => ((-1..=-1), (-1..=1)),
            Some(Direction::South) => ((1..=1), (-1..=1)),
            Some(Direction::East) => ((-1..=1), (-1..=-1)),
            Some(Direction::West) => ((-1..=1), (1..=1)),
        };

        y_range
            .flat_map(|dy| {
                x_range.clone().map(move |dx| Point {
                    x: self.x + dx,
                    y: self.y + dy,
                })
            })
            .filter(|p| p != self)
            .collect()
    }
}