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:

day22_01

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

day22_02

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:

day22_03

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

day22_04

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

day22_05

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

day22_06

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

day22_07

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.

day22_08

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.

day22_09

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

day22_10

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:

day22_11

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.

day22_12

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

day22_13

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:

day22_14

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

day22_15

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

day22_16

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.

day22_17

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.

day22_18

 

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.

day22_19

5 Comments

  1. Pingback: F# Weekly #52, 2015 | Sergey Tihon's Blog

  2. Horia Toma   •  

    hi,

    were you curious to see how many possible solutions are generated when the HitPoints for the Boss are superior to 50 and how much time does it take to process them?

  3. Yan Cui   •  

    my input was 71 HP, and 10 damage, did you find something interesting about some specific input?

  4. Horia Toma   •  

    51/9 spins on forever.
    I had the same issue with my algorithm and the solution I found was to compare the current spending with a global minimum, thus avoiding to go farther on useless paths

  5. Yan Cui   •  

    ah, that’s a nice optimization, thanks for that!

Leave a Reply

Your email address will not be published.