use std::collections::HashMap;
use std::collections::HashSet;
use std::collections::VecDeque;

#[path = "../lib.rs"]
mod lib;

type XYZ = (usize, usize, usize);

fn parse_input() -> Vec<(XYZ, XYZ)> {
    let mut bricks = vec![];
    for line in lib::iter_input() {
        let (s1, s2) = line.split_once('~').unwrap();
        let v1 = s1.split(',').map(|s| s.parse().unwrap()).collect::<Vec<usize>>();
        let v2 = s2.split(',').map(|s| s.parse().unwrap()).collect::<Vec<usize>>();
        assert!(v1[0] <= v2[0]);
        assert!(v1[1] <= v2[1]);
        assert!(v1[2] <= v2[2]);
        bricks.push(((v1[0], v1[1], v1[2]), (v2[0], v2[1], v2[2])));
    }
    bricks.sort_by_key(|brick| brick.0.2);
    return bricks;
}

fn get_support(bricks: &Vec<(XYZ, XYZ)>) -> Vec<HashSet<usize>> {
    let mut heights: HashMap<(usize, usize), (usize, usize)> = HashMap::new();
    let mut supported_by = vec![HashSet::new(); bricks.len()];

    for (i, brick) in bricks.iter().enumerate() {
        let mut zn = 0;
        for x in brick.0.0..=brick.1.0 {
            for y in brick.0.1..=brick.1.1 {
                if let Some((z, j)) = heights.get(&(x, y)) {
                    if *z > zn {
                        zn = *z;
                        supported_by[i].clear();
                        supported_by[i].insert(*j);
                    } else if *z == zn {
                        supported_by[i].insert(*j);
                    }
                }
            }
        }
        for x in brick.0.0..=brick.1.0 {
            for y in brick.0.1..=brick.1.1 {
                let height = brick.1.2 - brick.0.2 + 1;
                heights.insert((x, y), (zn + height, i));
            }
        }
    }

    return supported_by;
}

fn invert(supported_by: &Vec<HashSet<usize>>) -> Vec<HashSet<usize>> {
    let mut inverse = vec![HashSet::new(); supported_by.len()];
    for i in 0..supported_by.len() {
        for j in supported_by[i].iter() {
            inverse[*j].insert(i);
        }
    }
    return inverse;
}

fn count_falling(supported_by: &Vec<HashSet<usize>>, supports: &Vec<HashSet<usize>>, i0: usize) -> usize {
    let mut queue = VecDeque::new();
    let mut falling = HashSet::new();
    queue.push_back(i0);
    falling.insert(i0);
    while let Some(i) = queue.pop_front() {
        for j in supports[i].iter() {
            if !supported_by[*j].difference(&falling).next().is_some() {
                falling.insert(*j);
                queue.push_back(*j);
            }
        }
    }
    return falling.len() - 1;
}

fn main() {
    let bricks = parse_input();

    let supported_by = get_support(&bricks);
    let supports = invert(&supported_by);

    let mut count1 = 0;
    let mut count2 = 0;
    for i in 0..bricks.len() {
        let falling = count_falling(&supported_by, &supports, i);
        if falling == 0 {
            count1 += 1;
        }
        count2 += falling;
    }

    println!("part1: {}", count1);
    println!("part2: {}", count2);
}