Day 22: Sand Slabs

Puzzle description

https://adventofcode.com/2023/day/22

Model

Before delving into the solution, let's familiarize ourselves with the representation of bricks.. We have two case classes: Coordinate to denote a point in the three-dimensional space, and Brick to define a brick with starting and ending coordinates.

case class Coordinate(x: Int, y: Int, z: Int)

case class Brick(start: Coordinate, end: Coordinate)

Part 1

Parsing the input

The parse method employs pattern matching and string interpolation to extract starting and ending coordinates from a multi-line string representation of bricks. It iterates over each line, deconstructs it into coordinate values using pattern matching, and constructs a sequence of Brick objects with the parsed coordinates.

def parse(input: String): Seq[Brick] =
  for
    s"$x1,$y1,$z1~$x2,$y2,$z2" <- input.split('\n')
  yield
    val start = Coordinate(x1.toInt, y1.toInt, z1.toInt)
    val end = Coordinate(x2.toInt, y2.toInt, z2.toInt)
    Brick(start, end)

Brick methods

There are two fundamental operations on the Bricks that form the backbone of our solution: moving the brick down, and determining whether the brick collides with another one.

To facilitate the movement of bricks downward, the moveDown method is employed. This operation involves adjusting the z value of the brick's coordinates.

lazy val moveDown: Brick =
  copy(
    start = start.copy(z = start.z - 1),
    end = end.copy(z = end.z - 1)
  )

Another vital operation involves determining whether two bricks collide with each other. 3D collision is analogous to 1D collision, so let's start with that.

1D line segments on X axis collide with each other when:

maxX >= otherMinX && otherMaxX >= minX

We are not guaranteed the order of coordinates, so we have to determine min values and max values ourselves. Let's express it as a method on the Brick:

def xOverlaps(other: Brick) = {
  val minX = start.x min end.x
  val maxX = start.x max end.x
  val otherMinX = other.start.x min other.end.x
  val otherMaxX = other.start.x max other.end.x
  maxX >= otherMinX && otherMaxX >= minX
}

To extend this to a 3D collision, we apply the same logic for the y and z axes. To avoid code repetition, we introduce an axis: Coordinate => Int extractor that extracts a coordinate value from a Brick. The updated method is as follows:

def axisOverlaps(other: Brick)(axis: Coordinate => Int) = {
  val min = axis(start) min axis(end)
  val max = axis(start) max axis(end)
  val otherMin = axis(other.start) min axis(other.end)
  val otherMax = axis(other.start) max axis(other.end)
  max >= otherMin && otherMax >= min
}

Now, to determine a 3D collision, we create a method that uses the axisOverlaps defined above for each axis:

def collidesWith(other: Brick): Boolean =
  axisOverlaps(other)(_.x) &&
    axisOverlaps(other)(_.y) &&
    axisOverlaps(other)(_.z)

Dropping groups of bricks

As the input is a snapshot of falling bricks, we must first drop them all to a stationary position.

First, define a way to check if a brick has collided with the ground, determined with a simple check on the z axis:

def collidesWithGround(brick: Brick): Boolean =
  brick.start.z == 0 || brick.end.z == 0

Next, since we will determine the collisions at this point, we'll create a Map that will associate each brick with the bricks supporting it.

Let's define the dropBricks function that can do this:

import scala.collection.mutable

def dropBricks(bricks: Seq[Brick]): Map[Brick, Set[Brick]] = {

First, sort the bricks by the z axis to handle the falling order. This is necessary because the input doesn't guarantee the order of the bricks:

  val bricksByZAsc = bricks.sortBy(brick => (brick.start.z) min (brick.end.z))

Next, initialize the Stack of bricks to drop and the Map of already dropped ones:

  val remainingBricks = mutable.Stack.from(bricksByZAsc)
  val droppedBricks = mutable.Map[Brick, Set[Brick]]()

Then, loop over the remaining bricks with while (remainingBricks.nonEmpty).

  while (remainingBricks.nonEmpty) {

On each iteration, simulate the fall of a single brick:

    val brick = remainingBricks.pop()
    val brickMovedDown = brick.moveDown

First, determine if there are any colliding bricks from the currently known droppedBricks. We can produce this as a Set, with contents determined using the previously defined Brick#collidesWith method:

    val collidingBricks =
      droppedBricks.keys.filter(brickMovedDown.collidesWith).toSet

Now, determine whether the brick is stationary. "Stationary" means that it either collides with the ground or another brick. If it is stationary, put it into the droppedBricks along with the dropped bricks that collide with it. If not, put it back into the remainingBricks to move it further down in the next step:

    if (collidesWithGround(brickMovedDown) || collidingBricks.nonEmpty)
      droppedBricks.put(brick, collidingBricks)
    else
      remainingBricks.push(brickMovedDown)
  }

After all the bricks finish falling, return the droppedBricks by converting to an immutable Map.

  droppedBricks.toMap
}

Determining the disintegrable bricks

Now, let's get back to the core challenge. We want to figure out how many bricks we can safely disintegrate. A brick is considered disintegrable if it's not the sole support for another brick. Using our map that outlines which bricks support others, we can easily identify the opposite – bricks that we cannot disintegrate. All remaining bricks are safe for disintegration:

def getDisintegrableBricks(brickToSupportingBricks: Map[Brick, Set[Brick]]): Set[Brick] = {
  val nonDisintegrableBricks = brickToSupportingBricks.values.collect {
    case supporting if supporting.sizeIs == 1
      supporting.head // the only brick that holds the brick above
  }.toSet
  brickToSupportingBricks.keySet diff nonDisintegrableBricks
}

Bringing it all together, we get the solution for Part 1:

def part1(input: String): Int = {
  val bricks = parse(input)
  val brickToSupportingBricks = dropBricks(bricks)
  val disintegrableBricks = getDisintegrableBricks(brickToSupportingBricks)
  disintegrableBricks.size
}

Part 2

Part 2 builds upon the code from Part 1 with the introduction of a new functionality: calculating the total number of bricks that will fall after the removal of a specific brick. To accomplish this, we'll define the countFallingChain function. We'll utilize brickToSupportingBricks and brick as function arguments.

def countFallingChain(brickToSupportingBricks: Map[Brick, Set[Brick]])(brick: Brick): Int = {

Initially, we set up the collection of disintegratedBricks, remainingBricks to check, and a flag to determine the completion of the chain reaction:

  val disintegratedBricks = mutable.Set[Brick](brick)
  var remainingBricks = brickToSupportingBricks.removed(brick)
  var isChainReactionFinished = false

Next, loop while the chain reaction is not finished

  while (!isChainReactionFinished) {

In each iteration of the loop, we identify the bricks that have fallen (considered disintegrated) and those that remain untouched:

    val (newDisintegratedBricks, newRemainingBricks) = remainingBricks
      .partition { (_, supportingBricks) =>
        supportingBricks.nonEmpty && supportingBricks.subsetOf(disintegratedBricks)
      }

If no bricks have fallen, indicating the completion of the chain reaction, we conclude the process. Otherwise, we add all the fallen bricks to disintegratedBricks and update remainingBricks for further checking:

    if (newDisintegratedBricks.isEmpty)
      isChainReactionFinished = true
    else
      disintegratedBricks.addAll(newDisintegratedBricks.keySet)
      remainingBricks = newRemainingBricks
  }

Finally, after the chain reaction is complete, we return the count of disintegrated bricks, excluding the initial one:

  disintegratedBricks.size - 1 // don't include the initial brick
}

With countFallingChain defined, we can utilize it to calculate the falling chain for each brick:

val fallingChainCounts = brickToSupportingBricks.keys.toList.map(
  countFallingChain(brickToSupportingBricks)
)

It's important to highlight the use of .toList in this context. The keys method returns an Iterable, which is a Set underneath. By converting it to a list, we ensure that each count is preserved independently. Without this conversion, if multiple bricks have the same falling chain count, some counts may be lost.

By combining these individual chain counts and summing them up, we arrive at the answer for Part 2:

def part2(input: String): Int = {
  val bricks = parse(input)
  val brickToSupportingBricks = dropBricks(bricks)
  val fallingChainCounts = brickToSupportingBricks.keys.toList.map(
    countFallingChain(brickToSupportingBricks)
  )
  fallingChainCounts.sum
}

Final code

case class Coordinate(x: Int, y: Int, z: Int)

case class Brick(start: Coordinate, end: Coordinate) {

  lazy val moveDown: Brick =
    copy(
      start = start.copy(z = start.z - 1),
      end = end.copy(z = end.z - 1)
    )

  def collidesWith(other: Brick): Boolean =
    axisOverlaps(other)(_.x) &&
      axisOverlaps(other)(_.y) &&
      axisOverlaps(other)(_.z)

  private def axisOverlaps(other: Brick)(axis: Coordinate => Int) = {
    val min = axis(start) min axis(end)
    val max = axis(start) max axis(end)
    val otherMin = axis(other.start) min axis(other.end)
    val otherMax = axis(other.start) max axis(other.end)
    max >= otherMin && otherMax >= min
  }
}

def parse(input: String): Seq[Brick] =
  for s"$x1,$y1,$z1~$x2,$y2,$z2" <- input.split('\n')
    yield
      val start = Coordinate(x1.toInt, y1.toInt, z1.toInt)
      val end = Coordinate(x2.toInt, y2.toInt, z2.toInt)
      Brick(start, end)

import scala.collection.mutable

def dropBricks(bricks: Seq[Brick]): Map[Brick, Set[Brick]] = {
  val bricksByZAsc = bricks.sortBy(brick => (brick.start.z) min (brick.end.z))
  val remainingBricks = mutable.Stack.from(bricksByZAsc)
  val droppedBricks = mutable.Map[Brick, Set[Brick]]()

  while (remainingBricks.nonEmpty) {
    val brick = remainingBricks.pop()
    val brickMovedDown = brick.moveDown
    val collidingBricks =
      droppedBricks.keys.filter(brickMovedDown.collidesWith).toSet
    if (collidesWithGround(brickMovedDown) || collidingBricks.nonEmpty)
      droppedBricks.put(brick, collidingBricks)
    else
      remainingBricks.push(brickMovedDown)
  }

  droppedBricks.toMap
}

def collidesWithGround(brick: Brick): Boolean =
  brick.start.z == 0 || brick.end.z == 0

def getDisintegrableBricks(brickToSupportingBricks: Map[Brick, Set[Brick]]): Set[Brick] = {
  val nonDisintegrableBricks = brickToSupportingBricks.values.collect {
    case supporting if supporting.sizeIs == 1 =>
      supporting.head // the only brick that holds the brick above
  }.toSet
  brickToSupportingBricks.keySet diff nonDisintegrableBricks
}

def part1(input: String): Int = {
  val bricks = parse(input)
  val brickToSupportingBricks = dropBricks(bricks)
  val disintegrableBricks = getDisintegrableBricks(brickToSupportingBricks)
  disintegrableBricks.size
}

def countFallingChain(brickToSupportingBricks: Map[Brick, Set[Brick]])(brick: Brick): Int = {
  val disintegratedBricks = mutable.Set[Brick](brick)
  var remainingBricks = brickToSupportingBricks.removed(brick)
  var isChainReactionFinished = false

  while (!isChainReactionFinished) {
    val (newDisintegratedBricks, newRemainingBricks) = remainingBricks
      .partition { (_, supportingBricks) =>
        supportingBricks.nonEmpty && supportingBricks.subsetOf(
          disintegratedBricks
        )
      }
    if (newDisintegratedBricks.isEmpty)
      isChainReactionFinished = true
    else
      disintegratedBricks.addAll(newDisintegratedBricks.keySet)
      remainingBricks = newRemainingBricks
  }

  disintegratedBricks.size - 1 // don't include the initial brick
}

def part2(input: String): Int = {
  val bricks = parse(input)
  val brickToSupportingBricks = dropBricks(bricks)
  val fallingChainCounts = brickToSupportingBricks.keys.toList.map(
    countFallingChain(brickToSupportingBricks)
  )
  fallingChainCounts.sum
}

Solutions from the community

Solution by Rui Alves
Solution by Raymond Dodge

Share your solution to the Scala community by editing this page. You can even write the whole article! See here for the expected format

Day 22: Sand Slabs

Puzzle description​

Model​

Part 1​

Parsing the input​

Brick methods​

Dropping groups of bricks​

Determining the disintegrable bricks​

Part 2​

Final code​

Solutions from the community​