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

static DAY: u8 = 12;

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

#[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 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]) -> usize {
    let mut plots = HashMap::new();
    for (x, line) in input.iter().enumerate() {
        for (y, 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 = count_fences(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), 140);

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

        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), 1930);
    }
}