Edd Mann Developer

Advent of Code 2015 - Day 22 - Wizard Simulator 20XX

On the twenty-second day of Advent of Code 2015, we are asked to help ‘Little Henry Case’ beat the boss in another video game he is stuck on.

Part 1

Like the previous day, the game is turn-based. However, this time we are able to spend mana in exchange for spells we can cast per round. Certain spells have the ability to cause effects that can last between rounds. Due to this, we are unable to formulate the battle into a single calculation, so instead, we must simulate a given battle in its entirety. For part one, we are asked to work out the minimum amount of mana we can spend and still win the battle.

Based on the rules laid out within the problem specification, we begin by modelling how spells will be represented.

type Spell = {
  name: string;
  cost: number;
  damage: number;
  armor: number;
  heal: number;
  mana: number;
  turns: number;
};

const spells: Spell[] = [
  { name: 'Magic Missile', cost: 53, damage: 4, armor: 0, heal: 0, mana: 0, turns: 1 },
  { name: 'Drain', cost: 73, damage: 2, armor: 0, heal: 2, mana: 0, turns: 1 },
  { name: 'Shield', cost: 113, damage: 0, armor: 7, heal: 0, mana: 0, turns: 6 },
  { name: 'Poison', cost: 173, damage: 3, armor: 0, heal: 0, mana: 0, turns: 6 },
  { name: 'Recharge', cost: 229, damage: 0, armor: 0, heal: 0, mana: 101, turns: 5 },
];

This approach opts to normalise all the possible spell behaviours, creating no-op actions by way of zero values. From here, we model how we wish to store the state of a battle throughout gameplay.

type BattleState = {
  playerHp: number;
  playerMana: number;
  playerArmor: number;
  bossHp: number;
  bossDamage: number;
  manaSpent: number;
  activeEffects: Spell[];
};

There are a couple of rules around which spells are available for a player to cast at a given point in the battle. These include whether they have enough mana to purchase the spell and if the spell is an effect that is either not active or on its last turn. We will next translate these rules into a function that we can supply the current BattleState to and return the possible Spell listing.

const hasBattleEnded = (state: BattleState) =>
  state.bossHp <= 0 || state.playerHp <= 0;

const getAvailableSpells = (state: BattleState): Spell[] => {
  if (hasBattleEnded(state)) return [];

  return spells.filter(spell => {
    const active = state.activeEffects.find(effect => spell.name === effect.name);
    return spell.cost <= state.playerMana && (!active || active.turns === 1);
  });
};

This leads us to being able to start codifying the steps that a given battle round takes. We will start by building out all the desired steps as isolated immutable state transitions. First, we will handle how we apply effects before each participant’s turn.

type BattleTransition = (state: BattleState) => BattleState;

const enactEffects: BattleTransition = state => {
  if (hasBattleEnded(state)) return state;

  return {
    ...state,
    playerMana: state.playerMana + sumProp(state.activeEffects, 'mana'),
    playerArmor: sumProp(state.activeEffects, 'armor'),
    bossHp: state.bossHp - sumProp(state.activeEffects, 'damage'),
    activeEffects: state.activeEffects.reduce(
      (effects, effect) => effect.turns > 1 ? [...effects, { ...effect, turns: effect.turns - 1 }] : effects,
      []
    ),
  };
};

We have used the same sumProp function found in the previous day’s solution to help tally a collection’s property values. Next, we will handle how a player’s turn updates the battle state. We supply a given Spell we wish the player to cast for this round and return a BattleTransition similar to enacting effects.

const playerTurn = (spell: Spell): BattleTransition => state => {
  if (hasBattleEnded(state)) return state;

  const isSpellEffect = spell.turns > 1;

  return {
    ...state,
    playerHp: state.playerHp + (isSpellEffect ? 0 : spell.heal),
    playerMana: state.playerMana - spell.cost,
    bossHp: state.bossHp - (isSpellEffect ? 0 : spell.damage),
    manaSpent: state.manaSpent + spell.cost,
    activeEffects: isSpellEffect ? [...state.activeEffects, spell] : state.activeEffects,
  };
};

Following on from the player’s turn, we can now model how a boss’s turn updates the battle state.

const bossTurn: BattleTransition = state => {
  if (hasBattleEnded(state)) return state;

  return {
    ...state,
    playerHp: state.playerHp - Math.max(state.bossDamage - state.playerArmor, 1),
  };
};

With the core steps in place, modelled uniformly as BattleTransition types, we can begin to think about how we wish to stitch these together. When reading the problem definition, I thought it would be an ideal fit to employ composable state transitions. To wire these together, I’ve opted to use a small pipe helper function, which works in the opposite manner to a conventional compose. Instead of being called right-to-left, the pipe function composes the provided functions left-to-right, which reads more naturally.

const pipe = <R>(fn1: (a: R) => R, ...fns: Array<(a: R) => R>) =>
  fns.reduce((prevFn, nextFn) => value => nextFn(prevFn(value)), fn1);

Using this pipe function, we can build up the steps required to complete a round.

type BattleRound = (spell: Spell) => BattleTransition;

const roundOfBattle: BattleRound = spell =>
  pipe(enactEffects, playerTurn(spell), enactEffects, bossTurn);

With the round simulation modelled, we can work on a solution to determine the minimum mana required to win the battle. To do this, we will use a recursive function that takes in a BattleConfiguration and BattleRound function like so.

type BattleConfiguration = Pick<BattleState, 'playerHp' | 'playerMana' | 'bossHp' | 'bossDamage'>;

const isPlayerWinner = (state: BattleState) =>
  hasBattleEnded(state) && state.playerHp > 0;

const minManaSpent = (
  configuration: BattleConfiguration,
  round: BattleRound
): number => {
  let minMana = Infinity;

  const recur = (state: BattleState): void => {
    if (state.manaSpent > minMana) return;

    if (getAvailableSpells(state).length === 0) {
      if (isPlayerWinner(state)) minMana = state.manaSpent;
      return;
    }

    for (const spell of getAvailableSpells(state)) {
      recur(round(spell)(state));
    }
  };

  recur({
    ...configuration,
    playerArmor: 0,
    manaSpent: 0,
    activeEffects: [],
  });

  return minMana;
};

The BattleConfiguration is a subset type of the BattleState, allowing us to supply the battle properties that define the participants’ characteristics. The BattleRound function allows us to supply the roundOfBattle function we created earlier to simulate each given round’s state transition. To locate the minimum amount of mana required, we store the current minimum mana for a winning battle and prune out any branches that exceed this amount until no enactable branches remain. This allows us to limit the scope of the problem greatly, as upon the first winning game, we have a baseline to prune out any game that exceeds that mana spent.

With this in place, we can parse the boss’s characteristics from the supplied input and execute the minManaSpent function to find the desired answer 🌟.

const part1 = (input: string): number => {
  const [bossHp, bossDamage] = input.match(/(\d+)/gm).map(toInt);

  return minManaSpent(
    { playerHp: 50, playerMana: 500, bossHp, bossDamage },
    roundOfBattle
  );
};

Part 2

For part two, we are required to expand upon the game we created in part one. We are now to create a Hard Mode, in which, at the start of each round, the player’s health is reduced by one HP. Based on this addition, we need to determine the revised minimum mana spent required to still win the battle.

We will first create the additional BattleTransition step, defining how Hard Mode modifies the battle state.

const applyHardMode: BattleTransition = state => ({
  ...state,
  playerHp: state.playerHp - 1,
});

From this, we can create a new round of battle function, which pipes the BattleState to the applyHardMode function before continuing with the original game.

const hardRoundOfBattle: BattleRound = spell =>
  pipe(applyHardMode, roundOfBattle(spell));

We can then use the same setup as we did for part one, instead supplying the new hardRoundOfBattle function. In doing so, we get the desired answer to the question 🌟.

const part2 = (input: string): number => {
  const [bossHp, bossDamage] = input.match(/(\d+)/gm).map(toInt);

  return minManaSpent(
    { playerHp: 50, playerMana: 500, bossHp, bossDamage },
    hardRoundOfBattle
  );
};

I found today’s core problem did not take too long to devise (the minimum pruning technique). However, simulating the game took the majority of the time. As mentioned when reading the problem definition, I felt there could be a means to provide an elegant, composable solution for representing the steps required to perform a round of battle. I’m happy with how the BattleTransition type has been employed, lending itself well to the pipe operation. Reading both the roundOfBattle and hardRoundOfBattle functions clearly expresses their intent and the stages of a round.