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'
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.
Further Reading
- Index of All Solutions - All posts and solutions for 2022, in Kotlin.
- My Github repo - Solutions and tests for each day.
- Solution - Full code for day 22
- Advent of Code - Come join in and do these challenges yourself!