Advent of Code 2023 - Day 19, in Kotlin - Aplenty • Todd Ginsberg

This writeup is a bit late because I got busy around the time it came out and I struggled to find a solution that I was happy with. My original was very messy, but I’m mostly happy with this one.

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

Puzzle Input

Before we can parse our input we have quite a few support classes to define. First up, a class to represent a Workflow.

// In Day19

private data class Workflow(val name: String, val rules: List<Rule>) {
    companion object {
        fun of(input: String): Workflow =
            Workflow(
                input.substringBefore("{"),
                input
                    .substringAfter("{")
                    .substringBefore("}")
                    .split(",")
                    .map { rule -> Rule.of(rule) }
            )
    }
}

The Workflow has a name and the rules associated with it. For now, we’ll just define the of function to create a Workflow from a String, and leave the rest for later.

We will define Rule as a sealed class (the two implementations we need are below), also with an of function to create them from a String.

// In Day19

private sealed class Rule(val nextWorkflow: String) {
    companion object {
        fun of(input: String): Rule =
            if ('>' in input || '<' in input) {
                val variable = input[0]
                val test = input[1]
                val amount = input.substring(2).substringBefore(":").toInt()
                val target = input.substringAfter(":")
                RangeCheck(
                    variable,
                    if (test == '<') (1..<amount) else (amount + 1..4000),
                    if (test == '<') (amount..4000) else (1..amount),
                    target
                )
            } else Other(input)
    }

    abstract fun eval(partRating: PartRating): String?
}

The Rule class defines an abstract eval function for evaluating a PartRating (which we will define later).

As you can tell from the of function/parser we have two implementations of Rule. First is a RangeCheck which checks to see if the variable we care about is within a range.

// In Rule

class RangeCheck(
    val category: Char,
    val range: IntRange,
    val antiRange: IntRange,
    nextWorkflow: String
) :
    Rule(nextWorkflow) {

    override fun eval(partRating: PartRating): String? =
        if (partRating[category] in range) nextWorkflow else null
}

Since in part 2 we discover the range of x, m, a, and s are between 1 and 4000, we’ll use that here rather than strictly modeling this as greater than or less than the amount. We also have an antiRange which is the opposite of what we match with range. We need this for part 2 and it’s just easier to put it in here rather than explain it later. So if the rule is <1000, the range will be 1..999 and the antiRange will be 1000..4000.

The other part to note in RangeCheck is the eval function. It checks to see if the partRating falls in the range and if so, returns the nextWorkflow. Otherwise if the test fails, we return null (which will indicate to not reroute our checking, which we write later).

All Other types of rules have the same result - reroute to the nextWorkflow.

// In Rule

class Other(nextWorkflow: String) : Rule(nextWorkflow) {

    override fun eval(partRating: PartRating): String = nextWorkflow
}

And finally, PartRating which is another data class that holds the x, m, a, and s part rating data in a Map. It also defines a parser in of to turn a String into a PartRating. I’ve added an operator get to allow us to support indexable access to PartRating (so, partRating['x'] instead of partRating.categories['x']).

// In Day19

private data class PartRating(val categories: Map<Char, Int>) {

    val total: Int = categories.values.sum()

    operator fun get(category: Char): Int =
        categories.getValue(category)

    companion object {
        fun of(input: String): PartRating =
            PartRating(
                input
                    .removeSurrounding("{", "}")
                    .split(",")
                    .associate {
                        it.first() to it.substring(2).toInt()
                    }
            )
    }
}

And finally, we can parse all of our input. We will put the workflow into a Map<String,Workflow> indexing them by name. We make use of the associateBy function in Kotlin which turns our List<Workflow> into a Map<String,Workflow> for us! We put the partRatings into a List<PartRating>.

The input itself is unused past this point so we don’t need to define it as a property.

class Day19(input: List<String>) {

    private val workflows = input.takeWhile { it.isNotBlank() }.map { Workflow.of(it) }.associateBy { it.name }
    private val partRatings = input.dropWhile { it.isNotBlank() }.drop(1).map { PartRating.of(it) }

}

⭐ Day 19, Part 1

The puzzle text can be found here.

In order to solve part 1, we need to add an evaluate function to Workflow. The purpose of this function is to take a single PartRating and run it through the rules until an answer is produced.

// In Workflow

fun evaluate(part: PartRating, workflows: Map<String, Workflow>): String =
    rules.firstNotNullOf { rule ->
        when (val answer = rule.eval(part)) {
            null, in setOf("A", "R") -> answer
            else -> workflows.getValue(answer).evaluate(part, workflows)
        }
    }

The evaluate function is recursive - meaning it calls itself until an answer is determined. We do this by looking at all of the rules on the current workflow. If the rule is null, A (accept), or R (reject), we return the answer from the rule. Otherwise, we go find a workflow named after the answer and evaluate it, and so on. We eventually return either an R or an A.

And now we can solve part 1.

// In Day19

fun solvePart1(): Int =
    partRatings.filter { rating ->
        workflows.getValue("in").evaluate(rating, workflows) == "A"
    }.sumOf { it.total }

We go through each partRating and keep those whose end result after calling evaluate starting with the in workflow is “A” (accepted). Anything else (R) is not accepted, so we can filter them out. We get the sumOf the total workflows that result in “A” and that’s our answer.

Star earned! Onward!

⭐ Day 19, Part 2

The puzzle text can be found here.

Let’s discuss how we’re going to solve part 2 before jumping into any of the code. Basically, we need to think about the full set of possible outcomes. Lets suppose we have a workflow that has one rule that accepts everything. How many possibilities are there for that? There are four categories (x, m, a, and s) and 4000 accepted values for each so we have 4000^4 (256,000,000,000,000) possibilities. Now lets suppose we have a single rule that allows us to take 1..1000 for x and anything else. Meaning, x with a value of 1001 to 4000 is invalid. Now how many combinations do we have (1,000 * 4,000^3). This is where our antiRange comes in. So the strategy is, we’ll start with four ranges of 1..4000 and pare it down via the rules. If a rule says it allows a range, we remove all other values from the range we’re handed, and then recursively call countRanges on the workflow that we would have redirected to because of that rule.

Eventually, we will either get to a Reject in which case we return that all that work means zero possibilities, or an Accept which means we multiply all of the newly constrained ranges together. Because there are multiple paths through the workflow, we will add all of the possibilities together.

In order to support the code we’ll write to implement this idea, we’ll add some extensions to IntRange to make it a bit easier to work with.

// In Extensions.kt

infix fun IntRange.intersectRange(other: IntRange): IntRange =
    maxOf(first, other.first)..minOf(last, other.last)

fun IntRange.length(): Int =
    last - first + 1

The intersectRange function returns a new IntRange representing the intersection of the two given ranges. We implement this as infix to make the syntax a bit nicer. And length returns the overall size of the IntRange using math, instead of enumerating all of the values and counting them.

Now we can write our recursive countRanges function.

// In Workflow

fun countRanges(allWorkflows: Map<String, Workflow>, ranges: Map<Char, IntRange>): Long =
    when (name) {
        "R" -> 0
        "A" -> ranges.values.map { it.length().toLong() }.reduce(Long::times)
        else -> {
            val constrainedRanges = ranges.toMutableMap()
            rules
                .map { it to allWorkflows.getValue(it.nextWorkflow) }
                .sumOf { (rule, workflow) ->
                    when (rule) {
                        is Rule.Other -> workflow
                            .countRanges(allWorkflows, constrainedRanges)

                        is Rule.RangeCheck ->
                            constrainedRanges.getValue(rule.category).let { before ->
                                constrainedRanges[rule.category] = before intersectRange rule.range
                                workflow.countRanges(allWorkflows, constrainedRanges).also {
                                    constrainedRanges[rule.category] = before intersectRange rule.antiRange
                                }
                            }
                    }
                }
        }
    }

As with any recursive function, it’s a good idea to write our end conditions first. So we’ll check if we’ve reached an R or an A workflow and either return 0 or the product of all the range sizes.

Otherwise, we’re going to have to constrain our ranges given a rule, and recurse. To do this, we create a copy of the ranges and call it constrainedRanges. It is also mutable so we can change it. We go through all of the rules and for each one pair it up with the workflow that it would result in. Then we get the sumOf the constrainedRanges. In the case that the rule is an Other, we simply recurse without doing any more work. In the case of a RangeCheck we need to only consider the rule.range values plus any from the constrainedRanges (the overlap of them, to be more exact) which we get via intersectRange. With this value, we recursively call the workflow the rule would redirect to. When we’re back from that, we need to pretend that we didn’t just do that so the next rule will have a chance to calculate how many valid answers it has, so we intersect the constranedRanges with the antiRange from the rule. It is important to note that this intersection is on the set of ranges before we do any other intersections.

Now we can solve part 2.

// In Day19

fun solvePart2(): Long =
    workflows.getValue("in")
        .countRanges(
            workflows.withDefault { Workflow(it, emptyList()) },
            "xmas".associateWith { 1..4000 }
        )

Go get the in range and ask it to countRanges. Because we didn’t add “A” or “R” as workflows to the workflows map, we’ll tell our workflows map to return an empty no-op Workflow if we try to look one up. I also really like that Kotlin has associateWith which allows us to turn our “xmas” String into a Map<Char,IntRange>.

Star earned! See you tomorrow!

⭐ Day 19, Part 1

⭐ Day 19, Part 2

Further Reading