Advent of Code 2018 - Day 24, in Kotlin • Todd Ginsberg

On the penultimate date of Advent of Code 2018, we get to do more fighting simulation! And just like Day 15 , order of operations is really important. As a consequence, we’ll get to know all about sorting collections!

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

Problem Input

I decided to make life easier and break my input into two parts: immune system and infection. So in my repo, it will be two files that get loaded instead of one. This just made the parsing easier. We will parse these individual files below.

⭐ Day 24, Part 1

The puzzle text can be found here.

Let’s start by writing a small enum to identify which team the groups are on…

// In Day24

private enum class Team {
    ImmuneSystem,
    Infection
}

And from there we can start writing our Group data class, which we will extend later.

// In Day24

private data class Group(
    val team: Team,
    var units: Int,
    val unitHp: Int,
    val unitDamage: Int,
    val attackType: String,
    val initiative: Int,
    val weakTo: Set<String>,
    val immuneTo: Set<String>,
    var alive: Boolean = true
) {
    fun effectivePower(): Int =
        units * unitDamage
}

As you can see, we’ve made units and alive vars rather than vals. This is because during the fighting these can change and I don’t want to add the complexity to handle that with immutable Group classes. I’d rather have these be mutable and used simply and under controlled conditions rather then have the be immutable just for the sake of it. I usually try to go for immutability when I can, but this is one of those times when it’s not worth it to me.

We also calculate the effectivePower here, which can change over time (because the number of units can change) so it is a function and not a property. We will store its attack type, weaknesses, and immunities as simple Strings because we don’t really care what they are just that they match (or don’t). In theory we could just make team a String as well, but I feel the code looks nicer when doing comparisons against specific teams later.

Parsing

As I mentioned above, I’ve altered the input given to us just a little bit. Rather than one file that describes both groups in different sections that have headers, I’ve just broken it up into two files. I really only did it because it simplifies things while parsing, which is already pretty involved.

We’ll begin parsing the same way we have for most of the other days - with a companion function called of on our target class (in this casse Group).

// In Group, In Day24

companion object {
    private val pattern = """^(\d+) units each with (\d+) hit points (\([,; a-z]+\) )?with an attack that does (\d+) (\w+) damage at initiative (\d+)$""".toRegex()

    fun of(team: Team, input: String): Group {
        pattern.find(input)?.let {
            val (units, unitHp, strongWeak, unitDamage, attackType, initiative) = it.destructured
            return Group(
                team = team,
                units = units.toInt(),
                unitHp = unitHp.toInt(),
                unitDamage = unitDamage.toInt(),
                attackType = attackType,
                initiative = initiative.toInt(),
                weakTo = parseStrongWeak("weak", strongWeak),
                immuneTo = parseStrongWeak("immune", strongWeak)
            )
        }
    }

    private fun parseStrongWeak(kind: String, input: String): Set<String> =
        if (input.isBlank()) emptySet()
        else {
            val found = input.drop(1).dropLast(2).split("; ").filter { it.startsWith(kind) }
            if (found.isEmpty()) {
                emptySet()
            } else {
                found.first().split("to ")[1].split(",").map { it.trim() }.toSet()
            }
        }
}

Parsing out the digits should look familiar because they are in fixed locations. The tricky part is figuring out which weaknesses and immunities each group has. For that, we are matching against the possibility that there is a parenthetical group there. Even if there isn’t, we’ll still get a match (the empty String). And rather than come up with a complicated regular expression we’re just going to parse this string further manually. Essentially for any input that isn’t blank, we cut off the starting and ending parens, break it on ; (which may not exist), and figure out which one of those strings represents what we’re looking for. We parse that further by splitting it on , (if any), and trimming the results before turning it into a Set. Yes, this requires two passes and we could probably have done it with one pass, but I feel that this is easier to follow. Besides, we parse this once and never think about it again so there’s not much to gain here speed-wise. We’re trading a tiny bit of speed (maybe) for clarity (maybe?).

Fighting Logic

Now that we have a Group, we can determine how much damage is done when fighting each other.

// In Group, in Day24

fun calculateDamageTo(other: Group): Int =
    if (this.team == other.team) 0
    else effectivePower() * when (attackType) {
        in other.immuneTo -> 0
        in other.weakTo -> 2
        else -> 1
    }

I love that Kotlin lets us express this as one single expression. If the groups are on the same team, damage is zero. Otherwise we will multiply the effectivePower() by a force multiplier - 0x if the other group is immune to our attack, 2x if they are weak to our attack, and 1x if neither of those are true. Multiplying by 1x here is simpler than checking in an if and avoiding the multiplication. I love the power of when in Kotlin.

From there we can write the function that actually causes two groups to fight:

// In Group, in Day24

fun fight(other: Group): Int {
    val unitDeath = calculateDamageTo(other) / other.unitHp
    other.units -= unitDeath
    if (other.units <= 0) {
        other.alive = false
    }
    return unitDeath
}

In this function we calculate the damage we would do to other group and see how many of its units we have killed off. If they have zero or fewer units we mark them as no longer alive. And from this we return the number of unit deaths we’ve caused because we’ll need it later.

Target Selection

This is the part of the puzzle that gave me the most problems. We have to read the instructions carefully because the selection order is really important (sort of like on Day 15!). Let’s go over the logic for a single round of fighting.

// In Day24

private fun findTargets(combatants: List<Group>): Set<Pair<Group, Group?>> {
    val alreadyTargeted = mutableSetOf<Group>()
    return combatants.filter { it.alive }
        .sortedWith(compareByDescending<Group> { it.effectivePower() }.thenByDescending { it.initiative })
        .map { group ->
            group to combatants
                .filter { it.alive }   // Only fight the living
                .filterNot { group.team == it.team }  // Only fight the other team
                .filterNot { it in alreadyTargeted }  // Only fight somebody that isn't already a target
                .sortedWith(compareByDescending<Group> { group.calculateDamageTo(it) }.thenByDescending { it.effectivePower() }.thenByDescending { it.initiative })
                .filterNot { group.calculateDamageTo(it) == 0 }  // Remove any targets that we can't actually damage.
                .firstOrNull() // Account for the fact that we *may* not have a target
                .also {
                    // Add our selected target to the targeted list
                    if (it != null) alreadyTargeted.add(it)
                }
        }
        .toSet()
}

This function is used to have each Group pick its target. We return this data as a Set of Pairs, the second part of which is a nullable Group?. That’s because there may not be a target for each group. While picking, again, order is critical so we start by filtering out the dead groups and sorting them into the order in which they are allowed to pick opponents - by highest effective power, then by highest initiative.

Once our combatants are in order, we have them pick by going through all other fighters that are alive and on the other team. We again need to sort these potential targets by the amount of damage we can use them, then by their effective power (descending), and then by descending initiative. This section was the source of a few bugs for me, so be careful!

Then we filter out groups we can’t possibly damage, pick the best option if it exists, and add the target to the set we’re maintaining. That set is used to ensure that each group is only targeted at most once. Now we have our Pair<Group, Group?> and can repeat this for each of the living combatants.

Now we can use that data to actually fight one round!

// In Day24

private fun roundOfFighting(combatants: List<Group>): Int =
    findTargets(combatants)
        .sortedByDescending { it.first.initiative }
        .filterNot { it.second == null }
        .map { (attacker, target) ->
            if (attacker.alive) attacker.fight(target!!)
            else 0
        }
        .sum()

Again with the sorting. First we use the function we just wrote to find targets, order them by initiative, and then attack. In this function we record the total amount of unit deaths that occur in a single round. This is to catch when fighting stops. If we go an entire round without any deaths happening we know we’ve hit a point where we can’t possibly end the match. This will be important later, or for catching errors in our various sorts above (ask me how I know that).

The Battle

With our single round of fighting done, we can move on to the battle itself.

// In Day24

private fun fightBattle(combatants: List<Group>): List<Group> {
    var deaths: Int? = null
    while (deaths != 0) {
        deaths = roundOfFighting(combatants)
    }
    return combatants.filter { it.alive }
}

The battle will rage until no side scores a death against its opponent. This means it is truly over or can never end given the conditions. We loop through rounds over and over until this condition hits, and then return the list of survivors to the caller.

From there we can solve…

// In Day24

fun solvePart1(): Int =
    fightBattle(fighters).sumBy { it.units }

Star earned! Onward!

⭐ Day 24, Part 2

The puzzle text can be found here.

Good news! We don’t have to write any more sorting code! We need to keep fighting battles until we can get the immune system to win. Unlike Day 15, we don’t have to have every group survive. Even if one unit in one group survives that’s a win.

First, let’s write some code to boost the immune system by a given amount:

// In Day24
private fun boostImmuneSystem(boost: Int): List<Group> =
    fighters.map {
        it.copy(unitDamage = it.unitDamage + if (it.team == Team.ImmuneSystem) boost else 0)
    }

Because we mutate the Groups, we need to copy them. If they are part of the immune system we need to apply the boost factor. Otherwise, we just copy it as-is. By coping from the list of fighters we parsed earlier we can fight battles without worrying about the state of our Groups, because we’ll get all new ones for the next battle.

And now we can solve…

// In Day24

fun solvePart2(): Int =
    generateSequence(1, Int::inc).mapNotNull { boost ->
        val combatants = fightBattle(boostImmuneSystem(boost))
        if (combatants.all { it.team == Team.ImmuneSystem }) combatants.sumBy { it.units }
        else null
    }.first()

We get to use generateSequence here, which will keep incrementing numbers until we return a non-null value. Inside the lambda, we boost up each of our combatants, and fight the battle. If the only survivors are part of the immune system, we add up their surviving units, otherwise we return null.

Star earned! One more day left… \

⭐ Day 24, Part 1

⭐ Day 24, Part 2

Further Reading