# Advent of Code 2023 - Day 10, in Kotlin - Pipe Maze

Kotlin solutions to parts 1 and 2 of Advent of Code 2023, Day 10: 'Pipe Maze'

Posted on

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

1. Find all of the points in the pipeline.
2. Remove anything from the grid that isn’t part of the pipeline.
3. Traverse the pipeline and mark all of the spots on one side of it as the “outside”
4. 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
}
}
}
``````

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!