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

Scala3

Not much to say about this, very straightforward implementation that was still fast enough

case class Pos3(x: Int, y: Int, z: Int)
case class Brick(blocks: List[Pos3]):
    def dropBy(z: Int) = Brick(blocks.map(b => b.copy(z = b.z - z)))
    def isSupportedBy(other: Brick) = ???

def parseBrick(a: String): Brick = a match
    case s"$x1,$y1,$z1~$x2,$y2,$z2" => Brick((for x <- x1.toInt to x2.toInt; y <- y1.toInt to y2.toInt; z <- z1.toInt to z2.toInt yield Pos3(x, y, z)).toList)

def dropOn(bricks: List[Brick], brick: Brick): (List[Brick], List[Brick]) =
    val occupied = bricks.flatMap(d => d.blocks.map(_ -> d)).toMap

    @tailrec def go(d: Int): (Int, List[Brick]) =
        val dropped = brick.dropBy(d).blocks.toSet
        if dropped.intersect(occupied.keySet).isEmpty && !dropped.exists(_.z <= 0) then
            go(d + 1)
        else
            (d - 1, occupied.filter((p, b) => dropped.contains(p)).map(_._2).toSet.toList)
    
    val (d, supp) = go(0)
    (brick.dropBy(d) :: bricks, supp)

def buildSupportGraph(bricks: List[Brick]): Graph[Brick, DiEdge[Brick]] =
    val (bs, edges) = bricks.foldLeft((List[Brick](), List[DiEdge[Brick]]()))((l, b) => 
        val (bs, supp) = dropOn(l._1, b)
        (bs, supp.map(_ ~> bs.head) ++ l._2)
    )
    Graph() ++ (bs, edges)

def parseSupportGraph(a: List[String]): Graph[Brick, DiEdge[Brick]] =
    buildSupportGraph(a.map(parseBrick).sortBy(_.blocks.map(_.z).min))

def wouldDrop(g: Graph[Brick, DiEdge[Brick]], b: g.NodeT): Long =
    @tailrec def go(shaking: List[g.NodeT], falling: Set[g.NodeT]): List[g.NodeT] = 
        shaking match
            case h :: t => 
                if h.diPredecessors.forall(falling.contains(_)) then
                    go(h.diSuccessors.toList ++ t, falling + h)
                else
                    go(t, falling)
            case _ => falling.toList
    
    go(b.diSuccessors.toList, Set(b)).size

def task1(a: List[String]): Long = parseSupportGraph(a).nodes.filter(n => n.diSuccessors.forall(_.inDegree > 1)).size
def task2(a: List[String]): Long = 
    val graph = parseSupportGraph(a)
    graph.nodes.toList.map(wouldDrop(graph, _) - 1).sum

Zig

https://github.com/Treeniks/advent-of-code/blob/master/2023/day22/zig/src/main.zig

(or on codeberg if you don't like to use github: https://codeberg.org/Treeniks/advent-of-code/src/branch/master/2023/day22/zig/src/main.zig )

Every time I use Zig, I love the result, but I hate writing it. The language is just a little too inflexible for quick and dirty solutions to quickly try out an idea or debug print something useful, but once you're done and have a result, it feels quite complete.

C

Part 1 was fun, essentially a matter of mapping a grid and implementing a function to scan above and below bricks.

Was worried part 2 would either make the grid approach impossible (large numbers) or have combinatory complexity that would necessitate some super efficient dependency table that I don't know about. Luckily that wasn't the case! Phew.

https://github.com/sjmulder/aoc/blob/master/2023/c/day22.c