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.
Top comments (0)