Skip to Content

Advent of Code 2018 - Day 25, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2018, Day 25: 'Four-Dimensional Adventure'

Posted on

The last day of Advent of Code 2018 is finally here, and with is is the traditional one part problem that isn’t so hard you have to spend all day on it!

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

Problem Input

We will pull in input as a List<String> and parse it further in part 1.

Day 25, Part 1

The reindeer’s symptoms are getting worse, and neither you nor the white-bearded man have a solution. At least the reindeer has a warm place to rest: a small bed near where you’re sitting.

As you reach down, the reindeer looks up at you, accidentally bumping a button on your wrist-mounted device with its nose in the process - a button labeled “help”.

“Hello, and welcome to the Time Travel Support Hotline! If you are lost in time and space, press 1. If you are trapped in a time paradox, press 2. If you need help caring for a sick reindeer, press 3. If you–”

Beep.

A few seconds later, you hear a new voice. “Hello; please state the nature of your reindeer.” You try to describe the situation.

“Just a moment, I think I can remotely run a diagnostic scan.” A beam of light projects from the device and sweeps over the reindeer a few times.

“Okay, it looks like your reindeer is very low on magical energy; it should fully recover if we can fix that. Let me check your timeline for a source…. Got one. There’s actually a powerful source of magical energy about 1000 years forward from you, and at roughly your position, too! It looks like… hot chocolate? Anyway, you should be able to travel there to pick some up; just don’t forget a mug! Is there anything else I can help you with today?”

You explain that your device isn’t capable of going forward in time. “I… see. That’s tricky. Well, according to this information, your device should have the necessary hardware to open a small portal and send some hot chocolate back to you. You’ll need a list of fixed points in spacetime; I’m transmitting it to you now.”

“You just need to align your device to the constellations of fixed points so that it can lock on to the destination and open the portal. Let me look up how much hot chocolate that breed of reindeer needs.”

“It says here that your particular reindeer is– this can’t be right, it says there’s only one like that in the universe! But THAT means that you’re–” You disconnect the call.

The list of fixed points in spacetime (your puzzle input) is a set of four-dimensional coordinates. To align your device, acquire the hot chocolate, and save the reindeer, you just need to find the number of constellations of points in the list.

Two points are in the same constellation if their manhattan distance apart is no more than 3 or if they can form a chain of points, each a manhattan distance no more than 3 from the last, between the two of them. (That is, if a point is close enough to a constellation, it “joins” that constellation.) For example:

 0,0,0,0
 3,0,0,0
 0,3,0,0
 0,0,3,0
 0,0,0,3
 0,0,0,6
 9,0,0,0
12,0,0,0

In the above list, the first six points form a single constellation: 0,0,0,0 is exactly distance 3 from the next four, and the point at 0,0,0,6 is connected to the others by being 3 away from 0,0,0,3, which is already in the constellation. The bottom two points, 9,0,0,0 and 12,0,0,0 are in a separate constellation because no point is close enough to connect them to the first constellation. So, in the above list, the number of constellations is 2. (If a point at 6,0,0,0 were present, it would connect 3,0,0,0 and 9,0,0,0, merging all of the points into a single giant constellation instead.)

In this example, the number of constellations is 4:

-1,2,2,0
0,0,2,-2
0,0,0,-2
-1,2,0,0
-2,-2,-2,2
3,0,2,-1
-1,3,2,2
-1,0,-1,0
0,2,1,-2
3,0,0,0

In this one, it’s 3:

1,-1,0,1
2,0,-1,0
3,2,-1,0
0,0,3,1
0,0,-1,-1
2,3,-2,0
-2,2,0,0
2,-2,0,-1
1,-1,0,-1
3,2,0,2

Finally, in this one, it’s 8:

1,-1,-1,-2
-2,-2,0,1
0,2,1,3
-2,3,-2,1
0,2,3,-2
-1,-1,1,-2
0,-2,-1,0
-2,2,3,-1
1,2,2,0
-1,-2,0,-2

The portly man nervously strokes his white beard. It’s time to get that hot chocolate.

How many constellations are formed by the fixed points in spacetime?

First, let’s create another point class, this time for 4-dimensions! I decided to call the 4th dimension t for time, but you can really pick anything for today, they don’t really have much meaning. In principle we could go back and refactor Point, Point3d and Point4d into a single n-dimensional point class, but I didn’t want to have to refactor all of the code that depends on it. Maybe before Advent of Code 2019 starts I’ll do that to prepare.

class Day25(rawInput: List<String>) {

    private val points: List<Point4d> = rawInput.map { Point4d.of(it) }

	private data class Point4d(val x: Int, val y: Int, val z: Int, val t: Int) {

	    fun distanceTo(other: Point4d): Int =
	        abs(x - other.x) + abs(y - other.y) + abs(z - other.z) + abs(t - other.t)

	    companion object {
	        fun of(input: String): Point4d {
	            val (x, y, z, t) = input.split(",").map { it.trim().toInt() }
	            return Point4d(x, y, z, t)
	        }
	    }
	}
}

The distanceTo function should look familiar, as should our parsing logic once again using an of function in the companion. This time parsing is pretty straight forward - split our String on comma and turn the parts into Ints.

Next, we need to make a map of each point and what its immediate neighbors are. Remember, we consider something a neighbor if it is 3 or fewer units away (and it is not the same point).

// In Day25

private fun mapNeighbors(): Map<Point4d, Set<Point4d>> =
    points.map { point ->
        Pair(point, points.filterNot { it == point }.filter { point.distanceTo(it) <= 3 }.toSet())
    }.toMap()

Now that we have our neighborhood plotted, let’s talk about how we turn them into constellations. Let’s say we have some point A whose neighbors are B and C. We know that at a minimum, A, B, and C represent a constellation because B and C are within 3 units of A. Taking that one step further, anything that is a neighbor of B is also part of that constellation. The same goes for C. Therefore our approach is going to be to pick a point and add all of its neighbors to a constellation. Add all of the neighbors of those to it, and keep doing that until we stop adding new points. Poof! Constellation. Repeat until we run out of points to look at.

The code I wrote to do that is here, you can experiment and write it differently if you’d like:

// In Day25

private fun constellations(neighbors: Map<Point4d, Set<Point4d>>): Sequence<Set<Point4d>> = sequence {
    val allPoints = neighbors.keys.toMutableList()
    while (allPoints.isNotEmpty()) {
        val point = allPoints.removeAt(0)
        val thisConstellation = mutableSetOf(point)
        val foundNeighbors = ArrayDeque<Point4d>(neighbors.getValue(point))
        while (foundNeighbors.isNotEmpty()) {
            foundNeighbors.removeFirst().also {
                allPoints.remove(it) // Not the basis of a new constellation
                thisConstellation.add(it)   // Because it is part of our constellation

                // And all this point's neighbors are therefore part of our constellation too
                foundNeighbors.addAll(neighbors.getValue(it).filterNot { other -> other in thisConstellation })
            }
        }
        // We've run out of found neighbors to check, this is a constellation.
        yield(thisConstellation)
    }
}

As you can see, we’ll implement this with a queue (foundNeighbors), and keep adding its neighbors to the queue until we run out of things that aren’t already in the constellation. We’ll implement this as a sequence, but we could just keep a counter if we wanted as that’s all the problem asks for.

Running this solves our final puzzle of Advent of Code 2018:

// In Day25

fun solvePart1(): Int =
    constellations(mapNeighbors()).count()

Star earned!

Thanks for following along with me! I enjoyed solving and writing about these problems. Reach out and let me know what you think (good or bad).

Further Reading

  1. Index of All Solutions - All solutions for 2018, in Kotlin.
  2. My Github repo - Solutions and tests for each day.
  3. Solution - Full code for day 25
  4. Advent of Code - Come join in and do these challenges yourself!