Advent of Code F# – Day 22

The source code for this post (both Part 1 and Part 2) is available here and you can click here to see my solutions for the other Advent of Code challenges.

 

Day 22‘s challenge essentially a more difficult version of Day 21, so we can roughly follow the same approach we took the last time round.

To get started, let’s define what the states for the player and the boss look like:

then we have the state of the entire game, comprising of the current states of the player and boss, as well as any effects from spells that are still active – we need to know the name of the spell, how to apply the effect, and how many turns it has left.

There are three spells that will leave lasting effects : shield, poison and recharge. These effects can affect player state (shield and recharge) or boss state (poison), so I think the easiest way to represent an effect is as a function that takes in player and boss state and return their updated states.

Finally, we’re also defining a Result type to represent the two ways a game can end – player wins or boss wins.

But what about spells?

Well, spells can update player state (drain heals you, plus all spells costs mana), boss state (missile and drain damages the boss), as well as start effects (shield, poison and recharge) lasting several rounds. So, they can update all aspects of a game state, so basically a spell transforms a game state:

Next, in a nested module, let’s define our spells. But first, let’s add a couple of helper functions:

Magic Missile costs 53 mana. It instantly does 4 damage.

Drain costs 73 mana. It instantly does 2 damage and heals you for 2hit points.

Shield costs 113 mana. It starts an effect that lasts for 6 turns. While it is active, your armor is increased by 7.

Poison costs 173 mana. It starts an effect that lasts for 6 turns. At the start of each turn while it is active, it deals the boss 3 damage.

Recharge costs 229 mana. It starts an effect that lasts for 5 turns. At the start of each turn while it is active, it gives you 101 new mana.

and here are all the spells we can use during battle:

You start with 50 hit points and 500 mana points. The boss’s actual stats are in your puzzle input.

Based on the description of the challenge and my input file, this is how the player and boss state looks like at the start of the battle:

So far, we’ve added functions to damage the boss, let’s also add one to damage the player (taking into account the player’s armor value if there’s an active shield).

…if armor (from a spell, in this case) would reduce damage below 1, it becomes 1 instead – that is, the boss’ attacks always deal at least 1 damage.

Before each round, we also need to apply all the active effects. One tricky thing here is that because the shield effect is adding 7 to the player’s armor each time it’s applied, so we have to reset the player’s armor value first.

(aside : the shield effect should be setting the armor value to 7 rather than incrementing, which will remove the need to reset the armor value here. It happened here because I misread the description and thought the same spell can be cast twice and accumulate multiple shield effects…)

Regarding the above code, there’s an important paragraph to remember from the description of the challenge:

Effects apply at the start of both the player’s turns and the boss’ turns. Effects are created with a timer (the number of turns they last); at the start of each turn, after they apply any effect they have, their timer is decreased by one. If this decreases the timer to zero, the effect ends. You cannot cast a spell that would start an effect which is already active. However, effects can be started on the same turn they end.

Based on this paragraph, it means it’s ok for us to remove effects whose count becomes 0 after applying it (hence allowing the spell to be cast again), because effects can be started on the same turn they end.

Next, let’s also add a partial active pattern to check if it’s game over:

The simulation logic is also more complicated than Day 21, but it follows the high level structure in the snippet below

• player and boss turns are represented by mutually recursive functions that tracks the current game state as well as the total mana used;
• we’ll start the simulation with an initial game state using the provided player and boss state;
• player attacks first

Now that you’ve seen the high-level structure of the runSim function, let’s drill down into what’s going on when it’s the player’s turn.

• First, we apply any active effects, if an effect’s timer becomes 0 afterwards then it’s removed from the returned game state’s Effects list;
• If either player or boss dies after that, then we can end the game straight away;
• If the play can’t afford to cast any spells (the cheapest spell costs 53 mana) then he loses;
• Otherwise, from all the spells we must make a choice between the spells that:
  • we can afford, and
  • it won’t start an effect that is still active
• Using a brute force approach (no pruning), we will attempt each choice and collect the results
• If the boss dies after our spell then we win! yay!
• Otherwise, it’s now the boss’s turn..

When it’s the boss’s turn, again we have to first apply any active effects in the game. If either player or boss dies after that, then we can end the game straight away.

If not, we will hit the player, and if the player dies then the boss wins. Otherwise, we recurse back into the player’s turn.

Finally, to find the minimum amount of mana to still win the fight, we just run our brute force simulation, and find the smallest accumulated mana from the choices that lead to player winning.

 

Part 2

Just a tiny tweak required for Part 2 – to reduce the player’s HP by 1 at the start of a player round, as per the description.