AoC Day 24: Immune System Simulator 20XX

Christmas Eve! I'm super excited. Along with the anticipation for tomorrow, we also get the challenge for Day 24 where we are simulating an immune system battle raging inside a reindeer!

Each side -- immune system and infection -- has armies made up of units with different hit points, attack points, type strengths and weaknesses, not unlike some beloved animated battle monsters. We need to figure out how to help this reindeer get better!

Comments

[Neil Gall]

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 combinators all month. I've been tempted a couple of times to build a full-blown lexer/parser combination but have gotten by so far with simple character parsers. Today let's do the full thing.

The difference is that the lexer stage differentiates interesting parts of the input from delimiters and unwanted information. In a real language you often filter out comments here. The result is a sequence of tokens rather than characters, and you write the parser in terms of a grammar of tokens.

First a simple model. We'll start with some type aliases. I don't like to see native or primitive types in real data models. The structure is much as the input format.

typealias AttackType = String
typealias HitPoints = Int
typealias Initiative = Int

data class Attack(
    val damage: HitPoints,
    val type: AttackType
)

data class ArmyUnit(
    val hitPoints: HitPoints,
    val attack: Attack,
    val initiative: Initiative,
    val weaknesses: Set<AttackType>,
    val immunities: Set<AttackType>
)

data class ArmyGroup(
    val count: Int,
    val unit: ArmyUnit
)

data class Battle(
    val immuneSystem: Set<ArmyGroup>,
    val infection: Set<ArmyGroup>
)

Lexer

The lexer matches all interesting words and symbols in the input and ignores the rest. This is really useful as there are irregular line splits and other whitespace differences in the text. The lexer gets rid of all that.

val keywords = listOf(
    "an", "at", "attack",
    "damage", "does",
    "each",
    "hit",
    "immune", "infection", "initiative",
    "points",
    "system",
    "that", "to",
    "units",
    "weak", "with"
)

val terminals = Terminals
    .operators("(", ")", ";", ",", ":")
    .words(Scanners.IDENTIFIER)
    .caseInsensitiveKeywords(keywords)
    .build()

val tokenizer = or(Terminals.IntegerLiteral.TOKENIZER, terminals.tokenizer())
val tokenDelimiter = Scanners.WHITESPACES.skipMany()

I like to add a helper function for matching tokens in the parser stage. And since we have runs of tokens in the input I'm going to make an extra one which breaks a string into tokens and matches them in sequence. This allows me to write a parser like tokens("these words with any whitespace or line breaks") in the parser, and it'll do just what that says.

fun token(s: String): Parser<Token> = terminals.token(s)
fun tokens(s: String) = sequence(s.split(" ").map(::token))

Parser

The parser is slightly different from before. We're no longer consuming characters but tokens produced by the lexer. e.g. the word damage is a single token now, not six separate characters to be matched in sequence.

Terminals.IntegerLiteral.TOKENIZER is one kind of token. Its corresponding parser is:

val integer = Terminals.IntegerLiteral.PARSER.map(String::toInt)

Let's start in the middle of the parser, at army units. The text says things like "17 units each with", and I'm going to define the rest after that as the unit description. So it's just the sequence of things in the descripton. The major complication is the weaknessess and immunities group in parenthesis, so I factored that out.

    val unit: Parser<ArmyUnit> = sequence(
        integer,
        tokens("hit points").next(weaknessesAndImmunitiesOrEmpty),
        tokens("with an attack that does").next(attack),
        tokens("at initiative").next(integer),
        { hitPoints, wi, attack, initiative ->
            ArmyUnit(hitPoints, attack, initiative, wi.weaknesses.toSet(), wi.immunities.toSet())
        }
    )

Looking at the input text, the weaknesses and immunities can be in either order, or one can be missing, or the whole group might be ommitted. Good luck dealing with that with your hand-rolled parsers, but it's easy stuff for combinators. There are a few ways you could do it - the "weak to" and "immune to" tokens could qualify the following lists, then these would be sorted into their appropriate places when building the overall structure. I chose to keep the data structure simple and handle the various cases at the parser level, since there are only a few:

data class WeaknessesAndImmunities(val weaknesses: Collection<AttackType>, val immunities: Collection<AttackType>)

val commaList = Terminals.Identifier.PARSER.sepBy1(token(","))
val weaknesses = tokens("weak to").next(commaList)
val immunities = tokens("immune to").next(commaList)

val weaknessesAndImmunities: Parser<WeaknessesAndImmunities> = or(
    sequence(weaknesses, token(";").next(immunities), { w, i -> WeaknessesAndImmunities(w, i) }),
    sequence(immunities, token(";").next(weaknesses), { i, w -> WeaknessesAndImmunities(w, i) }),
    weaknesses.map { w -> WeaknessesAndImmunities(w, setOf()) },
    immunities.map { i -> WeaknessesAndImmunities(setOf(), i) }
).between(token("("), token(")"))

There's a lot going on here. Terminals.Identifier is one of our token types - its a word not predefined by the grammar, such as a variable name in a programming language. A commaList is one or more of these words separated by comma tokens. Remember the whitespace is dealt with in the lexer.

Weaknesses and immunities are just the identifying prefixes followed by comma lists.

The overall structure has four options:

1. Weaknesses followed by a semicolon then immunites
2. Immunities followed by a semicolon then weaknesses
3. Just weaknesses
4. Just immunities

In each case we build the data structure out of the parts available, using an empty set for anything missing. And finally at the very end the parser is augmented with between(token("("), token(")")) which matches (and skips) the parenthesis surrounding the group.

What if the whole section is omitted however?

val weaknessesAndImmunitiesOrEmpty = weaknessesAndImmunities.optional().map { wi ->
    wi ?: WeaknessesAndImmunities(setOf(), setOf())
}

.optional() turns a parser into one which matches its grammar, or nothing at all. If nothing is matched we get a null result, which is easily replaced with an empty data structure.

Building up the rest of the data structure is relatively easy, just more combinations of parsers all the way up to the full grammar:

val attack: Parser<Attack> = sequence(
    integer,
    Terminals.Identifier.PARSER.followedBy(token("damage")),
    ::Attack
)

val group: Parser<ArmyGroup> = sequence(
    integer,
    tokens("units each with").next(unit), 
    ::ArmyGroup
)

fun battleSide(name: String): Parser<List<ArmyGroup>> =
    tokens(name)
    .next(token(":"))
    .next(group.many1())

val battle: Parser<Battle> = sequence(
    battleSide("immune system"),
    battleSide("infection"),
    { a, b -> Battle(a.toSet(), b.toSet()) }
)

Parsing the example input gives me:

Battle(
  immuneSystem=[
    ArmyGroup(count=17, unit=ArmyUnit(hitPoints=5390, attack=Attack(damage=4507, type=fire), initiative=2, weaknesses=[radiation, bludgeoning], immunities=[])),
    ArmyGroup(count=989, unit=ArmyUnit(hitPoints=1274, attack=Attack(damage=25, type=slashing), initiative=3, weaknesses=[bludgeoning, slashing], immunities=[fire]))
  ],
  infection=[
    ArmyGroup(count=801, unit=ArmyUnit(hitPoints=4706, attack=Attack(damage=116, type=bludgeoning), initiative=1, weaknesses=[radiation], immunities=[])),
    ArmyGroup(count=4485, unit=ArmyUnit(hitPoints=2961, attack=Attack(damage=12, type=slashing), initiative=4, weaknesses=[fire, cold], immunities=[radiation]))
  ]
)

That was fun. I'll be back later for the battle simulation!

[Neil Gall]

Part 2

Find the minimum boost that lets the reindeer win? Sounds like a job for a binary search to me. Let's write a binary search that finds the minimum in a range that satisfies a predicate:

fun binarySearch(range: IntRange, predicate: (Int) -> Boolean): Int {
    var currentRange = range
    do {
        val midPoint = currentRange.start + (currentRange.endInclusive - currentRange.start) / 2
        currentRange = if (predicate(midPoint))
            currentRange.start..midPoint
        else
            midPoint+1..currentRange.endInclusive
    } while (currentRange.endInclusive != currentRange.start)
    return currentRange.start
}

We'll need some boosting helpers:

fun Attack.boostAttackPower(boost: Int) = copy(damage = damage + boost)
fun ArmyUnit.boostAttackPower(boost: Int) = copy(attack = attack.boostAttackPower(boost))
fun ArmyGroup.boostAttackPower(boost: Int) = copy(unit = unit.boostAttackPower(boost))

fun boostImmuneSystem(groups: Set<ArmyGroup>, boost: Int): Set<ArmyGroup> =
    groups.map { group -> 
        if (group.type == ArmyGroupType.INFECTION)
            group
        else
            group.boostAttackPower(boost)
    }.toSet()

A predicate to test a candidate, for use with the search:

fun immuneSystemWins(groups: Set<ArmyGroup>): Boolean =
    battle(groups).last().all { g -> g.type == ArmyGroupType.IMMUNE_SYSTEM }

And the answer becomes a matter of finding the minimum boost and running part 1 again with that boost:

fun part2(groups: Set<ArmyGroup>): Long {
    val minimumBoost = binarySearch(1..1000000) { boost ->
        immuneSystemWins(boostImmuneSystem(groups, boost))
    }
    return part1(boostImmuneSystem(groups, minimumBoost))
}

And yet again, I have a solution that works for the example and not for the real data. Probably the most frustrating aspect of Advent of Code.

[Mustafa Haddara]

One thing that burned me was the example data is missing a LOT of edge cases the real data will have. For example, the real data:

• has opposing groups where one is immune to the other's attacks
• can actually result in deadlocks if the last two remained groups are immune to each other, or if their damage/num units combination isn't enough to kill one opposing unit.

[Neil Gall]

Yes I find that annoying. But I guess it's like the real world too, and the answer is almost always in the detail of the text description, even if it takes several reads to jump out at you.

[Neil Gall]

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:

1. Sort the groups in attack order
2. For each attacking group select the maximum opposing group in defending order
3. 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)
    }
}

[Mustafa Haddara]

Yeah, a parser generator was definitely the right way to do it. I was stubborn and stuck to the naive way of doing it, which only worked because I noticed the only variable part was the special weaknesses/immunities bit. So I yanked that out:

specials = r"\(.*\)"
m = match(specials, line)

if m == nothing
    specials_chunk = ""
    simplified = line
else
    specials_chunk = m.match[2:end-1]  # remove ()
    simplified = line[1:m.offset-1] * line[m.offset+1+length(m.match):end]
end

tokens = split(simplified, " ")

and then processed the simple tokens the simple way:

units = parse(Int, tokens[1])  # this is the easy one
health = parse(Int, tokens[5])
damage = parse(Int, tokens[13])
attack_type = tokens[14]
initiative = parse(Int, tokens[end])

and then processed the special tokens separately:

if specials_chunk != ""
    chunks = split(specials_chunk, "; ")
    for c in chunks
        bits = split(c, " ")
        for i in 3:length(bits)
            if endswith(bits[i], ',')
                item = bits[i][1:end-1]
            else
                item = bits[i]
            end
            if bits[1] == "weak"
                push!(weakness, item)
            else
                push!(immunities, item)
            end
        end
    end
end

by the end I kinda ran out of good variable names was just using bits as a name, heh.

And then at the end, I could just return a new Group object...the first arg is the team, and the second arg is the number, more on that below

return Group("",0, units, health, damage, attack_type, initiative, weakness, immunities)

Assigning teams was done in a parent method that knew about the entire input:

function parse_input(input)
    groups::Array{Group} = []
    team = "Immune System"
    number = 1
    for line in input
        if line == ""
            continue
        end
        if line == "Immune System:"
            continue
        end
        if line == "Infection:"
            team = "Infection"
            number = 1
            continue
        end
        g = parse_group(line)
        g.number = number
        g.team = team
        push!(groups, g)
        number += 1
    end
    return groups
end

I also assigned a group number so I could get similar output to the sample output.

[Neil Gall]

I got it in the end. I missed the sentence "If it cannot deal any defending groups damage, it does not choose a target". A simple extra clause in the target selection:

if (defendingGroup == null) ...

became

if (defendingGroup == null || defendingGroup.damageFrom(attackingGroup.unit.attack) == 0) ...