Advent of Code 2023 - Day 10, in Kotlin - Pipe Maze • Todd Ginsberg

It’s a good thing it rained here today, because a bug in part 2 took me a non-trivial amount of time to figure out. I was really close initially, but finding the bug took me a long time and some diagramming by hand.

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

Puzzle Input

We’ll take our input as, once again, a List<String> and convert it to a grid. We don’t need to define input as a property as we won’t need to refer to it again.

class Day10(input: List<String>) {

    private val grid: Array<CharArray> = 
        input.map { it.toCharArray() }.toTypedArray()

    private val start: Point2D = 
        grid.indexOfFirst { 'S' in it }.let { y ->
            Point2D(grid[y].indexOf('S'), y)
        }
}

The grid will be an Array<CharArray> so we can alter the grid during part 2. We do this conversion by mapping each row of input toCharArray and then converting the resulting List<CharArray> to Array<CharArray> via toTypedArray. Yes, we could leave it alone because we don’t replace whole rows, just individual spots in the grid, but my preference was to use arrays for both. We could also have gone with List<MutableList<Char>>.

The start point is a Point2D (see previously written code) and is found by hunting through the grid. We do that by taking the indexOfFirst row that contains S, and then finding the indexOf the S on that row. Convert the x and y values resulting from that to a Point2D and we have the start.

Helper Extensions for Grid

Since grid-based puzzles are somewhat common in Advent of Code, and I tend to write most of them using Array<CharArray>, let’s define some helper functions to make our code look a bit cleaner. We’ll add three extension functions on Array<CharArray>…

// In Extensions

fun Array<CharArray>.isSafe(at: Point2D) =
    at.y in this.indices && at.x in this[at.y].indices

operator fun Array<CharArray>.set(at: Point2D, c: Char) {
    this[at.y][at.x] = c
}

operator fun Array<CharArray>.get(at: Point2D): Char =
    this[at.y][at.x]

The first function, isSafe, lets us know if a Point2D is within the bounds of the grid. It does this by looking at the indicies, which are returned as ranges and seeing if both x and y are within the corresponding indicies range.

The next two functions, get and set are defined as operators and let us write grid[spot] = value instead of grid[spot.y][spot.x] = value, and write value = grid[spot] instead of value = grid[spot.y][spot.x]. I think this makes our code look nice and clean, but it’s not required if you don’t like the level of indirection.

Making Point2D More Useful

We will be doing a fair deal of work with Point2D today so let’s make working with them easier.

First up, in the companion object of Point2D, let’s define some offsets for the cardinal directions. If we’re moving NORTH, we are subtracting 1 from the y axis value and leaving x alone, for example. Using these will help make our code easier to understand later.

// In Point2D

companion object {
    val NORTH = Point2D(0, -1)
    val EAST = Point2D(1, 0)
    val SOUTH = Point2D(0, 1)
    val WEST = Point2D(-1, 0)
}

In order to make using these offsets easier, let’s go ahead and define the plus and minus operators on Point2D. This will allow us to add or subtract Point2D objects from one another.

// In Point2D

operator fun minus(other: Point2D): Point2D =
    Point2D(x - other.x, y - other.y)

operator fun plus(other: Point2D): Point2D =
    Point2D(x + other.x, y + other.y)

And finally, since today’s puzzle doesn’t have any diagonals involved, we’re going to have to write a cardinalNeighbors function similar to the Point2D.neighbors() function we already have. Since we have directional offsets defined, we can write these as additions to the current location…

// In Point2D

fun cardinalNeighbors(): Set<Point2D> =
    setOf(
        this + NORTH,
        this + EAST,
        this + SOUTH,
        this + WEST
    )

Yes, we probably should go reimplement neighbors() to use the offset addition method, as well as constants for NE/NW/SE/SW. I’ll do that but not show it here.

The fun part is because we’ve implemented plus, these offsets compose (val NORTH_EAST = NORTH + EAST).

⭐ Day 10, Part 1

The puzzle text can be found here.

Strategy

If you think about it, each circular path is going to always have an even number of steps. Meaning, the farthest point out will be the total length divided by 2. So what we are going to do is traverse the pipeline, storing each unique Point2D that makes it up. Once we have that, we count them up and divide by 2.

Why do we have to store anything? Why can’t we just begin at the start and keep traversing until we end up back at start and return the count? Because part 2 needs all of the parts of the pipe, so we’ll implement part 1 in a way that gives us all the points and reuse it later.

As for traversal, how should we do that? There are only a certain number of movements within the pipe that are even possible. For example, if we’re traveling SOUTH and are on a | shape, we want to keep going SOUTH. Another example: If we are moving WEST and run into a L, we want to end up going NORTH. There are only a few of these rules so let’s encode them in a map of movements. The key to the map will be a Pair<Char,Point2D> where the Char is the symbol we’re currently on and the Point2D was the direction we came from to get there. The value of the map is a Point2D which indicates which direction we face after moving to the symbol.

// In Day10

private val movements: Map<Pair<Char, Point2D>, Point2D> =
    mapOf(
        ('|' to SOUTH) to SOUTH,
        ('|' to NORTH) to NORTH,
        ('-' to EAST) to EAST,
        ('-' to WEST) to WEST,
        ('L' to WEST) to NORTH,
        ('L' to SOUTH) to EAST,
        ('J' to SOUTH) to WEST,
        ('J' to EAST) to NORTH,
        ('7' to EAST) to SOUTH,
        ('7' to NORTH) to WEST,
        ('F' to WEST) to SOUTH,
        ('F' to NORTH) to EAST
    )

Implementation

We have enough information to write our traversePipe function. We start by setting up a MutableSet with the start in it to record which parts of the pipe we’ve seen already.

We also need to do some calculations on which way to move from S since it is puzzle-dependent. We look at the start position and get its cardinalNeighbors, taking care to filter for the ones neighbors that are safe to move to. To find the spot next to the start that we’re going to move to first, we find the first neighbor that has a valid movement rule.

// In Day10

private fun traversePipe(): Set<Point2D> {
    val pipe = mutableSetOf(start)
    var current = start
        .cardinalNeighbors()
        .filter { grid.isSafe(it) }
        .first {
            val d = it - start
            (grid[it] to d in movements)
        }
    var direction = current - start
    while (current != start) {
        pipe += current
        movements[grid[current] to direction]?.let { nextDirection ->
            direction = nextDirection
            current += direction
        } ?: error("Invalid movement detected: $current, $direction")
    }
    return pipe
}

Once we know where S leads us we store it in current and then calculate what the direction is by subtracting start from the current spot.

Then we iterate until we lap back around to the start. Within our loop, we add any current spot we see to the pipe set. Then we consult the movements map to figure out where to go next. We set the nextDirection (which, remember, is an offset) to the direction we’re moving, and add it to the current spot to move the current pointer along the pipeline.

Once this is done, we return the pipe which now contains all of the spots in the pipeline. Get the size of this set and divide it by 2 and we have the answer for part 1.

// In Day10

fun solvePart1(): Int =
    traversePipe().size / 2

Star earned! Onward!

⭐ Day 10, Part 2

The puzzle text can be found here.

Strategy

I don’t know a lot about mazes but one thing I do know is the “right hand rule” for finding your way out of one. Basically, if you’re ever stuck in a maze, put your right hand on a wall and walk forward. Keep your hand on the wall. Eventually, you’ll find the exit.

So let’s do something like that. We’ll traverse the pipeline and pick one side of it randomly to mark as outside. Imagine our pipeline is a square and we’re moving along it. Stick your left hand out and mark that side of the pipeline as “outside” if it is not occupied by part of the pipeline. In fact, not on that spot but any spot it touches that isn’t part of the pipeline. So if we’re moving SOUTH, we’ll see if the spot to the EAST is part of the pipe or not, and if not, flood that area with a symbol indicating that we consider it “outside” of the pipe.

In short

Find all of the points in the pipeline.
Remove anything from the grid that isn’t part of the pipeline.
Traverse the pipeline and mark all of the spots on one side of it as the “outside”
Figure out if we just marked the inside or the outside.

Implementation

To do this, we’ll need a markingDirection map where the key is the current direction of travel and the value is the direction to mark.

// In Day10

private val markingDirection: Map<Point2D, Point2D> =
    mapOf(
        SOUTH to EAST,
        NORTH to WEST,
        WEST to SOUTH,
        EAST to NORTH
    )

In order to do some marking when we traverse the pipeline, we’ll need to alter traversePipe to take in a function. I’ve highlighted the relevant rows here.

// In Day10
// Refactored from Part 1

private fun traversePipe(
  preMove: (Point2D, Point2D, Point2D) -> (Unit) = { _, _, _ -> }
): Set<Point2D> {
    val pipe = mutableSetOf(start)
    var current = start
        .cardinalNeighbors()
        .filter { grid.isSafe(it) }
        .first {
            val d = it - start
            (grid[it] to d in movements)
        }
    var direction = current - start
    while (current != start) {
        pipe += current
        movements[grid[current] to direction]?.let { nextDirection ->
            preMove(current, direction, nextDirection)
            direction = nextDirection
            current += direction
        } ?: error("Invalid movement detected: $current, $direction")
    }
    return pipe
}

The first change is to take in a function that takes three Point2D objects and returns Unit (has only side-effects). Because we call traversePipeline with no implementation for this function more often than not, we provide a default do-nothing implementation (which may be the strangest looking Kotlin I’ve ever written).

The second change is to call this preMove function with the current place, the current direction and the nextDirection.

Everything else in traversePipe is the same as part 1. We’ll call this function later, but first let’s talk about flood filling our grid.

// In Day10

private fun Array<CharArray>.floodFill(at: Point2D, c: Char) {
    if (!isSafe(at)) return
    val queue = ArrayDeque<Point2D>().apply { add(at) }
    while (queue.isNotEmpty()) {
        val next = queue.removeFirst()
        if (this[next] == '.') {
            this[next] = c
            queue.addAll(next.cardinalNeighbors().filter { isSafe(it) })
        }
    }
}

I didn’t add this to the Extensions.kt file because it feels like we may not need this in the future. Maybe I’m wrong.

The floodFill takes a place to begin the flood at and a Char to flood with. The first check we do is to make sure the place we’re starting the flood from is actually in the grid via isSafe. Then we start up a work queue and add the initial spot to it. So long as the queue has some work for us, we take out the next spot and if it is empty, fill it with c and add all of its cardinalNeighors to the queue if they are safe.

At the end of this function, the spot we start at and anything we can get to from it will be filled with c.

And now we can solve part 2.

// Day 10

fun solvePart2(): Int {
    val pipe = traversePipe()

    grid.forEachIndexed { y, row ->
        row.forEachIndexed { x, c ->
            val at = Point2D(x, y)
            if (at !in pipe) grid[at] = '.'
        }
    }
    val emptyCorner =
        listOf(
            Point2D(0, 0),
            Point2D(0, grid[0].lastIndex),
            Point2D(grid.lastIndex, 0),
            Point2D(grid.lastIndex, grid[0].lastIndex)
        )
            .first { grid[it] == '.' }

    traversePipe { current, direction, nextDirection ->
        grid.floodFill(current + markingDirection.getValue(direction), 'O')
        if (grid[current] in setOf('7', 'L', 'J', 'F')) {
            grid.floodFill(current + markingDirection.getValue(nextDirection), 'O')
        }
    }

    val find = if (grid[emptyCorner] == 'O') '.' else 'O'
    return grid.sumOf { row -> row.count { it == find } }
}

As in part 1, the fist part is to traverse the pipe. We then go and remove anything from the grid that isn’t part of the pipe. Rendering the grid at this point will show us what the pipe looks like.

The next thing to do is find a single emptyCorner to look at later, after we flood-fill. I’m going to be honest and tell you that I’m not actually sure if this works on all inputs. I’m assuming there is a corner that is on the outside of the pipe. We do this by creating a Point2D for each corner of the grid and finding the first one that is a space.

Now we can traverse the pipe and pass it our function to do the flood-filling. No matter where we are in the pipeline, we’ll look up the markingDirection for the current direction and initiate a flood-fill from the offset of that point from the current point.

This part eluded me for some time today - we also need to flood-fill the nextDirection if we’re on a corner. Most of the time this work won’t actually be required. But if your input is like mine, there will be spots that we never paint because they are completely surrounded by turns. So if we detect that we’re on a turn symbol, flood-fill the offset of the current spot plus the nextDirection.

Finally, we figure out if we’re going to find some O spots or . spots in the grid. This is because sometimes we traverse the pipeline clockwise and sometimes anti-clockwise. I’m sure there’s a way to figure it out (counting turns?) but this is what I ended up with.

Finally, we loop through the grid via combination of sumOf and count and count up the number of times we find the spot type we care about. This is our answer.

Star earned! See you tomorrow!

⭐ Day 10, Part 1

⭐ Day 10, Part 2

Further Reading