Python

10.578 line-seconds.

import collections

from aoc23.util import assert_full_match

from .solver import Solver


def _trace_brick(x0, y0, x1, y1):
  if x0 == x1:
    y0, y1 = min(y0, y1), max(y0, y1)
    for y in range(y0, y1 + 1):
      yield (x0, y)
  elif y0 == y1:
    x0, x1 = min(x0, x1), max(x0, x1)
    for x in range(x0, x1 + 1):
      yield (x, y0)
  else:
    raise ValueError(f'not a brick: {x0}, {y0}, {x1}, {y1}')

class Day22(Solver):
  can_be_deleted: set[int]
  support_map: dict[int, list[int]]
  brick_count: int

  def __init__(self):
    super().__init__(22)

  def presolve(self, input: str):
    lines = input.splitlines()
    bricks = []
    for line in lines:
      x0, y0, z0, x1, y1, z1 = assert_full_match(r'(\d+),(\d+),(\d+)~(\d+),(\d+),(\d+)', line).groups()
      bricks.append(((int(x0), int(y0), int(z0)), (int(x1), int(y1), int(z1))))
    self.brick_count = len(bricks)
    bricks.sort(key=lambda brick: min(brick[0][2], brick[1][2]))
    self.can_be_deleted = set()
    topmost_brick_per_position: dict[tuple[int, int], tuple[int, int]] = {}
    self.support_map = {}
    for brick_id, ((x0, y0, z0), (x1, y1, z1)) in enumerate(bricks):
      support_brick_ids = set()
      support_brick_z = 0
      for (x, y) in _trace_brick(x0, y0, x1, y1):
        potential_support = topmost_brick_per_position.get((x, y))
        if not potential_support:
          continue
        if potential_support[0] > support_brick_z:
          support_brick_z = potential_support[0]
          support_brick_ids = {potential_support[1]}
        elif potential_support[0] == support_brick_z:
          support_brick_ids.add(potential_support[1])
      self.support_map[brick_id] = list(support_brick_ids)
      if len(support_brick_ids) == 1:
        self.can_be_deleted.discard(support_brick_ids.pop())
      for (x, y) in _trace_brick(x0, y0, x1, y1):
        topmost_brick_per_position[(x, y)] = (support_brick_z + 1 + z1 - z0, brick_id)
      self.can_be_deleted.add(brick_id)


  def solve_first_star(self) -> int:
    return len(self.can_be_deleted)

  def solve_second_star(self) -> int:
    reverse_support_map = collections.defaultdict(set)
    for brick_id, support_brick_ids in self.support_map.items():
      for support_brick_id in support_brick_ids:
        reverse_support_map[support_brick_id].add(brick_id)
    total = 0
    for brick_id in range(self.brick_count):
      all_destroyed_bricks = set()
      queue = [brick_id]
      while queue:
        destroy_brick_id = queue.pop(0)
        for potential_destroyed_brick in reverse_support_map[destroy_brick_id]:
          if potential_destroyed_brick in all_destroyed_bricks:
            continue
          remaining_supports = set(self.support_map[potential_destroyed_brick])
          remaining_supports -= (all_destroyed_bricks | {destroy_brick_id})
          if not remaining_supports:
            queue.append(potential_destroyed_brick)
        all_destroyed_bricks.add(destroy_brick_id)
      total += len(all_destroyed_bricks) - 1
    return total

Rust

What a nice refreshment after the past 2 days. You could say that all of these problems are graph problems at their heart, but I didn’t expect this one to turn into a graph problem as hard as it did. But even in part 1 I slowly realized that just counting some bricks won’t cut it, and I need to actually construct the graph with edges between bricks that support each other.

At that point part 2 wasn’t that much different. By traversing the graph level by level while keeping track of all bricks that have already fallen, I could identify if a new block is only supported by fallen blocks.

For representing the bricks I tried out the euclid crate for the first time and it was pretty nice to work with.

use euclid::{Point3D, Size3D, vec3, Box3D, UnknownUnit};
use ndarray::{Array2, s};
use rustc_hash::FxHashSet;

type Brick = Box3D<i32, UnknownUnit>;

fn parse_box(line: &str) -> Brick {
    let (min_s, max_s) = line.split_once('~').unwrap();
    let point = |s: &str| {
        let mut nums = s.split(',').map(|n| n.parse().unwrap());
        Point3D::new(
            nums.next().unwrap(),
            nums.next().unwrap(),
            nums.next().unwrap(),
        )
    };
    // Switch max point to be exclusive
    Box3D::new(point(min_s), point(max_s) + Size3D::splat(1))
}

fn settle(falling: &mut [Brick]) {
    falling.sort_by_key(|b| b.min.z);
    let footprint = falling.iter()
        .fold(Box3D::zero(), |acc, e| acc.union(e));
    // Initialize at height 1 which is seen as exclusive. The first brick falls to height1.
    let mut highest: Array2<i32> = Array2::ones(footprint.max.xy().to_usize().to_tuple());
    for brick in falling.iter_mut() {
        let mut brick_area = highest.slice_mut(s![brick.to_usize().x_range(), brick.to_usize().y_range()]);
        let fall_height = *brick_area.iter().max().unwrap();
        // No falling up
        assert!(fall_height <= brick.min.z);
        *brick = brick.translate(vec3(0, 0, fall_height - brick.min.z));
        brick_area.fill(brick.max.z);
    }
    falling.sort_by_key(|b| b.min.z);
}

fn get_support_graph(bricks: &[Brick]) -> (Vec<Vec<usize>>, Vec<Vec<usize>>) {
    let mut supports = vec![vec![]; bricks.len()];
    for (i, brick) in bricks.iter().enumerate() {
        // For intersection checking with above bricks
        let grown = brick.inflate(0, 0, 1);
        bricks.iter()
            .enumerate()
            .skip(i + 1)
            .take_while(|(_, b)| b.min.z <= brick.max.z)
            .filter(|(_, b)| b.min.z == brick.max.z && grown.intersects(b))
            .for_each(|(j, _b)| supports[i].push(j));
    }
    let rev: Vec<Vec<usize>> = (0..bricks.len())
        .map(|i| supports.iter()
             .enumerate()
             .filter_map(|(j, adj)| adj.contains(&i).then_some(j))
             .collect()
        )
        .collect();
    (supports, rev)
}

fn removable((supports, rev): (Vec<Vec<usize>>, Vec<Vec<usize>>)) -> u32 {
    let count = supports.iter()
        .filter(|adj| adj.iter().all(|&s| rev[s].len() > 1))
        .count();
    count as u32
}

fn fall_count((supports, rev): (Vec<Vec<usize>>, Vec<Vec<usize>>)) -> u32 {
    let mut count = 0;
    for i in 0..supports.len() {
        let mut level = FxHashSet::default();
        level.insert(i);
        // Collect all fallen bricks
        let mut fallen = level.clone();
        while !level.is_empty() {
            let mut next_lvl = FxHashSet::default();
            for &j in &level {
                for &k in &supports[j] {
                    // j supports k, i supports j via chain
                    if rev[k].iter().all(|e| fallen.contains(e)) {
                        // k is only supported by current level, it will fall
                        next_lvl.insert(k);
                    }
                }
            }
            count += next_lvl.len() as u32;
            fallen.extend(&next_lvl);
            level = next_lvl;
        }
    }
    count
}

fn part1(input: String) {
    let mut bricks: Vec<_> = input.lines().map(parse_box).collect();
    settle(&mut bricks);
    let support_graph = get_support_graph(&bricks);
    println!("{}", removable(support_graph));
}

fn part2(input: String) {
    let mut bricks: Vec<_> = input.lines().map(parse_box).collect();
    settle(&mut bricks);
    let support_graph = get_support_graph(&bricks);
    println!("{}", fall_count(support_graph));
}

util::aoc_main!("day22.txt");