By Eric Burden | December 22, 2023

It’s that time of year again! Just like last year, I’ll be posting my solutions to the Advent of Code puzzles. This year, I’ll be solving the puzzles in Kotlin. I’ll post my solutions and code to GitHub as well. If you haven’t given AoC a try, I encourage you to do so along with me!

# Day 22 - Sand Slabs

Find the problem description HERE.

## The Input - A Brick of What?

Today, our input is a bunch of bricks, each of which can be represented by a group of “voxels”, or really just chunky points in 3D space. So, that’s how I’ll proceed: Parse each line into a list of cubes and bundle those lists into a brick.

```
/**
* This class represents on cubic component of a [BrickOfSand]
*
* @property x This cube's x-coordinate.
* @property y This cube's y-coordinate.
* @property z This cube's z-coordinate.
*/
data class SandCube(val x: Int, val y: Int, val z: Int)
/**
* This class represents a solid brick of sand
*
* I have no idea how the elves were able to get the sand to actually stay
* in "brick" form. Christmas magic?
*
* @property cubes The cubes that, stuck together, comprise this brick of sand.
*/
data class BrickOfSand(val cubes: List<SandCube>) {
companion object {
/**
* Parse a [BrickOfSand] from an input line
*
* @param str The input line representing a brick of sand.
* @return The [BrickOfSand] represented by `str`.
* @throws Exception When the input cannot be parsed.
*/
fun fromString(str: String): BrickOfSand {
val regex = Regex("""(\d),(\d),(\d+)~(\d),(\d),(\d+)""")
val matches =
regex.find(str)?.groupValues?.drop(1)?.map { it.toInt() }
?: throw Exception("Could not parse $str into a [BrickOfSand]!")
// Apparently you can't destructure 6 things at once from a list.
val (x1, y1, z1) = matches
val (x2, y2, z2) = matches.drop(3)
// Depending on _which_ dimension changes from the first cube to the
// last cube, produce a list of cubes from the front to the back
// of this brick.
val cubes = when {
x2 > x1 -> (x1..x2).map { x -> SandCube(x, y1, z1) }
x1 > x2 -> (x2..x1).map { x -> SandCube(x, y1, z1) }
y2 > y1 -> (y1..y2).map { y -> SandCube(x1, y, z1) }
y1 > y2 -> (y2..y1).map { y -> SandCube(x1, y, z1) }
z2 > z1 -> (z1..z2).map { z -> SandCube(x1, y1, z) }
z1 > z2 -> (z2..z1).map { z -> SandCube(x1, y1, z) }
else -> listOf(SandCube(x1, y1, z1)) // Tiny brick!
}
return BrickOfSand(cubes)
}
}
}
class Day22(input: List<String>) {
// Parse that list into bricks!
private val parsed =
input.filter { it.isNotEmpty() }.map(BrickOfSand::fromString)
}
```

## Part One - Pile So High

So, let me get this straight. The problem here is that we have *bricks* of sand
instead of, like, ya know, *grains*. And these bricks are magically stabilized
so that they won’t tip off the top of a stack line normal physics demands? Has
anyone considered that, perhaps, magically stabilizing the sand into bricks is
the thing that we should stop doing? No, that’s just me? Ok, well, we’ve got
the bricks now, let’s figure out what to do with them.

```
data class SandCube(val x: Int, val y: Int, val z: Int)
data class BrickOfSand(val cubes: List<SandCube>) {
// companion object { ... }
/**
* Drop this brick by a given amount along the z-axis
*
* This is the function used to simulate dropping the brick from where it
* starts to where it lands.
*
* @param amount How many steps along the z-axis to drop this brick.
* @return A copy of this brick, dropped along the z-axis.
*/
fun dropBy(amount: Int): BrickOfSand {
val cubes = cubes.map { (x, y, z) -> SandCube(x, y, z - amount) }
return BrickOfSand(cubes)
}
}
/**
* This class represents the pile of sand bricks
*
* The topographical map is mostly used for building up the pile of bricks,
* although it was nice to be able to print it out to verify that bricks were
* going where I thought they were.
*
* @property bricks A list of the bricks in the pile, in the order that the
* bricks are added to the pile.
* @property topoMap A 2D grid representing the height of the pile at each
* x/y-coordinate.
* @property spaceMap A mapping of each occupied cube to the brick that owns
* that cube.
*/
data class SandBrickPile(
val bricks: MutableList<BrickOfSand> = mutableListOf(),
val topoMap: List<MutableList<Int>> = List(10) { MutableList(10) { 1 } },
val spaceMap: MutableMap<SandCube, BrickOfSand> = mutableMapOf()
) {
/**
* Add a brick to the pile
*
* Drop a brick from it's starting position until it settles. Update the
* list of bricks, topographic map, and spatial map of bricks to accommodate.
*
* @param brick The brick to drop
*/
fun addBrick(brick: BrickOfSand) {
// Figure out how far we can drop this brick by checking the height
// of the topographic map underneath this falling brick. Then, drop
// this brick by the minimum distance between a brick cube and the
// tallest stack underneath.
val dropToZ = brick.cubes.maxOf { (x, y, _) -> topoMap[y][x] }
val dropByAmt = brick.cubes.minOf { (_, _, z) -> z - dropToZ }
val droppedBrick = brick.dropBy(dropByAmt)
// Add it to the list
bricks.add(droppedBrick)
// Update the topographical map
droppedBrick.cubes.forEach { (x, y, z) -> topoMap[y][x] = z + 1 }
// Update the spatial map
droppedBrick.cubes.forEach { cube -> spaceMap[cube] = droppedBrick }
}
/**
* Identify the bricks above the current brick (in contact)
*
* Get all the bricks resting on the brick being considered. A brick
* that's long on the z-axis would include itself, so those need to
* be filtered out.
*
* @param brick The brick to check for bricks above.
* @return The list of bricks above the current brick.
*/
private fun bricksAbove(brick: BrickOfSand) =
brick.cubes.mapNotNull { (x, y, z) ->
spaceMap[SandCube(x, y, z + 1)]
}.filter { it != brick }
/**
* Identify the bricks below the current brick (in contact)
*
* Get all the bricks supporting the brick being considered. A brick
* that's long on the z-axis would include itself, so those need to
* be filtered out.
*
* @param brick The brick to check for bricks above.
* @return The list of bricks above the current brick.
*/
private fun bricksBelow(brick: BrickOfSand) =
brick.cubes.mapNotNull { (x, y, z) ->
spaceMap[SandCube(x, y, z - 1)]
}.filter { it != brick }
/**
* Check to see if the target brick can be safely disintegrated
*
* A brick can be safely disintegrated if removing it wouldn't cause any
* other bricks to fall and create a cascade of sandy blocks of doom.
*/
fun canDisintegrate(brick: BrickOfSand): Boolean {
// If all of the bricks above are resting on at least one other brick,
// this brick can be disintegrated. The `all` function will return true
// if `bricksAbove` is empty, as well.
return bricksAbove(brick).all { brickAbove ->
bricksBelow(brickAbove).any { brickBelow -> brickBelow != brick }
}
}
}
/**
* Convert a list of sand bricks to a pile of sand bricks
*/
fun List<BrickOfSand>.pileUp(): SandBrickPile {
val pile = SandBrickPile()
// We need to sort the incoming bricks by the z axis so that we don't end
// up trying to drop a brick inside a pile that's already piled up past where
// that brick starts.
sortedBy { brick -> brick.cubes.minOf { it.z } }.forEach { pile.addBrick(it) }
return pile
}
class Day22(input: List<String>) {
// private val parsed = ...
// For part one, we pile up the bricks and see how many we could eliminate
// without unsettling the pile.
fun solvePart1(): Int {
val pile = parsed.pileUp()
return pile.bricks.count { brick -> pile.canDisintegrate(brick) }
}
}
```

Ok, I’m feeling pretty good about this problem representation. This is nice.

## Part Two - Another Brick In The Pile

Ok, *now* we’re about to have fun! It’s time to tip this pile over. Wait, no,
it’s not? We’re just going to simulate what would happen if we knocked the pile
over? Ah, man…

```
data class SandCube(val x: Int, val y: Int, val z: Int)
data class BrickOfSand(val cubes: List<SandCube>) {
// companion object { ... }
// fun dropBy(amount: Int): BrickOfSand { ... }
}
data class SandBrickPile(
val bricks: MutableList<BrickOfSand> = mutableListOf(),
val topoMap: List<MutableList<Int>> = List(10) { MutableList(10) { 1 } },
val spaceMap: MutableMap<SandCube, BrickOfSand> = mutableMapOf()
) {
// fun addBrick(brick: BrickOfSand) { ... }
// private fun bricksAbove(brick: BrickOfSand) = ...
// private fun bricksBelow(brick: BrickOfSand) = ...
// fun canDisintegrate(brick: BrickOfSand): Boolean { ... }
/**
* Count the number of bricks that would fall if the target brick is removed
*
* @param keystone The brick being removed.
*/
fun bricksDependingOn(keystone: BrickOfSand): Int {
// We're going to do a depth-first search starting with the keystone
// and working up the pile, adding bricks that will fall to our set
// of fallen bricks.
val stack = mutableListOf(keystone)
val fallenBricks = mutableSetOf<BrickOfSand>()
while (stack.isNotEmpty()) {
// Get the current brick to check off the top of the stack. If
// we've somehow already checked this one, skip it. Otherwise,
// add it to the set of fallen bricks.
val brick = stack.removeLast()
if (brick in fallenBricks) continue
fallenBricks.add(brick)
// Now get all the bricks that will fall if `brick` is
// removed
val nowFalling =
bricksAbove(brick).filter { brickAbove ->
bricksBelow(brickAbove).all { it in fallenBricks }
}
// For each brick that is now falling, add it to the stack for
// future consideration, unless it's already been considered.
for (newFallingBrick in nowFalling) {
if (newFallingBrick in fallenBricks) continue
stack.add(newFallingBrick)
}
}
// Don't forget we don't count the original brick being removed
return fallenBricks.size - 1
}
}
// fun List<BrickOfSand>.pileUp(): SandBrickPile { ... }
class Day22(input: List<String>) {
// private val parsed = ...
// fun solvePart1(): Int { ... }
// For part two, we pile up the bricks (again) and start dropping bricks to
// see how many fall!
fun solvePart2(): Int {
val pile = parsed.pileUp()
return pile.bricks.sumOf { brick -> pile.bricksDependingOn(brick) }
}
}
```

There they go! Well, I’m visualizing what it would be like, at any rate.

## Wrap Up

Today was a nice, implementation-heavy day, by which I mean it was a matter of
correctly modeling the behaviors described as opposed to some neat math trick.
In positive news, the *same* algorithm that solves the examples works on the
input!!! Yay! This was a nice step-down in difficulty from yesterday, I think.