use std::collections::{HashMap, HashSet};

static DAY: u8 = 12;

fn main() {
    let input = advent::read_lines(DAY);
    println!("{DAY}a: {}", fencing_price(&input, false));
    println!("{DAY}b: {}", fencing_price(&input, true));
}

#[derive(Eq, PartialEq, Copy, Clone, Hash)]
struct Position {
    x: isize,
    y: isize,
}

fn count_fences(region: &HashSet<Position>) -> usize {
    let mut total_fences = 0;
    for pos in region {
        /* every plot has 4 fences, except it has neighbors of the same type */
        let mut fences = 4;
        for diff in [(-1, 0), (1, 0), (0, -1), (0, 1)] {
            let neighbor = Position { x: pos.x + diff.0, y: pos.y + diff.1 };
            if region.contains(&neighbor) {
                fences -= 1;
            }
        }
        total_fences += fences;
    }
    total_fences
}

fn count_sides(region: &HashSet<Position>) -> usize {
    let mut horizontal = HashSet::new();
    let mut vertical = HashSet::new();

    let mut min_pos = Position { x: isize::MAX, y: isize::MAX };
    let mut max_pos = Position { x: isize::MIN, y: isize::MIN };

    for pos in region {
        min_pos.x = min_pos.x.min(pos.x);
        min_pos.y = min_pos.y.min(pos.y);
        max_pos.x = max_pos.x.max(pos.x);
        max_pos.y = max_pos.y.max(pos.y);

        let neighbor = Position { x: pos.x, y: pos.y + 1 };
        if !region.contains(&neighbor) {
            horizontal.insert((neighbor, 1));
            max_pos.y = max_pos.y.max(neighbor.y);
        }

        let neighbor = Position { x: pos.x, y: pos.y - 1 };
        if !region.contains(&neighbor) {
            horizontal.insert((neighbor, 0));
            min_pos.y = min_pos.y.min(neighbor.y);
        }

        let neighbor = Position { x: pos.x + 1, y: pos.y };
        if !region.contains(&neighbor) {
            vertical.insert((neighbor, 1));
            max_pos.x = max_pos.x.max(neighbor.x);
        }

        let neighbor = Position { x: pos.x - 1, y: pos.y };
        if !region.contains(&neighbor) {
            vertical.insert((neighbor, 0));
            min_pos.x = min_pos.x.min(neighbor.x);
        }
    }

    let mut sides = 0;
    for separator in [0, 1] {
        for x in min_pos.x ..= max_pos.x {
            let mut is_side = false;
            for y in min_pos.y ..= max_pos.y {
                let check = Position { x, y };
                if is_side && !vertical.contains(&(check, separator)) {
                    is_side = false;
                    sides += 1;
                }
                if !is_side && vertical.contains(&(check, separator)) {
                    is_side = true;
                }
            }
        }
    }
    for separator in [0, 1] {
        for y in min_pos.y ..= max_pos.y {
            let mut is_side = false;
            for x in min_pos.x ..= max_pos.x {
                let check = Position { x, y };
                if is_side && !horizontal.contains(&(check, separator)) {
                    is_side = false;
                    sides += 1;
                }
                if !is_side && horizontal.contains(&(check, separator)) {
                    is_side = true;
                }
            }
        }
    }
    sides
}

fn find_region(plots: &HashMap<Position, char>, pos: Position, visited: &mut HashSet<Position>) -> HashSet<Position> {
    let mut region = HashSet::new();
    if visited.contains(&pos) {
        return region;
    }

    let plot_type = plots.get(&pos).unwrap();
    region.insert(pos);
    visited.insert(pos);
    for diff in [(-1, 0), (1, 0), (0, -1), (0, 1)] {
        let neighbor = Position { x: pos.x + diff.0, y: pos.y + diff.1 };
        if let Some(t) = plots.get(&neighbor) {
            if t == plot_type {
                for r in find_region(plots, neighbor, visited) {
                    region.insert(r);
                }
            }
        }
    }

    region
}

fn find_regions(plots: &HashMap<Position, char>) -> HashMap<char, Vec<HashSet<Position>>> {
    let mut regions = HashMap::new();
    let mut visited = HashSet::new();

    for (pos, c) in plots {
        if visited.contains(pos) {
            continue;
        }
        let region = find_region(plots, *pos, &mut HashSet::new());
        for plot in &region {
            visited.insert(*plot);
        }
        regions.entry(*c).or_insert(Vec::new()).push(region);
    }

    regions
}

fn fencing_price(input: &[String], with_discount: bool) -> usize {
    let mut plots = HashMap::new();
    for (y, line) in input.iter().enumerate() {
        for (x, c) in line.chars().enumerate() {
            let pos = Position { x: x as isize, y: y as isize };
            plots.insert(pos, c);
        }
    }
    let all_regions = find_regions(&plots);
    let mut total_price = 0;
    for regions in all_regions.values() {
        for region in regions {
            let area = region.len();
            let fences = if !with_discount {
                count_fences(region)
            } else {
                count_sides(region)
            };
            total_price += area * fences;
        }
    }

    total_price
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test() {
        let input = [
            "AAAA",
            "BBCD",
            "BBCC",
            "EEEC",
        ].iter().map(|&x| String::from(x)).collect::<Vec<_>>();
        assert_eq!(fencing_price(&input, false), 140);
        assert_eq!(fencing_price(&input, true), 80);

        let input = [
            "OOOOO",
            "OXOXO",
            "OOOOO",
            "OXOXO",
            "OOOOO",
        ].iter().map(|&x| String::from(x)).collect::<Vec<_>>();
        assert_eq!(fencing_price(&input, false), 772);
        assert_eq!(fencing_price(&input, true), 436);

        let input = [
            "RRRRIICCFF",
            "RRRRIICCCF",
            "VVRRRCCFFF",
            "VVRCCCJFFF",
            "VVVVCJJCFE",
            "VVIVCCJJEE",
            "VVIIICJJEE",
            "MIIIIIJJEE",
            "MIIISIJEEE",
            "MMMISSJEEE",
        ].iter().map(|&x| String::from(x)).collect::<Vec<_>>();
        assert_eq!(fencing_price(&input, false), 1930);

        let input = [
            "EEEEE",
            "EXXXX",
            "EEEEE",
            "EXXXX",
            "EEEEE",
        ].iter().map(|&x| String::from(x)).collect::<Vec<_>>();
        assert_eq!(fencing_price(&input, true), 236);

        let input = [
           "AAAAAA",
           "AAABBA",
           "AAABBA",
           "ABBAAA",
           "ABBAAA",
           "AAAAAA",
        ].iter().map(|&x| String::from(x)).collect::<Vec<_>>();
        assert_eq!(fencing_price(&input, true), 368);
    }
}