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

deleted by creator

Nim

I sorted the bricks by their lower Z coordinate, then tried to move each of them downward, doing collision checks against all the others along the way. Once a level with collisions was found, I recorded each colliding brick as a supporter of the falling brick.

For part 1, I made another table of which other bricks each brick was supporting. Any bricks that weren’t the sole support for any other bricks were counted as safe to disintegrate.

For part 2, I sorted the bricks again after applying gravity. For each brick, I included it in a set of bricks that would fall if it were removed, then checked the others further down the list to see if they had any non-falling supporters. Those that didn’t would be added to the falling set.

Initially I was getting an answer for part 2 that was too high. I turned out that I was counting bricks that were on the ground as being unsupported, so some of them were getting included in the falling sets for their neighbors. Adding a z-level check fixed this.

Both of these have room for optimization, but non-debug builds run 0.5s and 1.0s respectively, so I didn’t feel the need to write an octree implementation or anything.

• Day 22, part 1
• Day 22, part 2