Advent of Code F# – Day 22

The source code for this post (both Part 1 and Part 2) is avail­able here and you can click here to see my solu­tions for the oth­er Advent of Code chal­lenges.

 

s chal­lenge essen­tial­ly a more dif­fi­cult ver­sion of Day 21, so we can rough­ly fol­low the same approach we took the last time round.

To get start­ed, let’s define what the states for the play­er and the boss look like:

day22_01

then we have the state of the entire game, com­pris­ing of the cur­rent states of the play­er 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 last­ing effects : shield, poi­son and rechargeThese effects can affect play­er state (shield and recharge) or boss state (poi­son), so I think the eas­i­est way to rep­re­sent an effect is as a func­tion that takes in play­er and boss state and return their updat­ed states.

Final­ly, we’re also defin­ing a Result type to rep­re­sent the two ways a game can end — play­er wins or boss wins.

day22_02

But what about spells?

Well, spells can update play­er state (drain heals you, plus all spells costs mana), boss state (mis­sile and drain dam­ages the boss), as well as start effects (shield, poi­son and recharge) last­ing sev­er­al rounds. So, they can update all aspects of a game state, so basi­cal­ly a spell trans­forms a game state:

day22_03

Next, in a nest­ed mod­ule, let’s define our spells. But first, let’s add a cou­ple of helper func­tions:

day22_04

Mag­ic Mis­sile costs 53 mana. It instant­ly does 4 dam­age.

day22_05

Drain costs 73 mana. It instant­ly does 2 dam­age 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

Poi­son 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 dam­age.

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 dur­ing bat­tle:

day22_10

You start with 50 hit points and 500 mana points. The boss’s actu­al stats are in your puz­zle input.

Based on the descrip­tion of the chal­lenge and my input file, this is how the play­er and boss state looks like at the start of the bat­tle:

day22_11

So far, we’ve added func­tions to dam­age the boss, let’s also add one to dam­age the play­er (tak­ing into account the player’s armor val­ue if there’s an active shield).

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

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 val­ue first.

(aside : the shield effect should be set­ting the armor val­ue to 7 rather than incre­ment­ing, which will remove the need to reset the armor val­ue here. It hap­pened here because I mis­read the descrip­tion and thought the same spell can be cast twice and accu­mu­late mul­ti­ple shield effects…)

day22_13

Regard­ing the above code, there’s an impor­tant para­graph to remem­ber from the descrip­tion of the chal­lenge:

Effects apply at the start of both the player’s turns and the boss’ turns. Effects are cre­at­ed with a timer (the num­ber 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 decreas­es the timer to zero, the effect ends. You can­not cast a spell that would start an effect which is already active. How­ev­er, effects can be start­ed on the same turn they end.

Based on this para­graph, it means it’s ok for us to remove effects whose count becomes 0 after apply­ing it (hence allow­ing the spell to be cast again), because effects can be start­ed on the same turn they end.

Next, let’s also add a par­tial active pat­tern to check if it’s game over:

day22_14

The sim­u­la­tion log­ic is also more com­pli­cat­ed than Day 21, but it fol­lows the high lev­el struc­ture in the snip­pet below

  • play­er and boss turns are rep­re­sent­ed by mutu­al­ly recur­sive func­tions that tracks the cur­rent game state as well as the total mana used;
  • we’ll start the sim­u­la­tion with an ini­tial game state using the pro­vid­ed play­er and boss state;
  • play­er attacks first

day22_15

Now that you’ve seen the high-lev­el struc­ture of the run­Sim func­tion, 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 after­wards then it’s removed from the returned game state’s Effects list;
  • If either play­er or boss dies after that, then we can end the game straight away;
  • If the play can’t afford to cast any spells (the cheap­est spell costs 53 mana) then he los­es;
  • Oth­er­wise, 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 prun­ing), we will attempt each choice and col­lect the results
  • If the boss dies after our spell then we win! yay!
  • Oth­er­wise, 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 play­er or boss dies after that, then we can end the game straight away.

If not, we will hit the play­er, and if the play­er dies then the boss wins. Oth­er­wise, we recurse back into the player’s turn.

day22_17

Final­ly, to find the min­i­mum amount of mana to still win the fight, we just run our brute force sim­u­la­tion, and find the small­est accu­mu­lat­ed mana from the choic­es that lead to play­er win­ning.

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 play­er round, as per the descrip­tion.

day22_19