Advent of Code 2019 - Day 10, in Kotlin • Todd Ginsberg

Today we’re going to blast some asteroids with a laser! And flatten the h*ck out of some data structures!

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

Problem Input

We are given a file with lines of . and # symbols. We’ll pass the lines in as a List<String> where each String represents one row. We’ll write a function called parseInput that takes our List<String> and turns it into a List<Point2D> (which we defined earlier on Day 3 ).

This is accomplished iterating over each row, by index (using widthIndex), and then by each column (also using withIndex). The flatMap function call takes advantage of destructuring. That means we can break up the IndexedValue we would normally receive into its component parts, calling them y (the index) and row (the String). We must make sure to only take the asteroid spots (#).


class Day10(input: List<String>) {

    private val asteroids: List<Point2D> = parseInput(input)

    private fun parseInput(input: List<String>): List<Point2D> =
        input.withIndex().flatMap { (y, row) ->
            row.withIndex().filter { it.value == '#' }.map { Point2D(it.index, y) }
        }

}

⭐ Day 10, Part 1

The puzzle text can be found here.

Well, we’re going to have to learn about angles I suppose. I’m not ashamed to say that I spent a lot of time searching and reading about this today, I just don’t remember the formula for angles I presumably learned in high school. What I want, because it seems easier to debug to me, is for any two given Point2D objects, to tell me the degrees of the angle between them. Between 0 and 359 degrees, like a compass.

Let’s add a new function to our existing Point2D:

// In Point2D:

fun angleTo(other: Point2D): Double {
    val d = toDegrees(
        atan2(
            (other.y - y).toDouble(),
            (other.x - x).toDouble()
        )
    ) + 90
    return if (d < 0) d + 360 else d
}

And here’s a picture of what we get for this:


.A.
DXB
.C.

If we are X in the middle, the angle to A should be 0°, B should be 90°, C should be 180°, and D should be 270°. I’m sure there are other systems of coordinates, but this is what I went with because I could understand it. Note that this system assumes that 0,0 (the origin) is in the upper left hand corner. It seems that most Advent of Code puzzles in the past have worked this way, and today’s does as well. If we end up needing degrees in some other system, we’ll write it then (and possibly refactor this).

Now that we have our angleTo function on Point2D, let’s write a helper function we’ll end up using for both parts of the puzzle:

// In Day10

private fun Point2D.countTargets(): Int =
    asteroids.filterNot { it == this }.map { this.angleTo(it) }.distinct().size

Given a point/asteroid (except for the one we’re on) calculate the angle between the current Point2D and each other asteroid. Reduce that to only the distinct values (so, if we have two points that are 90°, only count it once), and take the size of that list. This tells us the number of asteroids we can see from any given asteroid.

And we can use that to solve Part 1:

fun solvePart1(): Int =
    asteroids.map { it.countTargets() }.max()!!

For every asteroid, get the number of targets we can see, and take the one with the maximum value. This is our answer. (Yes, I used the Hold My Beer Operator . I don’t like it, but it’s fine in this case because we know there’s going to be a maximum value).

Star earned, onward!

⭐ Day 10, Part 2

The puzzle text can be found here.

I’m going to refer to this drawing while explaining our solution to Part 2:

...E...
...A...
.HDXBF.
...C...
...G...

To orient ourselves, we’re in the middle on the asteroid marked X. The laser should sweep the surrounding asteroids in alphabetical order. A, B, C, and D on the first sweep, and E, F, G, and H on the final sweep.

Simply ordering by angle and then by distance won’t work. We’ll end up with something like A,E,B,F,C,G,D,H.

What we’re going to do is:

Get a list of every asteroid except the base (where our laser is).
Group all of the asteroids by their angle from the base. We’ll have a Map<Double, List<Point2D>> at this point.
Sort all of the values of the map (our asteroids) by distance.
At this point we have a map of angle to asteroid, with the asteroids in distance order.
Turn that into a List<List<Point2D>> where each of the inner lists represents a value in the map before.
Care should be taken to insert the lists in angle order (0 first, 359 last).
Select one from each list in round-robin format.

I know it’s confusing, but let’s start at the end by making an extension function. I feel like we could reuse this at some point, so why not?

// In Extensions.kt

fun <T> Collection<Collection<T>>.flattenRoundRobin(): List<T> =
    this.flatMap { it.withIndex() }.sortedBy { it.index }.map { it.value }

This is the heart of our solution for Part 2 today. What happens is it turns this: listOf(listOf('A', 'C'), listOf('B', 'D')) into this: listOf('A', 'B', 'C', 'D')! I remember doing this on an old side project from years back in scala and translated it to Kotlin. I’m positive I read about it somewhere else and translated that into scala at the time, so I have no idea who to credit for this idea.

What happens is that we end up using withIndex again. By doing a flatMap to the indexed value, we end up with each element in the lists above, and their index (how far along the list they are).

Like this:

0,A
1,C
0,B
1,D

By sorting these by the index, we get this:

0,A
0,B
1,C
1,D

And then we can simply map to the values to get listOf('A', 'B', 'C', 'D')! Isn’t that cool?

Now that we have that, we can finish executing our plan:

// In Day10

private fun targetingOrder(base: Point2D): List<Point2D> =
    asteroids
        .filterNot { it == base }
        .groupBy { base.angleTo(it) }
        .mapValues { it.value.sortedBy { target -> base.distanceTo(target) } }
        .toSortedMap()
        .values
        .flattenRoundRobin()

Get all of the asteroids, remove the base from consideration, group all of the asteroids by their angle, sort the asteroids by distance, get all of the lists in order of their angle, and call our extension function to flatten it. And at the end, we have all the asteroids in the order they will be targeted by the laser.

Some notes on this approach:

We use Manhattan distance here, not an absolute distance. This worked for me, but I can’t guarantee it for all inputs. I suspect it works, but if it doesn’t, drop me a note and I’ll write up a new distanceTo function.

The sortBy { it.index } in flattenRoundRobin may need to be altered. This always gave me the right answer, but I feel like it works incidentally (which I’m ok with).

We now have everything we need to solve Part 2!

fun solvePart2(): Int =
    targetingOrder(asteroids.maxBy { it.countTargets() }!!).drop(199.run { (x * 100) + y }

We reuse our countTargets extension here, get the 200th asteroid in the list, and do the multiplication needed to get our answer.

Star earned!

I’m pretty happy with how this turned out today. I had a completely different idea of how to solve this going into it. One of the reasons you probably won’t see me live streaming my solutions is that I end up throwing a lot of code away. I go down the wrong path and eventually solve the puzzle. Once I know the answer, I refine it until it is clean and in a format that I can explain here. Maybe after Day 25, I’ll write up my process.

⭐ Day 10, Part 1

⭐ Day 10, Part 2

Further Reading