Advent of Code 2024 - Day 8, in Kotlin - Resonant Collinearity • Todd Ginsberg

What a fun way to spend a Sunday morning; solving an Advent of Code puzzle and watching the last Formula 1 race of the season! Once again this puzzle shows off some of the power in the Kotlin Standard Library, allowing us to share most of an implementation between parts 1 and 2.

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

Puzzle Input

We’ll parse the input into a Collection<List<Point2D>> where the inner List<Point2D> is a list of points for a given frequency. Since we don’t actually care at all about the frequency itself, we’ll only use them a far as we need to group the points and then get rid of them.

Our parseGrid function uses a familiar structure of flatMapIndexed (to get the row and the y value) with a nested mapIndexed (to get x and the character c at x,y). If c is not an empty spot, we will create a Pair<Char, Point2D> where the Char is the frequency and the Point2D represents the coordinates of the antenna. Once we filter out null via filterNonNull(), we’re left with a List<Pair<Char, Point2D>>, which we need to convert into a usable structure. We’ll do this by using the very handy groupBy passing in two lambdas to represent the key (the frequency) and the value (the locations), which we have picked out of the Pair. Otherwise we’d end up groping the pairs and not the values in the pairs, and we’d have to do more work.

Now we’re left with a Map<Char, List<Point2D>> - so close! To get this down to just the lists, we get only the .values, which returns a Collection<List<Point2D>>.

class Day08(private val input: List<String>) {

    private val nodes: Collection<List<Point2D>> = parseGrid(input)

    private fun parseGrid(input: List<String>): Collection<List<Point2D>> =
        input.flatMapIndexed { y, row ->
            row.mapIndexed { x, c ->
                if (c != '.') c to Point2D(x, y) else null
            }
        }.filterNotNull()
            .groupBy({ it.first }, { it.second })
            .values
}

We will need to test if a Point2D is in the grid a few times, so let’s write a function to do that. We’ll make it an extension function on Point2D that is private to our Day08 class so we can refer to input (the grid). We don’t really need to keep all of the input once we’ve parsed it (see above), we could instead decide to keep just the max x and y values. But that seems like more work than just keeping the input as-is and using indices to test our Point2D for inclusion.

// In Day08

private fun Point2D.isOnGrid(): Boolean =
    y in input.indices && x in input[y].indices

Finally, we need to determine the difference between two Point2D objects, so we will implement the minus operator on the Point2D class that we developed the other day (see the whole thing on GitHub ):

// In Point2D

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

⭐ Day 8, Part 1

The puzzle text can be found here.

Before we discuss strategy, we should recognize that Part 1 and Part 2 basically ask for the same kind of information, so we can share a lot of the implementation between them. The only real difference is how we find antinodes given two points. Everything else is the same.

Let’s write our countAntiNodes function with that concept in mind. Since Part 1 and Part 2 will have different logic to actually find the antinodes, we can pass the worker in as a function reference. The job of this worker is: Given two points a and b, and the diff of them, return a Set<Point2D> of all the antinodes created. I will acknowledge that calculating the diff and passing it in looks a bit weird, but I really wanted to write the workers as single expressions and passing in diff made that easier. Do it however you want though.

OK, let’s implement countAntiNodes:

// In Day08

private fun countAntiNodes(worker: (Point2D, Point2D, Point2D) -> Set<Point2D>): Int =
    nodes.flatMap { nodeList ->
        nodeList.flatMapIndexed { i, a ->
            nodeList.drop(i + 1).flatMap { b ->
                worker.invoke(a, b, a - b)
            }
        }.filter { it.isOnGrid() }
    }.toSet().size

Since our nodes is a List<List<Point2D>>, we want to loop through all of the lists and generate all of the combinations of nodes. For example, if we have the list [1, 2, 3], we want to generate [[1,2], [1,3], [2, 3]]. From there, we hand those pairs (which we call a and b) into our worker. Since the worker may generate spots outside the grid, we filter for this, and turn the whole structure into a Set, and return the size of the set.

The way the loops work might look a bit confusing, but once you’re used to flatMap, it should come easier. The outer flatMap goes through our nodes and evaluates each List<Point2D>. The next inner flatMapIndexed gives us a and its index within the node list. The final inner loop drops nodes we’ve already seen (i + 1) and gives us b. From here we can call the worker with a, b, and the difference between them.

That logic will remain the same for Part 1 and Part 2, let’s see how to implement the “generate anti nodes” function for Part 1:

// In Day08

private fun antiNodesForPart1(a: Point2D, b: Point2D, diff: Point2D): Set<Point2D> =
    if (a.y > b.y) setOf(a - diff, b + diff)
    else setOf(a + diff, b - diff)

I had a couple of different implementations of antiNodesForPart1 but settled on this. Basically, we figure out which point has the highest y value and add and subtract the diff, returning these two values as a Set<Point2D>.

All that’s left is to call our createAntiNodes function with a function reference (::) to antiNodesForPart1 and return the size of the resulting

// In Day08

fun solvePart1(): Int = 
    countAntiNodes(::antiNodesForPart1)

Star earned! Onward!

⭐ Day 8, Part 2

The puzzle text can be found here.

Most of the setup for Part 2 was done in Part 1, so all we need to do is write a function to calculate the antinode positions given the new rules. We will do this by setting up two sequences which generate points farther and farther away from the starting point (a in this case, it doesn’t really matter which we pick) in both directions, until one is generated off the grid.

The generateSequence function is really handy for things like this - given a starting condition (a), generate values forever (or until we stop taking from the sequence). In our case we’re generating two sequences - one that subtracts the diff and one that adds the diff so we have a complete vector. In each case we takeWhile the generated place is in the grid, and return the whole thing as a Set<Point2D>.

// In Day08

private fun antiNodesForPart2(a: Point2D, b: Point2D, diff: Point2D): Set<Point2D> =
    generateSequence(a) { it - diff }.takeWhile { it.isOnGrid() }.toSet() +
    generateSequence(a) { it + diff }.takeWhile { it.isOnGrid() }.toSet()

Like Part 1, Part 2 involves calling countAntiNodes with a function reference to antiNodesForPart2, which solves the puzzle.

// In Day08

fun solvePart2(): Int =
    countAntiNodes(::antiNodesForPart2)

Star earned! See you tomorrow!

Puzzle Input

⭐ Day 8, Part 1

⭐ Day 8, Part 2

Further Reading