day22.rs

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

type Pos = (usize, usize, usize);
type Brick = (Pos, Pos);

fn parse(input: &str) -> Vec<Brick> {
    input
        .lines()
        .map(|l| {
            let mut l = l.split('~').map(|p| {
                let mut p = p.split(',').map(|n| n.parse().unwrap());
                (p.next().unwrap(), p.next().unwrap(), p.next().unwrap())
            });
            (l.next().unwrap(), l.next().unwrap())
        })
        .collect()
}

#[aoc(day22, part1)]
fn part1(input: &str) -> usize {
    let mut bricks = parse(input);
    let mut supported_by = HashMap::new();
    gravity(&mut bricks, Some(&mut supported_by));
    (0..bricks.len())
        .filter(|i| !supported_by.values().any(|v| v.len() == 1 && v.contains(i)))
        .count()
}

#[aoc(day22, part2)]
fn part2(input: &str) -> usize {
    let mut bricks = parse(input);
    gravity(&mut bricks, None);
    (0..bricks.len())
        .map(|i| {
            let mut bricks = bricks.clone();
            bricks.remove(i);
            gravity(&mut bricks, None)
        })
        .sum()
}

fn intersects((min1, max1): (usize, usize), (min2, max2): (usize, usize)) -> bool {
    (min1..=max1).contains(&min2)
        || (min1..=max1).contains(&max2)
        || (min2..=max2).contains(&min1)
        || (min2..=max2).contains(&max1)
}

fn gravity(
    bricks: &mut [Brick],
    mut supported_by: Option<&mut HashMap<usize, Vec<usize>>>,
) -> usize {
    bricks.sort_unstable_by_key(|&((_, _, z1), _)| z1);
    let mut in_place: HashMap<usize, Vec<usize>> = HashMap::new();
    let mut count = HashSet::new();
    for i in 0..bricks.len() {
        while bricks[i].0 .2 > 1 {
            let mut falling = true;
            let ((x1, y1, z1), (x2, y2, _)) = &bricks[i];
            for &j in in_place.get(&(z1 - 1)).unwrap_or(&vec![]) {
                let ((xx1, yy1, _), (xx2, yy2, _)) = &bricks[j];
                if intersects((*x1, *x2), (*xx1, *xx2)) && intersects((*y1, *y2), (*yy1, *yy2)) {
                    if let Some(sb) = &mut supported_by {
                        sb.entry(i).or_default().push(j);
                    }
                    falling = false;
                }
            }
            if falling {
                let ((_, _, z1), (_, _, z2)) = &mut bricks[i];
                *z1 -= 1;
                *z2 -= 1;
                count.insert(i);
            } else {
                break;
            }
        }
        in_place.entry(bricks[i].1 .2).or_default().push(i);
    }
    count.len()
}