Advent of Code 2024 - Day 23, in Kotlin - LAN Party • Todd Ginsberg

Today was fun for me because I got to refactor some code we used in 2018 to solve another graph puzzle on Day 23! I’m way more satisfied with the code I wrote today than the code I wrote six years ago. Who knows, maybe Advent of Code 2030 Day 23 will give us another opportunity to look back, cringe a bit, and rewrite all of this. :)

The title of today’s puzzle - “LAN Party” also made me smile. I have good memories of LAN parties, especially at my first job where we’d finish our day and then sit around and play Quake (dating myself a bit, eh?) on the company LAN and computers. Back in the day when developers could get away with having things like Quake on their work computers, and a hole in the company firewall (that I may have added) to stream games!

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

Puzzle Input

Today our input will once again be delivered from our test case to our puzzle solution as a List<String>. We’ll parse this into a Map<String, Set<String>> called connections where the key is a node and the value is its set of neighbors.

class Day23(input: List<String>) {

    private val connections: Map<String, Set<String>> = parse(input)

}

To parse the input, we split each row and then flatMap it into a List<Pair<String,String>>. The trick here is to map both sides of the split so we capture each side of the bidirectional relationship. So if the original String is “a-b”, we want Pair(a,b) and Pair(b,a). Then we groupBy specifying the first element of the pair is the key and the second element is the value. Since the value is a List<String> we need to mapValues to turn them into a Set<String> instead.

// In Day23

private fun parse(input: List<String>): Map<String, Set<String>> =
    input.map { it.split("-") }
        .flatMap { (left, right) -> listOf(left to right, right to left) }
        .groupBy({ it.first }, { it.second })
        .mapValues { it.value.toSet() }

⭐ Day 23, Part 1

The puzzle text can be found here.

Before we get too far into today’s solutions, we should probably go over one term we’ll see a few times - “clique ”. Basically, in a graph, a clique is the set of vertices such that every vertex in the set is a neighbor of every other vertex in the set. So every triangle is a clique because every vertex is a neighbor of every other vertex.

To solve Part 1, we need to find all cliques of size 3 that have at least one node starting with “t” in it. We’ll break this down into a couple of phases. First, let’s write a findCliques function which takes a start vertex and enumerates all cliques that this start is part of. We do this by getting all the neighbors of start and then pairing them all up in every combination via allPairs, which we will define below.

Next, since each element of the pair is a known neighbor of start, we need to test to make sure they are neighbors of each other. If not, we filter them out. If so, we map the start and both parts of the pair into a List and then sort it.

// In Day23

private fun findCliques(start: String): List<List<String>> =
    connections
        .getValue(start)
        .allPairs()
        .filter { (b, c) -> c in connections.getValue(b) }
        .map { (b, c) -> listOf(start, b, c).sorted() }

In order to find allPairs of the elements of a Set, we will write an extension function to make calling it a bit more fluid. It will return a List<Pair<T,T>> representing each pair of elements in the set.

// In Day23

private fun <T> Set<T>.allPairs(): List<Pair<T, T>> =
    toList().let { list ->
        list.flatMapIndexed { index, first ->
            list.drop(index + 1).map { second ->
                first to second
            }
        }
    }

We first need to turn our set into a list so we can get ordered traversal, then we use our flatMapIndexed and map trick to iterate through each of the elements and the subsequent elements of each of those, pairing them up.

We now have enough to answer Part 1.

// In Day23

fun solvePart1(): Int =
    connections.keys
        .filter { it.startsWith("t") }
        .flatMap { findCliques(it) }
        .distinct()
        .size

We look at each of the keys in the connections map, filter down to any that start with “t”, and call findCliques on each one. Since we’ll have many duplicates, we reduce this to the distinct set of cliques and then return the size for our answer.

Star earned! Onward!

⭐ Day 23, Part 2

The puzzle text can be found here.

When I read this part of the puzzle I knew I would need an algorithm to find the largest clique. I was pretty sure I’d written one of these before and after searching wikipedia for the name I was forgetting, I came across The Bron–Kerbosch algorithm . That rang a bell, and after a brief search I found out, ironically, that I used this same algorithm to solve Advent of Code 2018 Day 23 , exactly six years ago from today!

Now, at the time I was probably pretty happy with that implementation of the Bron-Kerbosch algorithm. Thankfully, I have grown as a developer and felt compelled to rewrite the iterative approach into a nice recursive function. I also removed several usages of Kotlin’s Hold My Beer operator (!!).

It’s interesting to note that between 2018 (using Kotlin 1.3.11) and 2024 (using Kotlin 2.1.0), the semantics of maxBy have changed. Starting with Kotin 1.4, many functions were removed, renamed, and reintroduced (PDF Link) with new semantics, for the better. Whereas maxBy used to return a nullable result, it now returns a non-null result and throws an exception if no non-null result is found. To cover the case when we do want a null, we can use maxByOrNull instead. This is now the standard naming structure for Kotlin.

Anyway, I suppose I should be happy that looking back on 2018 code, I immediately see a few things I’d like to change, because otherwise I probably wouldn’t have grown much as a programmer in the intervening six years, eh?

Let’s look at the findLargestClique function and then I’ll explain it.

// In Day23

private fun findLargestClique(
    p: Set<String>,
    r: Set<String> = emptySet(),
    x: Set<String> = emptySet()
): Set<String> =
    if (p.isEmpty() && x.isEmpty()) r
    else {
        val withMostNeighbors: String = (p + x).maxBy { connections.getValue(it).size }
        p.minus(connections.getValue(withMostNeighbors)).map { v ->
            findLargestClique(
                p intersect connections.getValue(v),
                r + v,
                x intersect connections.getValue(v)
            )
        }.maxBy { it.size }
    }

While I am not a huge fan of variable names like p, r, x, and v, I’ve left them in as they directly reflect the variable names used in the Wikipedia page describing this algorithm. I felt it was best to keep the names the same so people can refer to both resources with a constant set of concepts.

As mentioned, this is a recursive function to find all of the largest cliques given p, a set of vertices. As with all recursive functions, we first handle the base case where we’ve run out of things to look for and return the working set (r) as a clique. For non-base cases, we want to find the vertex among p and x with the largest number of neighbors. We then remove that neighbor from p and recursively call findLargestClique with the new state.

We now have enough to solve part 2!

// In Day23

fun solvePart2(): String =
    findLargestClique(connections.keys).sorted().joinToString(",")

We findLargestClique, seeding it with all of the keys from our connections map. We take the single result and sort it so the names of the vertexes are alphabetical, and then joinToString to get our output in the format the puzzle asks for.

Star earned! See you tomorrow!

Puzzle Input

⭐ Day 23, Part 1

⭐ Day 23, Part 2

Further Reading