# Advent of Code 2023 - Day 12, in Kotlin - Hot Springs

Kotlin solutions to parts 1 and 2 of Advent of Code 2023, Day 12: 'Hot Springs'

Posted on

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 an`intArrayOf(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!