# Advent of Code 2022 - Day 22, in Kotlin - Monkey Map

Kotlin solutions to parts 1 and 2 of Advent of Code 2022, Day 22: 'Monkey Map'

Posted on

This was easily the hardest puzzle of Advent of Code 2022 for me. I approached this three different ways and completely started over a few times. I think what I ended up with is clear and will solve the puzzle for all inputs that Advent of Code uses. I sure learned a lot about cubes and coordinates while writing this.

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

Puzzle Input

We’re going to cheat a bit with the input to today’s puzzle. If you go look at the shape of your puzzle input, I suspect it will look the same as mine. I had originally written a solution to this puzzle that only worked with my input and its special set of transition rules thinking I’d generalize it once I had solved the problem. However, after reading up on how other people have solved this puzzle, I have come to understand that all of the inputs have a single shape.

Like this (I’ve numbered the boxes for clarity):

``````      +-----+-----+
|     |     |
|  1  |  2  |
|     |     |
+-----+-----+
|     |
|  3  |
|     |
+-----+-----+
|     |     |
|  4  |  5  |
|     |     |
+-----+-----+
|     |
|  6  |
|     |
+-----+
``````

So we will assume that each of these numbered areas have known, fixed locations and sizes.

With that in mind, lets get started with parsing all of the blocks in these numbered areas that are not passable. We will start our numbering at 0,0 in the text file of the input. This means the top left hand corner of block 1 is not going to be 0,0, it will be something like 50,0.

``````// In Day22

private fun parseBlockedPlaces(input: List<String>): Set<Point2D> =
input
.takeWhile { it.isNotBlank() }
.flatMapIndexed { y, row ->
row.mapIndexedNotNull { x, c ->
if (c == '#') Point2D(x, y) else null
}
}.toSet()
``````

We will go through the input and `takeWhile` the rows are not blank (meaning - it the map). We will then use the familiar `flatMapIndexed` and `mapIndexedNotNull` construct to produce a `Set<Point2D>` objects which each represent a place in one of the squares that we cannot move to.

Next, we’ll parse the instructions by defining a sealed type called `Instruction`.

``````// In Day22

private sealed class Instruction {
companion object {
fun ofList(input: List<String>): List<Instruction> =
input
.dropWhile { it.isNotBlank() }
.drop(1)
.first()
.trim()
.let { """\d+|[LR]""".toRegex().findAll(it) }
.map { it.value }
.filter { it.isNotBlank() }
.map { symbol ->
when (symbol) {
"L" -> Left
"R" -> Right
else -> Move(symbol.toInt())
}
}.toList()
}
}

private class Move(val steps: Int) : Instruction()
private object Left : Instruction()
private object Right : Instruction()
``````

The `Instruction` class does the parsing and definition of the subclasses. The `Instruction` class has three valid subclasses - `Move` which tells us the number of `steps` to move, `Left` which tells us to turn left, and `Right` which tells us to turn right. Since `Left` and `Right` hold no state, we can make them objects and not classes.

To parse out the instructions, we need to look at all the `input` and skip over the map portion by using `dropWhile` and then `drop(1)`, taking the `first()` row beyond that should be our giant string of instructions. We will use a regular expression to break up the string into `symbols` (a number, an `L`, or a `R`), and then `map` those `symbols` to the appropriate `Instruction` class. We return these as a `List<Instruction>`.

``````class Day22(input: List<String>) {

private val blockedPlaces: Set<Point2D> = parseBlockedPlaces(input)
private val instructions: List<Instruction> = Instruction.ofList(input)

}
``````

At the end of the input parsing section, we’ll save these in `blockedPlaces` and `instructions` in our `Day22` class.

#### ⭐ Day 22, Part 1

The puzzle text can be found here.

There is going to be a lot of code in this section, so I’m sorry in advance. I’ll try as hard as I can to make this clear.

When we move around the input, we need to know which direction we are `Facing`, and what direction we would be going if we were to turn left or right. To accomplish this, we’ll define another sealed class called `Facing`. It has four sub-objects (these hold no state): `North`, `East`, `South`, and `West`. These directions define how many `points` they are worth at the end of the game, and the `offset` for movement (if they were to move one space, how would we represent this when added to an existing `Point2D`?).

You will also notice the abstract `left` and `right` values. These are defined that way so the types are all parsed before they are referenced. Otherwise Kotlin will have no idea what `West` means when defining `North` (for example) because it hasn’t got to that yet.

``````// Day22

sealed class Facing(val points: Int, val offset: Point2D) {
abstract val left: Facing
abstract val right: Facing

object North : Facing(3, Point2D(0, -1)) {
override val left = West
override val right = East
}

object East : Facing(0, Point2D(1, 0)) {
override val left = North
override val right = South
}

object South : Facing(1, Point2D(0, 1)) {
override val left = East
override val right = West
}

object West : Facing(2, Point2D(-1, 0)) {
override val left = South
override val right = North
}
}
``````

When we are making our way across the field, we will need to keep track of where we are so We’ll define a data class called `Orientation` for this that knows our current `location` and which direction we are `facing`.

It also defines a `score` function to calculate the total points at the end of the instruction. We also define a `move` function which tells us the next `Orientation` if we were to advance one space in the direction we are `facing`. This is where the offset is used.

``````// In Day22

private data class Orientation(val location: Point2D, val facing: Facing) {
fun score(): Int =
(1000 * (location.y + 1)) + (4 * (location.x + 1)) + facing.points

fun move(): Orientation =
copy(location = location + facing.offset)
}
``````

Remember above, how we labeled sections of the input with numbers 1 through 6? Well it turns out that if you cut out that shape, and fold it just right, it forms a cube. We’re going to have to deal with the input as a cube rather than a plane in Part Two, so let’s just model Part One as a cube as well. Not really a cube, just the faces of a cube.

We’re going to introduce yet another new class called `CubeFacing`, and this describes an area of the map by `id`, its `size` (50 for all our inputs), where the `topLeft` point is, and how to `Transition` to another `CubeFace` when we run off the edge of this one. Defining six of these, and appropriately defining the transitions (which we will write below) will give us a way to move around the plane in Part One, and the outside of the cube in Part Two!

``````// In Day22

class CubeFacing(
val id: Int,
val size: Int,
val topLeft: Point2D,
val north: Transition,
val east: Transition,
val south: Transition,
val west: Transition
) {
val minX: Int = topLeft.x
val maxX: Int = topLeft.x + size - 1
val minY: Int = topLeft.y
val maxY: Int = topLeft.y + size - 1

operator fun contains(place: Point2D): Boolean =
place.x in (minX..maxX) && place.y in (minY..maxY)

fun transition(direction: Facing): Transition =
when (direction) {
Facing.North -> north
Facing.East -> east
Facing.South -> south
Facing.West -> west
}

companion object {
private val instances = mutableMapOf<Int, CubeFacing>()

operator fun invoke(id: Int): CubeFacing =
instances.getValue(id)

private operator fun plus(instance: CubeFacing) {
instances[instance.id] = instance
}

init {

// We will define these later

}
}
}
``````

Things to note about `CubeFacing`: We need to calculate the full size of the area by setting aside `minX`, `minY`, `maxX` and `maxY` to hold the minimum and maximum x and y values. We use those in the `contains` operator to answer the question of whether a `Point2D` exists within this `CubeFacing`.

We also define a `transition` function to help us figure out where to go next when we hit the outer edge of a cube face. We take in a `Facing` and use a `when` expression to return the appropriate `Transition` object.

Before we define our `CubeFacing` instances, let’s take a detour and look at `Transition`. This object represents how to move from one `CubeFacing` to another. In Part One these transitions are usually pretty simple, we just have to change the x or y value in a point and our location will wrap around. This gets a bit more complicated in Part Two, so while this might seem like over-engineering now, it will all make sense later.

Therefore, `Transition` knows the `sourceId` of a `CubeFacing` (where you are now), the `destinationId` of another `CubeFacing` (where you go next), the `Facing` you have when you `exit` this `CubeFacing`, and the `Facing` you’ll have when you `enter` the destination `CubeFacing`. Again, in Part One, the exit and enter values all match (if you were to go East off the edge of cube 2, you are still going East when you enter cube 1). We define the actual `soruce` and `destination` references to `CubeFacing` here using the `lazy` delegate. Again, because Kotlin won’t have defined them all yet since `CubeFacing` and `Transition` refer to each other. Maybe a different design would have eliminated the need for a circular dependency, but since these classes are just used in our puzzle solution, I don’t mind.

``````// In Day22

data class Transition(val sourceId: Int, val destinationId: Int, val exit: Facing, val enter: Facing) {
private val byDirection = Pair(exit, enter)
private val source: CubeFacing by lazy { CubeFacing(sourceId) }
val destination: CubeFacing by lazy { CubeFacing(destinationId) }

fun move(start: Point2D): Point2D = when (byDirection) {

Pair(Facing.North, Facing.North) -> Point2D(start.x, destination.maxY)
Pair(Facing.East, Facing.East) -> Point2D(destination.minX, start.y)
Pair(Facing.West, Facing.West) -> Point2D(destination.maxX, start.y)
Pair(Facing.South, Facing.South) -> Point2D(start.x, destination.minY)
else -> throw IllegalStateException("No transition from \$exit to \$enter")

}
}
``````

The important part of `Transition` is the `move` function which describes how to translate a single `start` point from one `Facing` to another. For example, when transitioning from `North` in one cube to `North` in another cube, the x value stays the same but the y value changes to be the minimum (the “top”) of the destination cube. Again, this gets more complicated in Part Two.

Now that we know why we have `CubeFacing` and `Transition`, we can define our `CubeFacing` instances:

``````// In Day22.CubeFacing

init {
CubeFacing + CubeFacing(
id = 1,
size = 50,
topLeft = Point2D(50, 0),
north = Transition(1, 5, Facing.North, Facing.North),
east = Transition(1, 2, Facing.East, Facing.East),
south = Transition(1, 3, Facing.South, Facing.South),
west = Transition(1, 2, Facing.West, Facing.West)
)

CubeFacing + CubeFacing(
id = 2,
size = 50,
topLeft = Point2D(100, 0),
north = Transition(2, 2, Facing.North, Facing.North),
east = Transition(2, 1, Facing.East, Facing.East),
south = Transition(2, 2, Facing.South, Facing.South),
west = Transition(2, 1, Facing.West, Facing.West)
)

CubeFacing + CubeFacing(
id = 3,
size = 50,
topLeft = Point2D(50, 50),
north = Transition(3, 1, Facing.North, Facing.North),
east = Transition(3, 3, Facing.East, Facing.East),
south = Transition(3, 5, Facing.South, Facing.South),
west = Transition(3, 3, Facing.West, Facing.West)
)

CubeFacing + CubeFacing(
id = 4,
size = 50,
topLeft = Point2D(0, 100),
north = Transition(4, 6, Facing.North, Facing.North),
east = Transition(4, 5, Facing.East, Facing.East),
south = Transition(4, 6, Facing.South, Facing.South),
west = Transition(4, 5, Facing.West, Facing.West)
)

CubeFacing + CubeFacing(
id = 5,
size = 50,
topLeft = Point2D(50, 100),
north = Transition(5, 3, Facing.North, Facing.North),
east = Transition(5, 4, Facing.East, Facing.East),
south = Transition(5, 1, Facing.South, Facing.South),
west = Transition(5, 4, Facing.West, Facing.West)
)

CubeFacing + CubeFacing(
id = 6,
size = 50,
topLeft = Point2D(0, 150),
north = Transition(6, 4, Facing.North, Facing.North),
east = Transition(6, 6, Facing.East, Facing.East),
south = Transition(6, 4, Facing.South, Facing.South),
west = Transition(6, 6, Facing.West, Facing.West)
)
}
``````

For Part One we number these 1 through 6 just like the picture.

And now we have (finally) written enough code to actually move around and `followInstructions`!

``````// In Day22

private fun followInstructions(startingCube: CubeFacing): Orientation {
var cube = startingCube
var orientation = Orientation(cube.topLeft, Facing.East)

instructions.forEach { instruction ->
when (instruction) {
is Left -> orientation = orientation.copy(facing = orientation.facing.left)
is Right -> orientation = orientation.copy(facing = orientation.facing.right)
is Move -> {
var keepMoving = true
repeat(instruction.steps) {
if (keepMoving) {
var nextOrientation = orientation.move()
var nextCube = cube

if (nextOrientation.location !in cube) {
// We have moved off the face of the cube we were on, find the transition we need.
with(cube.transition(orientation.facing)) {
nextOrientation = Orientation(move(orientation.location), enter)
nextCube = destination
}
}
if (nextOrientation.location in blockedPlaces) {
// We cannot move to this spot - it is on the map but blocking us.
keepMoving = false
} else {
// We can move to this spot - it is on the map AND free
orientation = nextOrientation
cube = nextCube
}
}
}
}
}
}
return orientation
}
``````

Let’s go over that, its a bit complicated. First, we are given a `startingCube`. In Part Two we’ll define another set of cubes (so as to capture their own `Transition` rules) so we can’t assume a consistent starting location. We set this aside in a var called `cube` which will keep track of which `CubeFacing` we are on currently. We also define a var for `orientation` and seed it with the top left corner of the `cube` as a starting point, and East as its facing.

Now, we go through each of the `instructions` and follow them. If we are given a `Left` or a `Right`, we make a `copy` of our `orientation` with a new `facing`, which is done by getting the `left` or `right` property from `Facing`. If we have to `Move`, the work gets more complicated. We set up a `repeat` loop for the given number of `steps` in the movement. We also have a flag for `keepMoving` because there’s no sense in looping when we know we’re just going to keep bonking into a barrier (I mean, we could, it’s probably not that big of a deal time-wise).

The first part of the move sequence is to speculatively call `orientation.next()` to move us one space in the direction we are facing. We save this in `nextORientation` and copy the `cube` into `nextCube`. First we need to test if that movement just caused us to fall off the edge of the cube we were just on by using `in` (the `contains` operator). If so, we look up the `transition` we need off the cube given a `facing` and execute it. The `move` function will return us a `Point2D` that is in the target cube.

Once we’ve either decided we haven’t gone off the edge of our cube, or have figured out which cube we are on now and what point we’re on and how we’re facing, we need to see if we can actually move there. If the `location` of the `nextOrientation` is in the `blockedPlaces` set, we know we can’t move there because we’ll bonk into a barrier. In this case, we set `keepGoing` to false so we don’t keep looping. Otherwise, we will set our “current” `orientation` and `cube` to speculative values we created - `nextOrientation` and `nextCube`.

Once we run through all of this, we can return the current `orientation`.

Following the instructions and getting the `score` from the `Orientation` will give us our answer!

``````// In Day22

fun solvePart1(): Int =
followInstructions(CubeFacing(1)).score()
``````

Star earned! Onward!

#### ⭐ Day 22, Part 2

The puzzle text can be found here.

Thanks to all the code we wrote for Part One, we have comparatively little to do for Part Two. We use the same logic and general approach, we just have to define a new set of `CubeFacing` objects, and a new set of `Transtion` rules! Everything else stays the same!

For clarity we are numbering these cubes for Part Two as 11 through 16 (as opposed to re-defining 1-6 for Part Two):

``````// In Day22.CubeFacing

// Add these to the init block, below the ones already defined for Part One
CubeFacing + CubeFacing(
id = 11,
size = 50,
topLeft = Point2D(50, 0),
north = Transition(11, 16, Facing.North, Facing.East),
east = Transition(11, 12, Facing.East, Facing.East),
south = Transition(11, 13, Facing.South, Facing.South),
west = Transition(11, 14, Facing.West, Facing.East)
)
CubeFacing + CubeFacing(
id = 12,
size = 50,
topLeft = Point2D(100, 0),
north = Transition(12, 16, Facing.North, Facing.North),
east = Transition(12, 15, Facing.East, Facing.West),
south = Transition(12, 13, Facing.South, Facing.West),
west = Transition(12, 11, Facing.West, Facing.West)
)

CubeFacing + CubeFacing(
id = 13,
size = 50,
topLeft = Point2D(50, 50),
north = Transition(13, 11, Facing.North, Facing.North),
east = Transition(13, 12, Facing.East, Facing.North),
south = Transition(13, 15, Facing.South, Facing.South),
west = Transition(13, 14, Facing.West, Facing.South)
)

CubeFacing + CubeFacing(
id = 14,
size = 50,
topLeft = Point2D(0, 100),
north = Transition(14, 13, Facing.North, Facing.East),
east = Transition(14, 15, Facing.East, Facing.East),
south = Transition(14, 16, Facing.South, Facing.South),
west = Transition(14, 11, Facing.West, Facing.East)
)

CubeFacing + CubeFacing(
id = 15,
size = 50,
topLeft = Point2D(50, 100),
north = Transition(15, 13, Facing.North, Facing.North),
east = Transition(15, 12, Facing.East, Facing.West),
south = Transition(15, 16, Facing.South, Facing.West),
west = Transition(15, 14, Facing.West, Facing.West)
)

CubeFacing + CubeFacing(
id = 16,
size = 50,
topLeft = Point2D(0, 150),
north = Transition(16, 14, Facing.North, Facing.North),
east = Transition(16, 15, Facing.East, Facing.North),
south = Transition(16, 12, Facing.South, Facing.South),
west = Transition(16, 11, Facing.West, Facing.South)
)
``````

As you can see, the `exit` and `enter` facings don’t always line up. Sometimes it’s still an easy transition (like when we move North out of cube 16 to cube 14, still facing North), but sometimes it is more complicated and requires us to hop over across the map.

For this, it was easier for me to “scale” the points down to those relative to the cube corner. Meaning, x and y relative to the `CubeFacing` we are in, not the entire map. This gives us a consistent 0-50 (in our case) to work with for both x and y. If we can “scale down” to relative points and then “scale up” to absolute points, transitions will be easier.

To accomplish this, let’s add a `scaleDown` and `scaleUp` function to `CubeFacing` which translates absolute points to relative points and back. We do this by either subtracting or adding the `topLeft` point.

``````// In Day22.CubeFacing

fun scaleDown(point: Point2D): Point2D =
point - topLeft

fun scaleUp(point: Point2D): Point2D =
point + topLeft
``````

Yes, we need to add `minus` support to `Point2D` (we already have `plus` from previous days):

``````// In Point2D

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

And because we’ll be doing scaling operations a lot in `Transition`, we’ll define some helper functions there as well. `rescale` will use the source `CubeFacing` to scale a point down (to relative points) and the scale back up to absolute points in the destination `CubeFacing`. We also have a case where we need to `flip` the x and y coordinates and then do a rescale, so we’ll define `flip` and `flipRescaled` for this work.

``````// In Day22.Transition

private fun Point2D.rescale(): Point2D =
destination.scaleUp(source.scaleDown(this))

private fun Point2D.flipRescaled(): Point2D =
destination.scaleUp(source.scaleDown(this).flip())

private fun Point2D.flip(): Point2D =
Point2D(y, x)
``````

And the final bit of code we’ll write, and the source of the most debugging pain for me, is to completely redefine the transition rules. Most of them.

``````// In Day22.Transition

// This replaces the move function from Part One entirely.
fun move(start: Point2D): Point2D = when (byDirection) {
Pair(Facing.North, Facing.North) -> Point2D(start.rescale().x, destination.maxY)
Pair(Facing.East, Facing.East) -> Point2D(destination.minX, start.rescale().y)
Pair(Facing.West, Facing.West) -> Point2D(destination.maxX, start.rescale().y)
Pair(Facing.South, Facing.South) -> Point2D(start.rescale().x, destination.minY)

Pair(Facing.North, Facing.East) -> Point2D(destination.minX, start.flipRescaled().y)
Pair(Facing.East, Facing.North) -> Point2D(start.flipRescaled().x, destination.maxY)
Pair(Facing.East, Facing.West) -> Point2D(destination.maxX, destination.maxY - source.scaleDown(start).y)
Pair(Facing.West, Facing.East) -> Point2D(destination.minX, destination.maxY - source.scaleDown(start).y)
Pair(Facing.West, Facing.South) -> Point2D(start.flipRescaled().x, destination.minY)
Pair(Facing.South, Facing.West) -> Point2D(destination.maxX, start.flipRescaled().y)
else -> throw IllegalStateException("No transition from \$exit to \$enter")
}
``````

If you think about it, there should be 16 total rules (from North, South, East, and West to each of North, South, East, and West). Since we don’t actually have all of these kinds of transitions in our model, I didn’t define them. If you feel this is missing, go ahead, they should all fit in here and follow very similar logic.

I’m not going to go over what each of these rules does because that would cause me to make a bunch of ASCII art cube drawings. But the basic logic is this - if we’ve gone off the edge of a cube, we know we’re landing on the edge of another cube. So one of the x or y values is always going to be either the minimum or maximum value, depending on the direction we’re coming from and to. For the other axis, we’ll need to at least rescale our point to the absolute coordinates of the target cube, and in some cases flip the x and y values (when we transition between completely opposite directions like going from East to West).

Calling our existing `followInstructions` function with `CubeFacing` 11, gives us our answer!

``````// In Day22

fun solvePart2(): Int =
followInstructions(CubeFacing(11)).score()
``````

Star earned! See you tomorrow.