By Eric Burden | December 12, 2023

It’s that time of year again! Just like last year, I’ll be posting my solutions to the Advent of Code puzzles. This year, I’ll be solving the puzzles in Kotlin. I’ll post my solutions and code to GitHub as well. If you haven’t given AoC a try, I encourage you to do so along with me!

# Day 12 - Hot Springs

Find the problem description HERE.

## The Input - Oh My Pun!

Today we have a relatively simple input for a deceptively difficult problem. Let’s start with the input, though. We have multiple lines where each line is split in half (by a single space every time, thankfully). The left half depicts different spring in different conditions and the right half indicates the sizes of known sizes of damaged groups. Oh, also, “Hot Springs”. Get it?

```
/**
* This enum represents the different states a spring
*
* @property rep The character that represents this enum variant.
*/
enum class Condition(val rep: Char) {
DAMAGED('#'), OPERATIONAL('.'), UNKNOWN('?');
companion object {
fun fromChar(char: Char): Condition {
return when (char) {
'#' -> DAMAGED
'.' -> OPERATIONAL
'?' -> UNKNOWN
else -> throw IllegalArgumentException("Cannot represent '$char' as a [Condition]!")
}
}
}
}
/**
* This class represents the condition record of a single row of springs.
*
* @property springs A list of the conditions of the springs.
* @property damagedGroups A list of known sizes of damaged groups.
*/
data class ConditionRecord(
val springs: List<Condition>, val damagedGroups: List<Int>
) {
companion object {
// Parse the input lines!
fun fromString(str: String): ConditionRecord {
val (conditionStr, groupStr) = str.split(" ").map { it.trim() }
val conditions = conditionStr.map(Condition::fromChar)
val groups = groupStr.split(",").map { it.toInt() }
return ConditionRecord(conditions, groups)
}
}
}
class Day12(input: List<String>) {
private val parsed =
input.filter { it.isNotEmpty() }.map(ConditionRecord::fromString)
}
```

Not too much to say about parsing today. LOTS to say about solving the puzzle, though.

## Part One - Novel Algorithm

In part one, our goal is to figure out which springs are damaged,
armed with the knowledge of which springs *might* be damaged and how large
all the damaged groups are. My first instinct was to try a depth-first search
over the springs, and honestly, it might have taken that approach less
time to run than it took me to type through my explanation for the dynamic
programming approach I ended up taking. See, I had an inkling that I was dealing
with overlapping sub-problems, and I was right! Now, on to the lengthy explanation!

### Example 1: .???.### 1,1,3

Note, my examples trim all the ‘.’ from the original puzzle input and prepend one ‘.’. I’m not sure this is 100% necessary, but it made it easier for me to think through. In this example, we have three groups of damaged springs (of lengths 1, 1, and 3) and 8 total springs, of which 2 are operational (’.’), 3 are damaged (’#’), and the remaining 3 are unknown (’?’). The essence of the DP approach here is to repeatedly calculate the number of possible combinations of springs under sets of increasing constraints, which are, in order:

- no damaged springs
- one damaged group of
`Damaged Groups`

[0] length - the first
*and*second damaged groups - all three damaged groups

For this example, I’ll walk through them one constraint at a time.

#### First Constraint: No Damaged Groups

```
Damaged Groups: []
Starting Conditions : [., ?, ?, ?, ., #, #, #]
Possible Combinations: [1, 1, 1, 1, 1, 1, 0, 0, 0]
/ | | | | | \
a b c d e f g
```

Note, the list of possible combinations is one longer than the list of springs, and is offset from the spring list by -1 as we walk through. This means that the first value in the list represents the number of possible ways to construct an empty list of springs with the given groups (in this case, none). Conveniently, there is one way to construct an empty list, so the value at (a) is 1.

The second value, (b) is also 1, because it is possible to construct a row with one operational spring when there are no damaged springs The values at (c-f) are similarly 1, because there is only one way a spring can be constructed of ‘.???.’ springs with no damage, which is ‘…..’.

On the other hand, (g) must be 0, because it is not possible to construct a row with one damaged section if there are no damaged springs allowed. This carries forward to the rest of the list, since ‘…..#’ and ‘…..#?’ are equally impossible.

#### Second Constraint: One group of one damaged section

In this second round, we are required to construct a row with one group of damaged springs consisting of only a single spring. It is important here to remember that each group of damaged springs must be separated by at least one operational section.

```
Groups: [1]
Starting Conditions : [., ?, ?, ?, ., #, #, #]
Possible Combinations: [1, 1, 1, 1, 1, 1, 0, 0, 0] with no groups
Possible Combinations: [0, 0, 1, 2, 3, 3, 1, 0, 0] add group of 1
/ / | | | | | \
a b c d e f g h
```

With a group length of 1, the pattern is readily recognized as
`current[i] = current[i - 1] + (previous[i - 2] ?: 0)`

. I’m using the
`?:`

notation here to indicate ‘zero if index out of bounds’.

We see that (a, b) are zero, which makes sense because you can’t construct
a row with a 1-wide defect from ’’ or ‘.’. ‘.?’ (c) *could* be ‘.#’, so
there’s one possible configuration at this point that meets our criteria.
‘.??’ (d) could be ‘.#.’ or ‘..#’ and ‘.???’ (e) could be ‘.#..’, ‘..#.’, or
‘…#’. (f) is the same as (e) with an extra operational section at the end.

(g) and (h) break the pattern, though because ‘#’ is a damaged spring, which
constrains our options for assigning the damaged group. At (g), there’s only
one way to assign a 1-wide group of damage, and at (h) there’s more damage
than we can accommodate. Notably, the value at (h) would be the same if the
springs were ‘.???.#?’ as well. This means we need to keep up with the width
of the damaged groups up to our current position and determine when we can’t
carry over combinations that were available up to the current point.
This would be when either the current group size is larger than the run of
possibly damaged springs *or* the spring just prior to where the group
would start is also DAMAGED (which would make the actual damaged
group too large). The logic goes like this:

```
damage can fit = group size <= run of DAMAGED and UNKNOWN
AND spring just prior to group start point is not DAMAGED
current[i] = if current section is not DAMAGED and damage can fit:
(A) current[i - 1] + (previous[i - 2] ?: 0)
else if current section is DAMAGED and damage can fit:
(B) (previous[i - 2] ?: 0)
else if current section is not DAMAGED:
(C) current[i - 1]
else:
(D) 0
```

That final `else`

applies if the current spring *is* DAMAGED and the group
size is larger than the current run of DAMAGED and UNKNOWN springs.

#### Third Constraint: Two groups of 1 damaged spring each

```
Groups: [1, 1]
Starting Conditions : [., ?, ?, ?, ., #, #, #]
Possible Combinations: [1, 1, 1, 1, 1, 1, 0, 0, 0] with no groups
Possible Combinations: [0, 0, 1, 2, 3, 3, 1, 0, 0] add group of 1
Possible Combinations: [0, 0, 0, 0, 1, 1, 3, 0, 0] add group of 1
/ | | | | \
a b c d e f
```

Here, we see that (a) is behaving as expected. At (a), the run of possible damaged springs is 1 and the spring there is not damaged, so branch (A) of our logic applies, yielding 0. The same is true for (b-d). Logically, we can see that there’s only one way to distribute two 1-wide damage regions into ‘.???.’, which is ‘.#.#.’. Recall that the damaged groups must be separated by an operational spring.

(e) is interesting because the spring there *is* damaged, which
ties up one of the damage groups and, again logically, we see that this
means that the *other* group of damaged springs can be distributed three
different ways, as ‘.#…#’, ‘..#..#’, or ‘…#.#’. Because the section at (e)
is damaged and the current group can fit in the run, this uses branch (B) of
our logic above.

(f) is a spring that *is* DAMAGED and the spring just prior to the
group start area is also DAMAGED (which would make a two-wide DAMAGED region),
so branch (D) applies.

#### Third Constraint: Two groups of 1 and one group of 3 DAMAGED springs

```
Groups: [1, 1, 3]
Starting Conditions : [., ?, ?, ?, ., #, #, #]
Possible Combinations: [1, 1, 1, 1, 1, 1, 0, 0, 0] with no groups
Possible Combinations: [0, 0, 1, 2, 3, 3, 1, 0, 0] add group of 1
Possible Combinations: [0, 0, 0, 0, 1, 1, 3, 0, 0] add group of 1
Possible Combinations: [0, 0, 0, 0, 0, 0, 0, 0, 1] add group of 3
/ | \
a b c
```

Our options are much more limited now, needing to add a 3-wide DAMAGED
group on top of the two 1-wide groups. This means that when we reach
section (a), we’ll only have space for either the two 1-wide groups or
or the one 3-wide group, but not both. At point (a), considering the
three-wide group, the current spring is *not* DAMAGED and we do have
enough room to insert the group, so we take branch (B) of our logic.

At section (b), the spring *is* damaged and we do *not* have space to
insert our 3-wide DAMAGED group, so we take branch (D). Finally, at section
(c), the section *is* DAMAGED and we *do* have space for our 3-wide
group, so we take branch (B). Except, now branch (B) would yield a result
of 0, but we can clearly see that there’s one way to arrange all three
DAMAGED groups: ‘.#.#.###’. If we examine the logic of branch (B), we can see
that with the first two groups, we were selecting the number of possible
combinations containing the previous groups at the point *before* we
were inserting the current group. Making a slight modification yields the
final algorithm:

```
damage can fit = group size <= run of DAMAGED and UNKNOWN
AND spring just prior to group start point is not DAMAGED
current[i] = if current section is not DAMAGED and damage can fit:
(A) current[i - 1] + (previous[i - (group size + 1)] ?: 0)
else if current section is DAMAGED and damage can fit:
(B) (previous[i - (group size + 1)] ?: 0)
else if current section is not DAMAGED:
(C) current[i - 1]
else:
(D) 0
```

The code below will follow this logic, with some minor indexing tweaks to
account for the fact that we can’t *really* shift the row of springs
representation over by one index as we did when visualizing these examples.

I encourage you to apply the logic above to this second example of a row of springs from today’s example input if you’re not 100% clear on how it works yet.

### Example 2: .?###???????? 3,2,1

```
Damaged Groups: [3, 2, 1]
Starting Conditions : [., ?, #, #, #, ?, ?, ?, ?, ?, ?, ?, ?]
Possible Combinations: [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] with no groups
Possible Combinations: [0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] add group of 3
Possible Combinations: [0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6] add group of 2
Possible Combinations: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 6, 10] add group of 1
```

And now, let’s turn that logic into actual code!

```
// enum class Condition(val rep: Char) { ... }
data class ConditionRecord(
val springs: List<Condition>, val damagedGroups: List<Int>
) {
// companion object { ... }
fun countAllPossibleConditions(): Long {
// The list of conditions should start with _one_ OPERATIONAL
// spring in order to support the algorithm for counting possible
// combinations of conditions. Excess OPERATIONAL springs at the
// beginning are removed.
val springs = mutableListOf(Condition.OPERATIONAL)
springs.addAll(this.springs.dropWhile { it == Condition.OPERATIONAL })
// Note, the first value in this list does not correspond to the first
// section, but to a hypothetical 'empty' section preceding the list
// of springs. This means there is exactly 1 possible
// configuration for an empty list of springs.
var possibleCombinations = MutableList(springs.size + 1) { 1L }
// Starting with the first DAMAGED section all the way to the end,
// set the number of possible combinations to zero, because there is
// no way to make a spring with damaged springs if there is no
// damage (our starting constraint).
//
// Starting Conditions : [., ?, ?, ?, ., #, #, #]
// Possible Combinations: [1, 1, 1, 1, 1, 1, 0, 0, 0]
for ((idx, _) in springs.withIndex()
.dropWhile { (_, c) -> c != Condition.DAMAGED }) {
possibleCombinations[idx + 1] = 0
}
// For each group size of damaged springs, we successively build upon
// the previous set of possible constraints, determining how many
// combinations are possible after adding each group as a constraint.
for (checkedGroupSize in damagedGroups) {
// Each new 'layer' of possibilities starts out empty.
val nextPossibleCombinations =
MutableList(springs.size + 1) { 0L }
var possiblyDamagedRunSize = 0
for ((idx, condition) in springs.withIndex().drop(1)) {
// Reset the 'group' of possibly DAMAGED springs to consider if
// we encounter an OPERATIONAL section.
if (condition == Condition.OPERATIONAL) {
possiblyDamagedRunSize = 0
} else {
possiblyDamagedRunSize += 1
}
// Here is where we implement our logic described exhaustively
// above:
// damage can fit = group size <= run of DAMAGED and UNKNOWN
// AND section just prior to group insertion point is not DAMAGED
// current[i] = if current section is not DAMAGED and damage can fit:
// (A) current[i - 1] + (previous[i - (group size + 1)] ?: 0)
// else if current section is DAMAGED and damage can fit:
// (B) (previous[i - (group size + 1)] ?: 0)
// else if current section is not DAMAGED:
// (C) current[i - 1]
// else:
// (D) 0
val groupCanFit = possiblyDamagedRunSize >= checkedGroupSize
val precedingIdx = (idx - checkedGroupSize).coerceAtLeast(0)
val notContiguousDamage =
springs[precedingIdx] != Condition.DAMAGED
val isNotDamaged = condition != Condition.DAMAGED
val damageCanFit = groupCanFit && notContiguousDamage
nextPossibleCombinations[idx + 1] =
if (isNotDamaged && damageCanFit) {
nextPossibleCombinations[idx] + possibleCombinations[precedingIdx]
} else if (condition == Condition.DAMAGED && damageCanFit) {
possibleCombinations[precedingIdx]
} else if (isNotDamaged) {
nextPossibleCombinations[idx]
} else {
0L
}
}
// Update the 'current' layer
possibleCombinations = nextPossibleCombinations
}
// Update the number of possible combinations with the result of
// determining possible combinations with the current group
// of DAMAGED springs.
return possibleCombinations.last()
}
}
class Day12(input: List<String>) {
// private val parsed = ...
fun solvePart1(): Long = parsed.sumOf { it.countAllPossibleConditions() }
}
```

Yes, I *know* that’s a lot of comments in addition to the *book* that was this
section. I told you it took a long time to write.

## Part Two - The Spring Has Sprung

I have *excellent* news! We’re back to misunderstanding documentation! And,
thankfully, it was just the *text* and not the *method*. Both the springs and
the lists of damaged groups are 5 times longer than we thought. No big deal!

```
// enum class Condition(val rep: Char) { ... }
data class ConditionRecord(
val springs: List<Condition>, val damagedGroups: List<Int>
) {
// companion object { ... }
// fun countAllPossibleConditions(): Long { ... }
fun unfold(): ConditionRecord {
val conditions =
listOf(springs + Condition.UNKNOWN).repeating().asSequence()
.take(5).flatMap { it }.toMutableList().dropLast(1)
val damagedGroups =
listOf(damagedGroups).repeating().asSequence().take(5)
.flatMap { it }.toList()
return ConditionRecord(conditions, damagedGroups)
}
}
class Day12(input: List<String>) {
// private val parsed = ...
// fun solvePart1(): Long = ...
fun solvePart2(): Long =
parsed.sumOf { it.unfold().countAllPossibleConditions() }
}
```

Nah, I don’t have much to say about this one. Used up all my words today.

## Wrap Up

Dynamic programming is hard! And, for me at least, it’s harder to *explain* than
it is to do. Today was certainly good practice in both regards, though. I don’t
think I used any new Kotlin-specific goodies, which is probably a good thing.