Advent of Code 2024 - Day 14, in Kotlin - Restroom Redoubt • Todd Ginsberg

A lot of people sure disliked today’s puzzle, but don’t count me among them. I liked the fact that the requirements were vague. I’ve made a career out of dealing with vague requirements, or working on things that don’t have requirements from other people. Our industry (and I suspect many others) is filled with problems that have imprecise or missing specifications.

Part 1 has a specific specification and following the instructions in the puzzle text solves it. Part 2 is much more vague and leaves us plenty of room to solve it. I suspect there are probably quite a few ways to approach it, but I’ll only present two of them.

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

Puzzle Input

Let’s first create a data class to store the information we have about each Robot. We will store the postion and the velocity each as a Point2D. Note that today we’ll make position a var - meaning we can change it.

As usual, we will parse a String into a Robot via an of function in the companion object. Like previous days we could have written a regular expression to find all integers but I prefer to use the various form of substring functions in the Kotlin Standard Library, as I feel it is clearer.

// In Day14

private data class Robot(
    val position: Point2D,
    val velocity: Point2D
) {

    companion object {
        fun of(input: String): Robot =
            Robot(
                position = Point2D(
                    input.substringAfter("=").substringBefore(",").toInt(),
                    input.substringAfter(",").substringBefore(" ").toInt()
                ),
                velocity = Point2D(
                    input.substringAfterLast("=").substringBefore(",").toInt(),
                    input.substringAfterLast(",").toInt()
                )
            )
    }
}

Next, we’ll take in our input as a List<String> and parse it into a List<Robot> using the of function we just wrote. Additionally, we will take an optional Point2D to express the area the robots are allowed in. This defaults to the 101x103 size, allowing tests for the example in part 1 to override it with a smaller arena.

class Day14(input: List<String>, private val area: Point2D = Point2D(101, 103)) {

    private val robots: List<Robot> = input.map { Robot.of(it) }

}

⭐ Day 14, Part 1

The puzzle text can be found here.

First, let’s add a couple of convenience functions to our ongoing Point2D class. We’ll add operators for division and multiplication by some number. These will be used later on in today’s solution, and seem generally useful to have. The div function divides x and y by some number, and times multiplies x and y by some number.

// In Point2D

operator fun div(by: Int): Point2D =
    Point2D(x / by, y / by)

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

Next, we need to determine which quadrant our Robot is in. For this we will add a quadrant function to Robot that takes in a Point2D to represent the midpoint of the arena. We determine where the position is relative to the midpoint and assign that quadrant a number. It doesn’t really matter what we return here, it could be any Int, or a Char or a custom enum.

// In Robot

fun quadrant(midpoint: Point2D): Int =
    when {
        position.x < midpoint.x && position.y < midpoint.y -> 1
        position.x > midpoint.x && position.y < midpoint.y -> 2
        position.x < midpoint.x && position.y > midpoint.y -> 3
        position.x > midpoint.x && position.y > midpoint.y -> 4
        else -> 0
    }

Our Robot also needs to move, so we’ll create a function for that as well. This time we take in how many moves we want to do, and how big the area they are allowed to move in is. The implementation of this function uses our times operator to multiply the veolocy times the number of moves before adding it to the existing position.

// In Robot

fun move(moves: Int, area: Point2D): Robot =
    copy(
        position = (position + (velocity * moves)).wrap(area)
    )

What happens if the new position is outside the area? We have to wrap that back around, so we’ll ad a function local to Robot for that (as I don’t think this is generally useful outside of this context).

// In Robot

fun Point2D.wrap(other: Point2D): Point2D {
    val nextX = x % other.x
    val nextY = y % other.y
    return Point2D(
        if (nextX < 0) nextX + other.x else nextX,
        if (nextY < 0) nextY + other.y else nextY
    )
}

The wrap function applies a remainder function (%) to both the x and y values of the Point2D (n.b. we could have added this as an operator on Point2D). Then it tests to make sure the newly calculated values are in the area. If not, we wrap the values around.

Finally, we have enough to solve part 1.

// In Day14

fun solvePart1(): Int =
    robots
        .map { it.move(100, area) }
        .groupingBy { it.quadrant(area / 2) }
        .eachCount()
        .filterNot { it.key == 0 }
        .values
        .reduce(Int::times)

First each of the robots is moved 100 times. Then we group the resulting robots by their quadrant. We calculate the midpoint of the area here with the division operator we added to Point2D earlier. We get eachCount of the quadrants and filter out 0 because the robots that are on a quadrant boundary aren’t in any quadrant. The values at this point represents how many robots are in each quadrant. We don’t care about the order or names of the quadrants, just how many robots are in each one. We then reduce the values by multiplying all of them together.

Star earned! Onward!

⭐ Day 14, Part 2

The puzzle text can be found here.

Well, well! Now we’re supposed to find a picture of a Christmas tree! What does it look like? How big is it? What orientation is it in? Like most of you, I too have been given vague at best requirements before, and I appreciate that today’s Advent of Code puzzle has so many possible solutions.

I will present two to you.

Part 2: Method 1

First, I printed out every arrangement of robots for the first 10,000 moves and looked through it for a tree. The file created from this process is only about 100k.

// In Day14

fun solvePart2a() {
    var printTheseRobots = robots
    File("10_000_robots.txt").printWriter().use { out ->
        repeat(10_000) { move ->

            printTheseRobots = printTheseRobots.map { it.move(1, area) }
            val uniquePlaces = printTheseRobots.map { it.position }.toSet()
            out.println("::::$move::::")

            repeat(area.y) { y ->
                repeat(area.x) { x ->
                    out.print(if (Point2D(x, y) in uniquePlaces) "#" else '.')
                }
                out.println()
            }
        }
    }
}

I use Sublime Text as my text editor and it has a preview pane on the side of long files that shows a zoomed out view of the document I’m working on. This let me scan the whole file somewhat quickly. Generating the output took around three seconds, and finding the tree (by scanning manually) probably took me about five minutes.

At first one frame looked like any other (completely random), but eventually a pattern started to emerge like this:

A Pattern Emerges

And eventually, the pattern will become clear:

Christmas Tree

We’ve found our tree! As you can see in the print function I output the move number before the output. Copy that down, that’s our answer.

Part 2: Method 2

Method two came to me while walking my dog Charlie this morning (he’s not much of a programmer, but he’s a very good listener). I suspected the pattern with the tree is ultimately where this puzzle started. Meaning, I don’t think Eric Wastl (Advent of Code creator) started with something other than the image of the tree and perhaps some random robots outside the actual image of the tree. Given that the robots are allowed to overlap, it would be unlikely for them to have been drawn that way from the start. So I worked on the theory that the image of the tree must not have any overlapping robots. In my case this turned out to be the first such arrangement. I am not sure about any other inputs other that my own.

// In Day14

fun solvePart2b(area: Point2D = Point2D(101, 103)): Int {
    var moves = 0
    var robotsThisTurn = robots
    do {
        moves++
        robotsThisTurn = robotsThisTurn.map { it.move(1, area) }
    } while (robotsThisTurn.distinctBy { it.position }.size != robotsThisTurn.size)
    return moves
}

Solution 2b keeps moving robots until we get to a state where each of them is in their own position.

Star earned! See you tomorrow!

Puzzle Input

⭐ Day 14, Part 1

⭐ Day 14, Part 2

Part 2: Method 1

Part 2: Method 2

Further Reading