Discussion on: AoC Day 24: Immune System Simulator 20XX

View post

Replies for: I've only done the parsing so far but it warrants a look all on its own. Reading the description I feel fully vindicated in my advocacy of parser c...

Part 1

It's another iterative simulation with a bunch of details to implement. I chose to do it completely functionally with immutable data, with the overall battle state updated on each step and threaded through the entire calculation. As before I simulated the whole battle as a sequence of states, and the part 1 result can be obtained from the last in this sequence:

fun battle(groups: Set<ArmyGroup>): Sequence<Set<ArmyGroup>> = sequence {
    var remaining = groups
    while (remaining.map { g -> g.type }.toSet().size == 2) {
        remaining = fight(remaining)
        yield(remaining)
    }
}

fun part1(groups: Set<ArmyGroup>): Int =
    battle(groups).last().map { g -> g.count }.sum()

The fight() function must therefore compute the next state for the battle. First it does target selection, the result of which is a map of attacking groups IDs to defending groups IDs. I used IDs as the data objects are immutable and will be getting replaced with modified versions as the battle proceeds.

Target selection needs a set of unselected groups and the set of selections to be threaded through the computation so I wrapped both in a container data structure and gave it a helper function for adding new selections:

typealias TargetSelection = Map<Int, Int>

data class SelectionBuilder(val unselected: Set<ArmyGroup>, val selected: TargetSelection) {
    fun add(attack: ArmyGroup, defend: ArmyGroup) = 
        SelectionBuilder(unselected - defend, selected + Pair(attack.id, defend.id))
}

Selecting targets and fighting involves a few sorts and orderings so I used Kotlin Comparators again:

val initiativeOrder = Comparator<ArmyGroup> {
    x, y -> y.unit.initiative - x.unit.initiative   
}

val attackingOrder = Comparator<ArmyGroup> {
    x, y -> y.effectivePower - x.effectivePower
}.then(initiativeOrder)

fun defendingOrder(attack: Attack) = Comparator<ArmyGroup> {
    x, y -> x.damageFrom(attack) - y.damageFrom(attack)
}.then(attackingOrder.reversed())

These depends on a couple of simple helpers which capture the business logic quite neatly:

val ArmyGroup.effectivePower: HitPoints get() = count * unit.attack.damage

fun ArmyGroup.damageFrom(attack: Attack): HitPoints = when {
    unit.immunities.contains(attack.type) -> 0
    unit.weaknesses.contains(attack.type) -> attack.damage * 2
    else -> attack.damage
}

Building the target selection now becomes:

Sort the groups in attack order
For each attacking group select the maximum opposing group in defending order
Add the pairing to the selection, removing the defending group from future candidates

fun selectTargets(groups: Set<ArmyGroup>): TargetSelection {
    return groups.sortedWith(attackingOrder).fold(SelectionBuilder(groups, mapOf())) { selection, attackingGroup ->
        val opposingGroups = selection.unselected.filter { g -> g.type != attackingGroup.type }
        val defendingGroup = opposingGroups.maxWith(defendingOrder(attackingGroup.unit.attack))
        if (defendingGroup == null) 
            selection
        else 
            selection.add(attackingGroup, defendingGroup)
    }.selected
}

Once we've done the target selection we run the fight. We take the target selection, order the attackers by initiative and put them back into a (now ordered) list of attacker, defender pairs:

val orderedAttackIds = targetSelection.keys
                            .mapNotNull(groups::find)
                            .sortedWith(initiativeOrder)
                            .map { g -> Pair(g.id, targetSelection[g.id]!!) }

Running the attacks is pretty simple but we have to be careful to use the current state at each step. groups is the set of Army Groups at the beginning of the fight round, groups_ is the set at the current point in the attack sequence. One nice aspect of this style of design is that by swapping those around it's trivial to change the behaviour from sequential to parallel (i.e. all attacks happen at once), should that requirement change.

orderedAttackIds.fold(groups) { groups_, (attackingGroupId, defendingGroupId) ->
    val attackingGroup = groups_.find(attackingGroupId)
    val defendingGroup = groups_.find(defendingGroupId)
    if (attackingGroup == null || defendingGroup == null) // might be eliminated
        groups_
    else {
        val otherGroups = groups_.filterNot { g -> g.id == defendingGroupId }.toSet()
        val damage = defendingGroup.damageFrom(attackingGroup.unit.attack) * attackingGroup.count
        val unitsKilled = minOf(damage / defendingGroup.unit.hitPoints, defendingGroup.count)
        if (unitsKilled == defendingGroup.count)
            otherGroups
        else
            otherGroups + (defendingGroup - unitsKilled)
    }
}