Advent of Code 2024 - Day 19, in Kotlin - Linen Layout • Todd Ginsberg

This might be the least amount of code I’ve written to solve an Advent of Code puzzle in a long time. This is partly a testament to the Kotlin Standard Library, having constructs that are nice to work with, and partly due to the design of the puzzle lending itself to a shared solution for both parts if we’re willing to make a slight time trade-off for part 1.

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

Puzzle Input

Today’s input will come to us from our test cases as a List<String> which we will break up into two lists - patterns and designs. To get the patterns, we split the first row of input, taking care to trim each of the results. Sure, we could write a regular expression to do that for us in split, but this seems more clear for people who don’t read RegEx. The designs list is the tail end of the input, so dropping the first two rows gives us that.

class Day19(input: List<String>) {

    private val patterns: List<String> = input.first().split(",").map { it.trim() }
    private val designs: List<String> = input.drop(2)

}

Strategy and Shared Code

It turns out we can solve both parts of today’s puzzle with the same recursive function. We’re taking a bit of a time hit on the first part, but not a huge one. Given the fact that we can use the same function to solve both parts in a reasonable amount of time (a few milliseconds), let’s go with this.

Today we’ll write a single recursive function to count the total number of ways to make up a design from the set of patterns. We’ll be able to answer Part 1 (count the number of designs that have at least one solution) and Part 2 (get the sum of all possible solutions for all designs).

The function we will write is called makeDesign and takes two arguments: a design or part of a design we wish to make, and a cache. We will end up repeating a lot of work (evaluating the same patterns) so a cache here is going to be essential to get the runtime of the function down to something reasonable. Since the cache is not a detail the caller to the function really needs to know, we’ll provide an empty map as the default, so they don’t have to specify it.

// In Day19

private fun makeDesign(design: String, cache: MutableMap<String, Long> = mutableMapOf()): Long =
    if (design.isEmpty()) 1
    else cache.getOrPut(design) {
        patterns.filter { design.startsWith(it) }.sumOf {
            makeDesigns(design.removePrefix(it), cache)
        }
    }

The first thing to do with any recursive function is to handle the base case. In this function, the base case is when design is the empty string (no more parts of the design to find). When we get there we know we have one way to make the empty string (select no patterns).

Next we check to see if our design is in the cache already. If so, we return that number (which must be a Long, as they get huge). Otherwise, getOrPut runs the lambda we’ll define to calculate the total number of ways to create the given design.

Finally, we go through all of the patterns and keep the ones that our design startsWith. For example if we have patterns “A”, “AB”, and “ABC”, and our design is “ABD”, we would select “A”, and “AB”. We then get the sumOf each of the designs minus this pattern. Using our example again, we would call makeDesigns recursively with “BD” (“A” removed) and “D” (“AB” removed). We pass along the cache. If you view recursive functions like a tree, that might help make sense of the calls happening here.

Returning from this function will give us the total number of ways (a Long!) to create the design given the patterns we know about.

⭐ Day 19, Part 1

The puzzle text can be found here.

Using our makeDesign function, we can count how many of the designs have at least one solution to solve Part 1.

// In Day19

fun solvePart1(): Int =
    designs.count { makeDesign(it) > 0 }

Star earned! Onward!

⭐ Day 19, Part 2

The puzzle text can be found here.

Instead of counting solutions like we did in Part 1, we can get the sumOf all solutions to solve Part 2.

// In Day19

fun solvePart2(): Long =
    designs.sumOf { makeDesign(it) }

Star earned! See you tomorrow!

Puzzle Input

Strategy and Shared Code

⭐ Day 19, Part 1

⭐ Day 19, Part 2

Further Reading