AoC Day 24: Immune System Simulator 20XX

twitter logo github logo ・1 min read

Advent of Code (26 Part Series)

1) AoC Day 1: Chronal Calibration 2) AoC Day 2: Inventory Management System 3 ... 24 3) AoC Day 3: No Matter How You Slice It 4) AoC Day 4: Repose Record 5) AoC Day 5: Alchemical Reduction 6) AoC Day 6: Chronal Coordinates 7) AoC Day 7: The Sum of Its Parts 8) AoC Day 8: Memory Maneuver (Placeholder) 9) AoC Day 9: Marble Mania 10) AoC Day 10: The Stars Align 11) AoC Day 11: Chronal Charge 12) AoC Day 12: Subterranean Sustainability 13) AoC Day 13: Mine Cart Madness 14) AoC Day 14: Chocolate Charts 15) AoC Day 15: Beverage Bandits 16) AoC Day 16: Chronal Classification 17) AoC Day 17: Reservoir Research 18) AoC Day 18: Settlers of The North Pole 19) AoC Day 19: Go With the Flow 20) AoC Day 20: A Regular Map 21) AoC Day 21: Chronal Conversion 22) AoC Day 22: Mode Maze 23) AoC Day 23: Experimental Emergency Teleportation 24) AoC Day 24: Immune System Simulator 20XX 25) AoC Day 25: Four-Dimensional Adventure 26) Advent of Code Wrap-Up

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!

twitter logo DISCUSS (7)
markdown guide
 

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!

 

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.

 

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.

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.

 

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.

 

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) ...
 

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)
    }
}
Classic DEV Post from Dec 29 '18

What's your 🎉New Year Resolutions🎉 ?

I know you all must be thinking, "Ugh... Not this again. These things never wor...

Ryan Palo profile image
Ryan is a mechanical engineer in the East SF Bay Area with a focus on dynamic languages like Ruby & Python. Goal: learn a ton and become a physics, math, and programming teacher. Message me on DEV.TO

Sore eyes?

dev.to now has dark mode.

Go to the "misc" section of your settings and select night theme ❤️

(There is also a pink mode)