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.txt")?;
    let elves = ElfMap::parser(&input).unwrap().1;

    {
        let mut elves_1 = elves.clone();
        for _ in 0..10 {
            elves_1.process_round();
        }
        dbg!(elves_1.count_empty_ground());
    }

    {
        let mut elves_2 = elves;
        for round in 1.. {
            if !elves_2.process_round() {
                dbg!(round);
                break;
            }
        }
    }

    Ok(())
}

#[derive(Debug, Clone, PartialEq, Eq)]
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) -> bool {
        // 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) {
                use std::collections::btree_map::Entry;
                match elf_moves.entry(destination) {
                    Entry::Occupied(elf_move_entry) => {
                        conflict_moves.insert(elf_move_entry.key().clone());
                        elf_move_entry.remove_entry();
                    }
                    Entry::Vacant(elf_move_entry) => {
                        if !conflict_moves.contains(elf_move_entry.key()) {
                            elf_move_entry.insert(elf.clone());
                        }
                    }
                }
            }
        }

        let any_elf_moved = !elf_moves.is_empty();

        // 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);

        any_elf_moved
    }

    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 elf_x = self.elves.iter().map(|elf| elf.x);
        let min_x = elf_x.clone().min().unwrap_or(0);
        let max_x = elf_x.max().unwrap_or(0);

        let elf_y = self.elves.iter().map(|elf| elf.y);
        let min_y = elf_y.clone().min().unwrap_or(0);
        let max_y = elf_y.max().unwrap_or(0);

        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::West) => ((-1..=1), (-1..=-1)),
            Some(Direction::East) => ((-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()
    }
}

#[test]
fn follows_the_example() {
    let mut elf_map = ElfMap::parser(
        r"..............
..............
.......#......
.....###.#....
...#...#.#....
....#...##....
...#.###......
...##.#.##....
....#..#......
..............
..............
..............",
    )
    .unwrap()
    .1;

    elf_map.process_round();
    assert_eq!(
        elf_map.elves,
        ElfMap::parser(
            r"..............
.......#......
.....#...#....
...#..#.#.....
.......#..#...
....#.#.##....
..#..#.#......
..#.#.#.##....
..............
....#..#......
..............
..............
"
        )
        .unwrap()
        .1
        .elves
    );

    elf_map.process_round();
    assert_eq!(
        elf_map.elves,
        ElfMap::parser(
            r"..............
.......#......
....#.....#...
...#..#.#.....
.......#...#..
...#..#.#.....
.#...#.#.#....
..............
..#.#.#.##....
....#..#......
..............
..............
"
        )
        .unwrap()
        .1
        .elves
    );

    elf_map.process_round();
    assert_eq!(
        elf_map.elves,
        ElfMap::parser(
            r"..............
.......#......
.....#....#...
..#..#...#....
.......#...#..
...#..#.#.....
.#..#.....#...
.......##.....
..##.#....#...
...#..........
.......#......
.............."
        )
        .unwrap()
        .1
        .elves
    );

    elf_map.process_round();
    assert_eq!(
        elf_map.elves,
        ElfMap::parser(
            r"..............
.......#......
......#....#..
..#...##......
...#.....#.#..
.........#....
.#...###..#...
..#......#....
....##....#...
....#.........
.......#......
.............."
        )
        .unwrap()
        .1
        .elves
    );

    elf_map.process_round();
    assert_eq!(
        elf_map.elves,
        ElfMap::parser(
            r".......#......
..............
..#..#.....#..
.........#....
......##...#..
.#.#.####.....
...........#..
....##..#.....
..#...........
..........#...
....#..#......
.............."
        )
        .unwrap()
        .1
        .elves
    );

    for _ in 0..5 {
        elf_map.process_round();
    }
    assert_eq!(
        elf_map.elves,
        ElfMap::parser(
            r".......#......
...........#..
..#.#..#......
......#.......
...#.....#..#.
.#......##....
.....##.......
..#........#..
....#.#..#....
..............
....#..#..#...
.............."
        )
        .unwrap()
        .1
        .elves
    );
}