Advent of Code 2023 - Day 12, in Kotlin - Hot Springs • Todd Ginsberg

I found today’s puzzle quite challenging. Probably the next most challenging after Day 10 - Pipe Maze . My original solution was a mess, but I cleaned it up to a point where I believe if it isn’t fully clear, it’s at least explainable.

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

Puzzle Input

We will take our input in as List<String> and keep it as a property (a private val) because we’ll convert it row-by-row when we need it.

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

    private fun parseRow(input: String): Pair<String, List<Int>> =
        input.split(" ").run {
            first() to last().split(",").map { it.toInt() }
        }
}

We will define a parseRow function that turns our String into a Pair<String, List<Int>> where the String is the spring arrangement and the List<Int> are the damage values. We split our input on a space, and then call the run extension from the Kotlin Standard Library to make this a single function chain.

⭐ Day 12, Part 1

The puzzle text can be found here.

We’re going to write a big recursive function to go through each arrangement springs and apply some damage. This will eventually handle every single arrangement possible according to the rules. In order to speed things up (especially in part 2 with real input) we will cache results. It’s not super important for part 1 but critical for part 2, so let’s just build it in now.

Here’s the countArrangements recursive function, which I will explain below.

// Day12

private fun countArrangements(
    springs: String,
    damage: List<Int>,
    cache: MutableMap<Pair<String, List<Int>>, Long> = HashMap()
): Long {
    val key = springs to damage
    cache[key]?.let {
        return it
    }
    if (springs.isEmpty()) return if (damage.isEmpty()) 1 else 0

    return when (springs.first()) {
        '.' -> countArrangements(springs.dropWhile { it == '.' }, damage, cache)

        '?' -> countArrangements(springs.substring(1), damage, cache) +
                countArrangements("#${springs.substring(1)}", damage, cache)


        '#' -> when {
            damage.isEmpty() -> 0
            else -> {
                val thisDamage = damage.first()
                val remainingDamage = damage.drop(1)
                if (thisDamage <= springs.length && springs.take(thisDamage).none { it == '.' }) {
                    when {
                        thisDamage == springs.length -> if (remainingDamage.isEmpty()) 1 else 0
                        springs[thisDamage] == '#' -> 0
                        else -> countArrangements(springs.drop(thisDamage + 1), remainingDamage, cache)
                    }
                } else 0
            }
        }

        else -> throw IllegalStateException("Invalid springs: $springs")
    }.apply {
        cache[key] = this
    }
}

If you think that’s complicated, you should have seen the version I had before cleaning this up. Seriously, it was a huge mess that I wouldn’t be proud to show anybody.

The very first thing we do in countArrangements is to check the cache. We create the key (which we will use later even if the cache check misses) and then check the cache. If we’ve seen the combination of springs and damage before there is no sense in calculating them again, so we return the pre-calculated value from the cache.

I do want to note that we could have implemented the cache key as anintArrayOf(springsOffset, damageOffset) and not dealt with manipulating the springs String and damage List, but I thought the resulting code was harder to read.

After we’ve decided that this is new work to be done (the cache doesn’t remember the answer), we check to make sure we’ve not run out of input by checking if springs.isEmpty(). If we have, we’re done one way or another. If we’re also out of damage to portion out, we have found 1 way that we could arrange the springs. Otherwise, if there is damage to deal out but no places in springs, we’ve found a way that doesn’t work and can return 0. We won’t bother caching this as it is a trivial operation.

Now that we have the basic conditions checked, we can start figuring out if we can fit some damage at the start of the spring. We do this by looking at the first character of the springs. If the first character is a . (meaning: it is not damaged or questionable) we can basically ignore it in this specific case. So we recursively call countArrangement with the same damage values but only after stripping all of the . characters off of the springs.

If the first character of springs is a ? that means it can either be damaged (#) or operational (.). That means we need to count how many arrangements there are for both possibilities by recursively calling countArrangements with both options. The case where we pretend the spring is damaged at this point is shown by replacing the first character of springs with #. The pretend . case is handled by removing the ? and not bothering to add a real . because as above, we’ll just remove it anyway.

The case where the first character of springs is #, meaning damaged, is interesting. Either this is really damaged or we are questioning what would happen if it were damaged (from the ? case). We’re about to apply some damage (possibly) so let’s set aside thisDamage to represent the first value in the damages list and remainingDamage to represent the rest of the list.

We’ve got a few conditions to check here, all of which depend on whether there are enough characters left in springs to hold all of theDamage, and if so, that there aren’t any operational spots in the space the damage is going to go.

If those hold true, we check to see if we would be consuming the rest of the springs string with thisDamage. If we are in this state we’ve either found a combination that works (when there is no damageRemaining) or an impossible state (there is damageRemaining). If the character immediately following the characters taken up by thisDamage is a # (meaning, also broken), we’ve reached another impossible state. We know this is impossible because we wouldn’t ever see ???# for example and have the ??? replaced by 3 damage.

In all other cases, we recursively call countArrangeents by advancing the strings string to the place after thisDamage and passing the remainingDamage so thisDamage isn’t part of subsequent calculations.

All other conditions are either impossible (return 0) or errors (I didn’t hit this, but figured I’d put it there rather than define an enum for the character meanings or returning 0 (which would be acceptable, I guess).

The final thing to do in this method is to store our result in the cache by using apply.

Finally, we can run this and get our result:

// Day12

fun solvePart1(): Long =
    input
        .map { parseRow(it) }
        .sumOf { (springs, damage) -> countArrangements(springs, damage) }

Star earned! Onward!

⭐ Day 12, Part 2

The puzzle text can be found here.

We’ve got everything we need to handle part 2 already, we just need to unfold each row of input.

// In Day12

private fun unfold(input: Pair<String, List<Int>>): Pair<String, List<Int>> =
    (0..4).joinToString("?") { input.first } to (0..4).flatMap { input.second }

We set up a range of 0..4 so we get 5 loops and call joinToString specifying we want ? as a delimiter and input.first as the string to join We do the same for the second value of the input, but since that’s a list we flatMap them all together so we don’t end up with List<List<Int>>.

All that’s left to do is unfold our input before we countArrangements like in part 1.

// In Day12

fun solvePart2(): Long =
    input
        .map { parseRow(it) }
        .map { unfold(it) }
        .sumOf { (springs, damage) -> countArrangements(springs, damage) }

Alternatively, you could write .map { unfold(parseRow(it)) } and skip one of the map calls if you find that easier to read.

Star earned! See you tomorrow!

⭐ Day 12, Part 1

⭐ Day 12, Part 2

Further Reading