Advent of Code 2023 - Day 18, in Kotlin - Lavaduct Lagoon • Todd Ginsberg

I am not a huge fan of the mostly math-based puzzles. Days like today are not my favorite, but it’s a good learning opportunity for me. I started off on the right track, after remembering how some people solved Day 10 , but ended up getting frustrated with off-by-two errors and ended up seeking help from Reddit to understand why. I’ll try my best to explain the math. :)

If you’d rather just view the code, my GitHub Repository is here.

Puzzle Input

Today we’ll take our input as a List<String> and declare it as a property, because we’ll need to parse it twice, one for each part of the puzzle.

class Day18(private val input: List<String>) {

}

⭐ Day 18, Part 1

The puzzle text can be found here.

Before we get too far into what we’re doing today, we need to make an addition to our Point2D class. It will become handy to be able to multiply a Point2D, usually referencing an offset by some integer. So we’ll define an operator on Point2D to do just that. Its implementation simply multiplies the coordinates by the amount specified.

// In Point2D

operator fun times(amount: Int): Point2D =
    Point2D(x * amount, y * amount)

Next, we’ll write a parser for part 1. It takes a single row of input and returns a Pair<Point2D, Int> where the Point2D is an offset representing the direction to go, and the Int represents the distance.

// In Day18

private fun parseRowPart1(input: String): Pair<Point2D, Int> =
    when (input[0]) {
        'U' -> NORTH
        'D' -> SOUTH
        'L' -> WEST
        'R' -> EAST
        else -> throw IllegalStateException("Bad direction $input")
    } to input.substringAfter(" ").substringBefore(" ").toInt()

We’ll use the substringAfter and substringBefore trick we’ve used a few times already to parse out what we need.

Next, the part that took me a really long time to get right and actually understand - calculating the lava volume. Thankfully, lava is only one unit deep, so we don’t have to do any three-dimensional math here.

// In Day18

private fun calculateLava(instructions: List<Pair<Point2D, Int>>): Long {
    val area = instructions
        .runningFold(ORIGIN) { acc, (direction, distance) ->
            acc + (direction * distance)
        }
        .zipWithNext()
        .sumOf { (a, b) ->
            (a.x.toLong() * b.y.toLong()) - (a.y.toLong() * b.x.toLong())
        } / 2
    val perimeter = instructions.sumOf { it.second }
    return area + (perimeter / 2) + 1
}

The first part of this function uses the Shoelace Formula to calculate the area of the lava pit. The runningFold is like a normal fold except it keeps all of the transitive values. This lets us create a List<Point2D> which represents all of the actual points on the outside of the lava pit. Each instruction gives us the direction from the last point and the distance to travel and the fold part gives us the previously calculated value (a point). This allows us to string all of the points together beginning and ending with 0,0 (the ORIGIN). This is important for later. The Shoelace Formula asks us to perform some math on each pair of points in the list, so we use zipWithNext in order to pair them together. Taking the sumOf the reciprocal differences gives us the area. Note here we convert these x and y values of the points toLong because we’ll need them that way in part 2.

The perimeter of the lava pit is the sumOf all the distances in the instructions.

This last part is the part that gave me the most trouble. I was trying to follow Pick’s Theorem without really knowing what I was doing. I was constantly off by 2 implementing it the way wikipedia had it. Pick’s Theorem is A = i + b/2 - 1 where A is the area, i is the number of points inside the polygon, b is the number of points on the outside of the polygon. The thing I didn’t realize is that we aren’t trying to calculate A. We have A from the Shoelace Formula. We’re really trying to calculate b+i, and if you rearrange the formula for that, you end up with i + b = A + b/2 + 1. That’s why we add 1 rather than subtract it, and that’s why this works at all. I will fully admit that I got my stars by just saying “well, I’m off by 2 on the example, lets see if that holds true for the actual input”. Not the best way to earn stars, but at least I know why that worked now.

Calling this with the input parsed for part 1 gives us our answer to part 1.

// In Day18

fun solvePart1(): Long =
    calculateLava(input.map { parseRowPart1(it) })

Star earned (with some math theory help from Reddit)! Onward!

⭐ Day 18, Part 2

The puzzle text can be found here.

Part 2 uses the same algorithm as part 1 except the numbers are parsed differently and are much larger. This is why we defined our calculateLava function to use Long rather than Int.

// In Day18

private fun parseRowPart2(input: String): Pair<Point2D, Int> =
    with(input.substringAfter("#").substringBefore(")")) {
        when (last()) {
            '0' -> EAST
            '1' -> SOUTH
            '2' -> WEST
            '3' -> NORTH
            else -> throw IllegalStateException("Bad direction $input")
        } to dropLast(1).toInt(16)
    }

The call to calculateLava is the same except for the new values.

// In Day18

fun solvePart2(): Long =
    calculateLava(input.map { parseRowPart2(it) })

Star earned! See you tomorrow!

⭐ Day 18, Part 1

⭐ Day 18, Part 2

Further Reading