use std::fmt;
use std::collections::HashSet;

enum Rule {
    Death,
    Birth,
    Live
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
struct Cell {
    x: i32,
    y: i32
}

impl Cell {
    fn new(x: i32, y: i32) -> Self {
        Self { x, y }
    }

    fn neighbors(&self) -> [Cell; 8] {
        [
            Cell::new(self.x - 1, self.y - 1),
            Cell::new(self.x - 1, self.y + 0),
            Cell::new(self.x - 1, self.y + 1),
            Cell::new(self.x + 0, self.y - 1),
            Cell::new(self.x + 0, self.y + 1),
            Cell::new(self.x + 1, self.y - 1),
            Cell::new(self.x + 1, self.y + 0),
            Cell::new(self.x + 1, self.y + 1),
        ]
    }
}

#[derive(Clone)]
struct LifeState {
    cells: HashSet<Cell>
}

impl LifeState {
    fn new() -> Self {
        Self { cells: HashSet::new() }
    }

    fn set_alive(&self, cell: Cell) -> Self {
        let mut updated = self.cells.clone();
        updated.insert(cell);
        Self { cells: updated }
    }

    fn iterate(&self, rules: &[Rule; 9]) -> Self {
        fn update_cell(old_state: &LifeState, new_state: &LifeState, cell: Cell, rules: &[Rule; 9]) -> LifeState {
            if new_state.cells.contains(&cell) {
                new_state.clone()
            } else {
                let alive_count = cell.neighbors().iter().filter(|cell| old_state.cells.contains(cell)).count();
                match rules[alive_count] {
                    Rule::Death => new_state.clone(),
                    Rule::Live => if old_state.cells.contains(&cell) { new_state.set_alive(cell) } else { new_state.clone() },
                    Rule::Birth => new_state.set_alive(cell),
                }
            }
        }

        self.cells.iter()
            .flat_map(|&cell| cell.neighbors().to_vec().into_iter().chain(vec![cell]).collect::<Vec<_>>())
            .fold(LifeState::new(), |new_state, cell|
            update_cell(self, &new_state, cell, rules)
        )
    }
}

impl fmt::Display for LifeState {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        if self.cells.is_empty() {
            return write!(f, "");
        }

        struct Border {
            left: i32,
            top: i32,
            right: i32,
            bottom: i32,
        }

        let mut iter = self.cells.iter().map(|it| Border {
            left: it.x, right: it.x,
            top: it.y, bottom: it.y,
        });
        let start = iter.next().unwrap();

        let border = iter.fold(start, |acc, border|
            Border {
                left: acc.left.min(border.left), right: acc.right.max(border.right),
                top: acc.top.min(border.top), bottom: acc.bottom.max(border.bottom),
            }
        );

        (border.top..=border.bottom).for_each(|row| {
            (border.left..=border.right).for_each(|col| {
                if self.cells.contains(&Cell::new(col, row)) {
                    write!(f, "X").unwrap();
                } else {
                    write!(f, " ").unwrap();
                }
            });
            write!(f, "\n").unwrap();
        });
        write!(f, "\n")
    }
}

fn main() {
    let rules = [
        Rule::Death, Rule::Death,
        Rule::Live,
        Rule::Birth,
        Rule::Death, Rule::Death, Rule::Death, Rule::Death, Rule::Death,
    ];
    let glider = LifeState::new()
        .set_alive(Cell::new(0, 0))
        .set_alive(Cell::new(1, 0))
        .set_alive(Cell::new(2, 0))
        .set_alive(Cell::new(2, -1))
        .set_alive(Cell::new(1, -2));

    println!("{}", glider);

    (0..100).fold(glider, |acc, _| {
        println!("-------------------------------------------");
        let next = acc.iterate(&rules);
        println!("{}", next);
        next
    });
}