Immune System Simulator 20XX

Advent of Code 2018 Day 24

Task: Solve for X where...

Part 1

X = the number of units remaining in the winning army

Example input

Immune System:
17 units each with 5390 hit points (weak to radiation, bludgeoning) with an attack that does 4507 fire damage at initiative 2
989 units each with 1274 hit points (immune to fire; weak to bludgeoning, slashing) with an attack that does 25 slashing damage at initiative 3

Infection:
801 units each with 4706 hit points (weak to radiation) with an attack that does 116 bludgeoning damage at initiative 1
4485 units each with 2961 hit points (immune to radiation; weak to fire, cold) with an attack that does 12 slashing damage at initiative 4

It represents:

• A reindeer's immune system and an infection, depicted as armies comprised of groups
• Each group consists of identical units
• Units have several attributes

Part 1: Act 1

1. Trying to classify all of this exposition
2. Confirming understanding by way of the example
3. Embarking on a seemingly impossible task

Trying to classify all of this exposition

Setting the stage of combat

• There are two battling armies: Immune System and Infection
• Each army is made up of several groups
• Each group is made up of identical units
• Each unit has several attributes that determine how it will attack and whether it will survive

The hierarchy as I see it:

Army
  Group of units
    Unit
      Identical Base Attributes:
        Hit points: amount of damage a unit can take before it is destroyed
        Attack damage: the amount of damage each unit deals
        Attack type: type of damage each unit outputs
        Initiative: higher initiative units attack first and win ties
        Weaknesses: type of damage each unit is susceptible to
        Immunities: type of damage each unit is resistant to
    Group's Computed Attribute:
      Effective Power:
        Unit count * Attack damage

Some initial rules worth noting:

The armies repeatedly fight until only one army has units remaining

• I sense a while loop that runs until a variable tracking the number of groups for each army reports a 0 for one of the groups

Groups never have zero or negative units; instead, the group is removed from combat

• This further enforces my comment above about tracking the number of groups...and their current DNA after each round of combat

Understanding the two phases of combat

Target selection

Each group attempts to choose one target

• So, in a single round of combat, one group will attack one other?

At the end of the target selection phase, each group has selected zero or one groups to attack, and each group is being attacked by zero or one groups

• Hmm. So, the possibilities are:

Each Attacking group from Army 1:
Don't attack
Attack one group from Army 2

Each Defending group from Army 2:
Remain unharmed
Get attacked by one group from Army 1

In decreasing order of effective power, groups choose their targets...

• Now I see where Effective Power comes into play: it is a sort of ranking that helps pair opposing groups

...in a tie, the group with the higher initiative chooses first

• Groups 'line up' in descending order be Effective Power. If two groups have the same Effective Power, the one with a higher Initiative is added first to the line.
• This is the first in a series of conditions that this puzzle quickly amasses

The attacking group chooses to target the group in the enemy army to which it would deal the most damage (after accounting for weaknesses and immunities, but not accounting for whether the defending group has enough units to actually receive all of that damage).

• Next in line: review each group in the other army, calculate the total damage dealt with no regard for unit count...

If an attacking group is considering two defending groups to which it would deal equal damage, it chooses to target the defending group with the largest effective power

• ...Could you deal the most damage to two groups? Pick the one with the largest Effective Power...

If there is still a tie, it chooses the defending group with the highest initiative

• ...Did those two groups have the same Effective Power? Pick the one with the highest Initiative.

If it cannot deal any defending groups damage, it does not choose a target.

• This could happen if an attacking group's Attack Type is the Attack Type that each of the remaining defending groups' units have as Immunities

Defending groups can only be chosen as a target by one attacking group.

• Whenever a group is paired with a defending group in the current round of combat, both groups must be flagged as no longer available for pairing
• It is therefore possible and highly likely that one or more groups will not participate in combat each round due to Attack Type and Immunity mismatches

Attacking

Each group deals damage to the target it selected, if any.

• This makes sense: targeting is done and groups are paired or omitted from combat, then the hit points of the group are decremented by the amount of damage calculated during the targeting phase to determine the match

Groups attack in decreasing order of initiative, regardless of whether they are part of the infection or the immune system.

• Interesting! It doesn't go Army 1 then Army 2 - or vice versa - rather groups attack based on their Initiative number, highest first.

If a group contains no units, it cannot attack.

• Since order isn't one army then the next, it's now possible that a group's hit point could become depleted before that group moved to the front of the attacking queue.
• There will definitely be a ton of state management throughout this algorithm

By default, an attacking group would deal damage equal to its effective power to the defending group

• This first condition makes sense

If the defending group is immune to the attacking group's attack type, the defending group instead takes no damage

• This second condition makes sense

If the defending group is weak to the attacking group's attack type, the defending group instead takes double damage

• This third condition makes sense

All three conditions of damage dealt by attacking group:

Is Attack Type of attacking group in neither Weakness or Immunity lists of defending group?
  Continue with Effective Power calculated amount

Is Attack Type of attacking group in Immunity list of defending group?
  Do not change hit points of defending group

Is Attack Type of attacking group in Weakness list of defending group?
  Continue with double the Effective Power calculated amount

How defending groups' hit points are ultimately affected by an attacking group's damage output:

The defending group only loses whole units from damage

• I sense some rounding

Damage is always dealt in such a way that it kills the most units possible, and any remaining damage to a unit that does not immediately kill it is ignored

• Indeed. Round down.

Example offered for clarification:

75 damage sent to defending group

Defending group contains:
10 units each with 10 hit points

Multiples of 10 up to 75:
70

70 damage ultimately sent to defending group
7 units each with 10 hit points removed
3 units each with 10 hits points remain

Lastly, confirmation of the need for a while loop that depends on at least one army to contain at least one group with hit points of at least 1:

After the fight is over, if both armies still contain units, a new fight begins; combat only ends once one army has lost all of its units.

Confirming understanding by way of the example

Parsing the example into a dictionary of armies and their groups:

Immune System Army
Group 1:
17 units
5390 HP
Weak to: Radiation, Bludgeoning
Damage Amount: 4507
Damage Type: Fire
Initiative: 2
Effective Power: 76619

Group 2:
989 units
1274 HP
Immune to: Fire
Weak to: Bludgeoning, Slashing
Damage Amount: 25
Damage Type: Slashing
Initiative: 3
Effective Power: 24725

Infection Army
Group 1:
801 units
4706 HP
Weak to: Radiation
Damage Amount: 116
Damage Type: Bludgeoning
Initiative: 1
Effective Power: 92916

Group 2:
4485 units
2961 HP
Immune to: Radiation
Weak to: Fire, Cold
Damage Amount: 12
Damage Type: Slashing
Initiative: 4
Effective Power: 53820

The instructions then - thankfully - describe:

• The possible pairings in each step
• The actual pairings in each step
• The damage dealt
• The number of units killed

Embarking on a seemingly impossible task

• I don't expect to generate the correct answer for my puzzle input
• I may not even finish building an algorithm (and its many required sub-routines) that can generate the correct answer for the example input
• But I feel compelled to try, especially since I feel confident enough in my understanding of how this simulator plays out in each round

I'll give myself three days.

If I haven't solved Part 1 by the end of the third day, I must move on.

• I wonder...if I can solve Part 1 using the example input.
• What if...I write an algorithm bit by bit in attempts to try?
• Let's try!

Part 1: Act 2

1. Skippable, but gotta try: a complicated regular expression
2. Building an object for each group
3. Ugh: I overlooked one key detail
4. Inching my way toward a working algorithm, I hope
5. Confirming when effective power is calculated
6. It works on one round of the example. Does it work on two? Three? All?
7. Woah, yes! Now, does it work on my puzzle input?

Skippable, but gotta try: a complicated regular expression

• I expect to manually craft the dictionary of items representing armies and the groups
• But I have to try extracting the information from each string using a regular expression

The instructions offer this example I will use:

18 units each with 729 hit points (weak to fire; immune to cold, slashing) with an attack that does 8 radiation damage at initiative 10

Each line follows this pattern:

• \d+ One or more digits
• units each with
• \d+ One or more digits
• hit points
• The tough part: the optional parenthetical weaknesses and/or immunities
• with an attack that does
• \d+ One or more digits
• single-word attack type
• damage at initiative
• \d+ One or more digits

As for that tough part in the middle, here are some further examples:

(weak to radiation, bludgeoning)
(immune to fire; weak to bludgeoning, slashing)
(weak to radiation)
(immune to radiation; weak to fire, cold)
(immune to bludgeoning, fire)

Variations are:

• Either weak or immune
• to
• single-word
• Optional additional single-word, each separated by comma
• ; if the other category follows
• Repeat bullets 1-4

Maybe, just maybe I can make this work.

Time to try using regexr.com!

Well, this works...but it feels overly specific and icky:

/(?<units>\d+) units each with (?<hp>\d+) hit points (?<extras>\((?<type1>immune|weak) to (?<item1>\w+),?\s?(?<item2>\w+)?;?\s?(?<type2>immune|weak)?\s?t?o?\s?(?<item3>\w+)?,?\s?(?<item4>\w+)?\))?\s?with an attack that does (?<damage>\d+) (?<type>\w+) damage at initiative (?<initiative>\d+)/g

It combines two regular expressions:

/(?<units>\d+) units each with (?<hp>\d+) hit points (?<extras>\(\))?\s?with an attack that does (?<damage>\d+) (?<type>\w+) damage at initiative (?<initiative>\d+)/g

This captures everything except what's inside the optional parentheses

And this one:

/\((?<type1>immune|weak) to (?<item1>\w+),?\s?(?<item2>\w+)?;?\s?(?<type2>immune|weak)?\s?t?o?\s?(?<item3>\w+)?,?\s?(?<item4>\w+)?\)/g

This captures up to two of each weakness and immunity inside the parentheses

I only check for two of each because the groups in my input only have up to two of each, if any at all.

Building an object for each group

I chose to represent each group as an object, with key-value pairs for each attribute.

Most attributes are captured directly from the regular expression above.

But some need to be computed using various tactics, including:

• id - each group needs a unique one so I can store them in the same list
• power - short for Effective Power, derived from the product of the number of units and damage
• army - this is the army each group belongs to: either Immune System or Infections (0 or 1 in my case) - since I will store all groups in the same list

The toughest part was building the extras object:

• My regular expression captured everything necessary
• But it also captured undefined for any missing values
• I couldn't rely on immune to be first and weak to be second or vice versa
• And in my input, one group didn't have either, so I wanted that value to be null

Eventually, each object looked something like this:

{
  id: 0,
  units: 3321,
  hp: 6178,
  damage: 18,
  type: 'bludgeoning',
  initiative: 20,
  extras: { immune: ['fire'] },
  power: 59778,
  army: 0
}

That doesn't include the pre-calculated damage amounts that a single group does to each of the opposing groups.

After some list creation and filtering, and conditional logic, I generated that object that stores the amount of damage any group would deal to all opposing army groups should that group be targeted.

The final object for each group looks akin to this:

  {
    id: 18,
    units: 1336,
    hp: 56700,
    damage: 69,
    type: 'radiation',
    initiative: 12,
    extras: { weak: ['slashing'] },
    power: 92184,
    army: 1,
    attacks: {
      '0': 92184,
      '1': 92184,
      '2': 92184,
      '3': 92184,
      '4': 92184,
      '5': 0,
      '6': 92184,
      '7': 92184,
      '8': 92184,
      '9': 92184
    }
  }

So much setup!

Am I ready to start building the algorithm that computes each round of combat?

Ugh: I overlooked one key detail

I started to generate the list of opposing groups, ordered by their effective power, using my puzzle input.

I noticed that all of them had different values.

That made it seem odd for the instructions to call out this detail:

In decreasing order of effective power, groups choose their targets; in a tie, the group with the higher initiative chooses first.

• Why call out the tie condition if my input would never encounter it?
• Silly me. The effective power is a derivation of unit count. The unit count could change each round for different groups. Hence, why there could eventually be a tie.

This just adds to the variability of attribute values during and between rounds, and the amount of computing I'll have to do each round.

This also makes me want to revert my object to no longer initially include the attacks object, since I'll have to re-generate that each round.

Inching my way toward a working algorithm, I hope

Here's what I have working by the end of Day 1:

• Parsed the input using a regular expression to generate an array of objects representing each group
• Determined the order in which each group would select an opposing group to attack - during the targeting phase
• Determined the defending group, if any, each attacking group selects - also during the targeting phase
• Determined the order in which each attacking group would attack - during the attacking phase

When I run all this once on the example input, I see the expected group pairings and order in which they attack.

When I run all this once on my puzzle input, I don't get any errors, and I see similar group pairings in an order other than that which they were in during the targeting phase.

All this is to say...I'm feeling better positioned to solve this puzzle than I thought I would by end of Day 1!

A big variable for me is Effective Power:

• Since it is derived from unit count, how often should it be calculated?
• Just prior to the targeting phase, since it is used to determine the ordering of groups, many of whom were just attacked and lost units?
• Or also just prior to a group attacking a defending group, since the attacking group may have been attacked earlier during the attacking phase - which would have reduced its unit count, thereby altering its effective power and thus its damage?
• Doing the latter feels wrong, since its effective power as calculated during the targeting phase was used to determine which group to attack. If effective power could change during the attacking phase then the defending group may no longer be correct

I think I'll proceed with the former: effective power is calculated once per round, during the targeting phase.

Confirming when effective power is calculated

In the first round of combat in the example, this result is offered:

Immune System group 2 attacks defending group 1, killing 4 units

This single statement helped me understand how often effective power must be calculated:

1. For each group at the beginning of the targeting phase, since groups may have lost units during the last round of combat
2. For each attacking group throughout the attacking phase, since each group is susceptible to a loss of units from an earlier attack

• I wasn't updating effective power at first
• My algorithm had Immune System group 2 attacking defending group 1, but killing 5 units
• Why 5? Because I wasn't re-calculating effective power between Immune System group 2's earlier loss in units and its turn at attacking
• So, I was using effective power of 24725 reflecting 989 units instead of 22625 reflecting 905 units remaining after losing 81 units from the attack that just happened from Infection group 2

So, there was my answer:

• Each group's effective power must be re-calculated twice during each round of combat: once before targeting and again before attacking

It works on one round of the example. Does it work on two? Three? All?

• It didn't work after two rounds

I realized a few bugs:

• I wasn't updating each group's effective power at the beginning of the round
• I wasn't correctly filtering the list of armies to exclude groups with units zero or fewer

Trying again:

• It now worked after two rounds
• And after three, four, five, six, seven
• And after the eighth round, it correctly showed only 2/4 groups having positive units of the expected amounts

I successfully generated the correct answer for the example input!

Woah, yes! Now, does it work on my puzzle input?

• First try: no
• After some troubleshooting, I generated a value over 20,000
• Sadly, that answer was too high
• I logged each group's unit after each round
• I confirmed that once a group's unit count reaches zero or lower, it doesn't change, which means my logic works as expected

I don't know how else to troubleshoot my code to generate a different, correct answer.

I'm bummed, but not disappointed in myself.

Celebrating accomplishments

• I went from feeling completely confused and intimidated by this puzzle's instructions...to feeling confident enough to attempt writing an algorithmic solution
• I wrote an algorithm that generated the correct answer using the example input!

Bummers:

• I didn't solve Part 1
• I didn't make any GIFs
• I didn't make a simulator: a big bummer for a puzzle with Simulator in its name!

This puzzle was a beast

• I'm glad I stuck with it enough to write an algorithm that runs on the example and my puzzle input
• I'm glad I generated the correct answer for the example input
• I'm not surprised I didn't generate the correct answer for my puzzle input

I'm ready to move on!