Task 22

Thorn Thaler - <

2025-07-25

1 Setup

1.1 Libraries

library(httr)
library(xml2)
library(magrittr)
library(dplyr)
library(purrr)
library(stringr)
library(tidyr)

1.2 Retrieve Data from AoC

session_cookie <- set_cookies(session = keyring::key_get("AoC-GitHub-Cookie"))
base_url <- paste0("https://adventofcode.com/", params$year, "/day/", params$task_nr)
puzzle <- GET(base_url,
              session_cookie) %>% 
  content(encoding = "UTF-8") %>% 
  xml_find_all("///article") %>% 
  lapply(as.character)

parse_puzzle_data <- function(text_block = readClipboard()) {
  if (length(text_block) == 1L) {
    text_block <- text_block %>% 
      str_split("\n") %>% 
      extract2(1L) %>% 
      keep(nzchar)
  }
  stats <- str_extract_all(text_block, "\\d+") %>% 
    flatten() %>% 
    as.integer() %>% 
    set_names(c("boss_HP", "dmg")) %>% 
    as.list()
  spells <- tibble(
    name = c("Magic Missile",
             "Drain",
             "Shield",
             "Poison",
             "Recharge"),
    damage = c(4L, 2L, 0L, 3L, 0L),
    heal = c(0L, 2L, 0L, 0L, 0L),
    armor = c(0L, 0L, 7L, 0L, 0L),
    mana = c(0L, 0L, 0L, 0L, 101L),
    duration = c(0L, 0L, 6L, 6L, 5L),
    costs = c(53L, 73L, 113L, 173L, 229L)
  )
  list(stats = c(stats, mana = 500L, hp = 50L), spells = spells)
}

puzzle_data <- local({
  GET(paste0(base_url, "/input"),
      session_cookie) %>% 
    content(encoding = "UTF-8") %>% 
    parse_puzzle_data()
})

2 Puzzle Day 22

2.1 Part 1

2.1.1 Description

— Day 22: Wizard Simulator 20XX —

Little Henry Case decides that defeating bosses with swords and stuff is boring. Now he’s playing the game with a wizard. Of course, he gets stuck on another boss and needs your help again.

In this version, combat still proceeds with the player and the boss taking alternating turns. The player still goes first. Now, however, you don’t get any equipment; instead, you must choose one of your spells to cast. The first character at or below 0 hit points loses.

Since you’re a wizard, you don’t get to wear armor, and you can’t attack normally. However, since you do magic damage, your opponent’s armor is ignored, and so the boss effectively has zero armor as well. As before, 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.

On each of your turns, you must select one of your spells to cast. If you cannot afford to cast any spell, you lose. Spells cost mana; you start with 500 mana, but have no maximum limit. You must have enough mana to cast a spell, and its cost is immediately deducted when you cast it. Your spells are Magic Missile, Drain, Shield, Poison, and Recharge.

  • Magic Missile costs 53 mana. It instantly does 4 damage.
  • Drain costs 73 mana. It instantly does 2 damage and heals you for 2 hit 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.

Effects all work the same way. 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.

For example, suppose the player has 10 hit points and 250 mana, and that the boss has 13 hit points and 8 damage: 

-- Player turn --
- Player has 10 hit points, 0 armor, 250 mana
- Boss has 13 hit points
Player casts Poison.

-- Boss turn --
- Player has 10 hit points, 0 armor, 77 mana
- Boss has 13 hit points
Poison deals 3 damage; its timer is now 5.
Boss attacks for 8 damage.

-- Player turn --
- Player has 2 hit points, 0 armor, 77 mana
- Boss has 10 hit points
Poison deals 3 damage; its timer is now 4.
Player casts Magic Missile, dealing 4 damage.

-- Boss turn --
- Player has 2 hit points, 0 armor, 24 mana
- Boss has 3 hit points
Poison deals 3 damage. This kills the boss, and the player wins.

Now, suppose the same initial conditions, except that the boss has 14 hit points instead: 

-- Player turn --
- Player has 10 hit points, 0 armor, 250 mana
- Boss has 14 hit points
Player casts Recharge.

-- Boss turn --
- Player has 10 hit points, 0 armor, 21 mana
- Boss has 14 hit points
Recharge provides 101 mana; its timer is now 4.
Boss attacks for 8 damage!

-- Player turn --
- Player has 2 hit points, 0 armor, 122 mana
- Boss has 14 hit points
Recharge provides 101 mana; its timer is now 3.
Player casts Shield, increasing armor by 7.

-- Boss turn --
- Player has 2 hit points, 7 armor, 110 mana
- Boss has 14 hit points
Shield's timer is now 5.
Recharge provides 101 mana; its timer is now 2.
Boss attacks for 8 - 7 = 1 damage!

-- Player turn --
- Player has 1 hit point, 7 armor, 211 mana
- Boss has 14 hit points
Shield's timer is now 4.
Recharge provides 101 mana; its timer is now 1.
Player casts Drain, dealing 2 damage, and healing 2 hit points.

-- Boss turn --
- Player has 3 hit points, 7 armor, 239 mana
- Boss has 12 hit points
Shield's timer is now 3.
Recharge provides 101 mana; its timer is now 0.
Recharge wears off.
Boss attacks for 8 - 7 = 1 damage!

-- Player turn --
- Player has 2 hit points, 7 armor, 340 mana
- Boss has 12 hit points
Shield's timer is now 2.
Player casts Poison.

-- Boss turn --
- Player has 2 hit points, 7 armor, 167 mana
- Boss has 12 hit points
Shield's timer is now 1.
Poison deals 3 damage; its timer is now 5.
Boss attacks for 8 - 7 = 1 damage!

-- Player turn --
- Player has 1 hit point, 7 armor, 167 mana
- Boss has 9 hit points
Shield's timer is now 0.
Shield wears off, decreasing armor by 7.
Poison deals 3 damage; its timer is now 4.
Player casts Magic Missile, dealing 4 damage.

-- Boss turn --
- Player has 1 hit point, 0 armor, 114 mana
- Boss has 2 hit points
Poison deals 3 damage. This kills the boss, and the player wins.

You start with 50 hit points and 500 mana points. The boss’s actual stats are in your puzzle input. What is the least amount of mana you can spend and still win the fight? (Do not include mana recharge effects as “spending” negative mana.)

2.1.2 Solution

This was a difficult puzzle, where we overread a lot of details in hte first iterations (e.g. that buffs are applied not only before the player’s turn but also before the boss’ turn). We started out with a recursive R implementation, but as there are quite some combinations to check, R’s copy on modify semantic became soon a deal-breaker. Thus, we switched to C++.

We learned an aweful lot about smart pointers (unique_ptr with its move semantics and shared_ptr) just to realize that using a unique pointer, for something which effectively should be shared, is not the smartest move.

We needed a lot of iterations before the code worked, which was due to the self inflicted complications with moving unique pointers and even more importantly due to not following the instructions of the game.

Eventually We came up with the following solution (after switching from a recursive function to an iterative method). The idea is that we save the current state, cast an affordable spell (which is not yet casted) and add the new state to the stack. If we find a solution (i.e. the boss is dead), we update the mana count. During the process, if we hit a state which is more expensive than the best solution so far, we pruned to save some iterations.

#ifndef STANDALONE
#include <Rcpp.h>
using namespace Rcpp;
#endif

#include <algorithm>
#include <iostream>
#include <limits>
#include <memory>
#include <stack>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

enum Player { BOSS, PLAYER };

struct Stats {
    int my_hp;
    int boss_hp;
    int mana;
    int armor;
    int round;
    int mana_spent;
};

class Spell {
  public:
    Spell(const std::string, const std::unordered_map<std::string, int>&);
    void cast(Stats&);
    void apply(Stats&);
    int get_cost() const;
    std::string get_name() const;
    int get_duration() const;
    bool is_buff() const;

    friend std::ostream& operator<<(std::ostream&, const Spell&);

  private:
    std::string name;
    int damage;
    int heal;
    int armor;
    int mana;
    int costs;
    int duration;
};

struct ActiveBuffs {
    std::shared_ptr<Spell> spell;
    int usages;
};

class GameController {
  public:
    GameController(Stats,
                   int,
                   const std::unordered_map<std::string, std::unordered_map<std::string, int>>&);
    void apply_buffs();
    void attack();
    void cast(const std::string&);
    void sting();
    bool is_dead(Player) const;
    bool can_cast(const std::string&) const;
    int get_mana_spent() const;
    std::vector<std::string> get_spells() const;

  private:
    std::vector<ActiveBuffs> buffs;
    std::vector<std::string> spells;
    std::unordered_map<std::string, std::shared_ptr<Spell>> spell_library;
    Stats stats;
    int boss_damage;

    bool is_active(const std::string&) const;
};

class Game {
  public:
    Game();
    int start_game(int,
                   int,
                   int,
                   int,
                   const std::unordered_map<std::string, std::unordered_map<std::string, int>>&,
                   bool);

  private:
    int simulate(GameController, bool);
};

Spell::Spell(const std::string spell_name, const std::unordered_map<std::string, int>& stats)
    : name(spell_name)
    , damage(stats.at("damage"))
    , heal(stats.at("heal"))
    , armor(stats.at("armor"))
    , mana(stats.at("mana"))
    , costs(stats.at("costs"))
    , duration(stats.at("duration")) { }

void Spell::cast(Stats& stats) {
  stats.mana_spent += costs;
  stats.mana -= costs;
  stats.round++;
}

void Spell::apply(Stats& stats) {
  // 1. boss loses hp
  stats.boss_hp -= damage;
  // 2. 1 heal
  stats.my_hp += heal;
  // 3. armor is set up
  stats.armor = std::max(stats.armor, armor);
  // 4. I get mana
  stats.mana += mana;
}

int Spell::get_cost() const {
  return costs;
}

int Spell::get_duration() const {
  return duration;
}

bool Spell::is_buff() const {
  return duration > 0;
}

std::string Spell::get_name() const {
  return name;
}

std::ostream& operator<<(std::ostream& stream, const Spell& spell) {
  stream << spell.name << " [Damage: " << spell.damage << ", Heal: " << spell.heal;
  stream << ", Armor: " << spell.armor << ", Mana: " << spell.mana << ", Costs: ";
  stream << spell.costs << "]" << " @" << spell.duration;
  return stream;
}

GameController::GameController(
    Stats start_stats,
    int damage,
    const std::unordered_map<std::string, std::unordered_map<std::string, int>>& all_spells)
    : stats(start_stats)
    , boss_damage(damage) {
  for (const auto& [name, stats] : all_spells) {
    spell_library[name] = std::make_shared<Spell>(name, stats);
    spells.push_back(name);
  }
}

void GameController::apply_buffs() {
  stats.armor = 0;
  for (auto it = buffs.begin(); it != buffs.end();) {
    if (it->usages > 0) {
      it->spell->apply(stats);
      it->usages--;
      if (it->usages == 0) {
        it = buffs.erase(it);
      } else {
        ++it;
      }
    }
  }
}

void GameController::attack() {
  stats.my_hp -= std::max<int>(boss_damage - stats.armor, 1);
}

void GameController::cast(const std::string& spell_name) {
  auto spell = spell_library[spell_name];
  spell->cast(stats);
  if (spell->is_buff()) {
    buffs.push_back({spell, spell->get_duration()});
  } else {
    spell->apply(stats);
  }
}

void GameController::sting() {
  stats.my_hp--;
}

bool GameController::is_dead(Player who) const {
  if (who == BOSS) {
    return stats.boss_hp <= 0;
  } else {
    return stats.my_hp <= 0;
  }
}

bool GameController::can_cast(const std::string& spell_name) const {
  auto spell = spell_library.at(spell_name);
  return stats.mana >= spell->get_cost() && !is_active(spell_name);
}

bool GameController::is_active(const std::string& name) const {
  return std::any_of(buffs.begin(), buffs.end(), [&](const ActiveBuffs& b) {
    return b.spell->get_name() == name;
  });
}

int GameController::get_mana_spent() const {
  return stats.mana_spent;
}

std::vector<std::string> GameController::get_spells() const {
  return spells;
}

Game::Game() { }

int Game::start_game(
    int boss_damage,
    int boss_hp,
    int my_hp,
    int mana,
    const std::unordered_map<std::string, std::unordered_map<std::string, int>>& spell_library,
    bool hard_game = false) {
  Stats stats;
  stats.my_hp = my_hp;
  stats.boss_hp = boss_hp;
  stats.mana = mana;
  stats.armor = 0U;
  stats.round = 1U;
  stats.mana_spent = 0U;
  GameController controller(stats, boss_damage, spell_library);
  int result = simulate(controller, hard_game);
  return result;
}

int Game::simulate(GameController start_controller, bool hard_game) {
  struct SimulationState {
      GameController controller;
      size_t next_spell_index = 0;
  };
  std::vector<std::string> spells = start_controller.get_spells();
  std::stack<SimulationState> stack;
  stack.push({start_controller, 0});

  int best_mana = std::numeric_limits<int>::max();
  bool found_solution = false;

  while (!stack.empty()) {
    SimulationState& current = stack.top();

    if (current.next_spell_index >= spells.size()) {
      stack.pop();
      continue;
    }

    const std::string& spell = spells[current.next_spell_index++];

    GameController controller_copy = current.controller;
    if (hard_game) {
      controller_copy.sting();
    }
    controller_copy.apply_buffs();
    if (controller_copy.is_dead(BOSS)) {
      found_solution = true;
      best_mana = std::min(best_mana, controller_copy.get_mana_spent());
      continue;
    }
    if (!controller_copy.can_cast(spell)) {
      continue;
    }
    controller_copy.cast(spell);
    controller_copy.apply_buffs();
    if (controller_copy.is_dead(BOSS)) {
      found_solution = true;
      best_mana = std::min(best_mana, controller_copy.get_mana_spent());
      continue;
    }
    controller_copy.attack();
    if (controller_copy.is_dead(PLAYER)) {
      continue;
    }
    if (controller_copy.get_mana_spent() >= best_mana) {
      continue;
    }
    stack.push({controller_copy, 0});
  }
  return found_solution ? best_mana : -1;
}
#ifndef STANDALONE
// [[Rcpp::export]]
int get_lowest_mana(List stats, DataFrame spells, bool hard_game = false) {
  std::unordered_map<std::string, std::unordered_map<std::string, int>> spell_library;
  std::vector<std::string> names = spells["name"];
  std::vector<std::string> fields = {"damage", "heal", "armor", "mana", "duration", "costs"};
  for (int i = 0; i < spells.nrows(); ++i) {
    std::unordered_map<std::string, int> spell_stats;
    for (const std::string& field : fields) {
      spell_stats[field] = as<std::vector<int>>(spells[field])[i];
    }
    spell_library[names[i]] = std::move(spell_stats);
  }
  Game game;
  int result = game.start_game(
      stats["dmg"], stats["boss_HP"], stats["hp"], stats["mana"], spell_library, hard_game);
  return result;
}
#else
int main() {
  // Example usage
  Game game;
  int mana_spent = game.start_game(
      8,
      13,
      10,
      250,
      {{"Magic Missile",
        {{"damage", 4}, {"heal", 0}, {"armor", 0}, {"mana", 0}, {"costs", 53}, {"duration", 0}}},
       {"Drain",
        {{"damage", 2}, {"heal", 2}, {"armor", 0}, {"mana", 0}, {"costs", 73}, {"duration", 0}}},
       {"Shield",
        {{"damage", 0}, {"heal", 0}, {"armor", 7}, {"mana", 0}, {"costs", 113}, {"duration", 6}}},
       {"Poison",
        {{"damage", 3}, {"heal", 0}, {"armor", 0}, {"mana", 0}, {"costs", 173}, {"duration", 6}}},
       {"Recharge",
        {{"damage", 0},
         {"heal", 0},
         {"armor", 0},
         {"mana", 101},
         {"costs", 229},
         {"duration", 5}}}},
      false);
  std::cout << "Mana spent: " << mana_spent << std::endl;
  return 0;
}
#endif
get_lowest_mana(puzzle_data$stats, puzzle_data$spells)
## [1] 1269

2.2 Part 2

2.2.1 Description

— Part Two —

On the next run through the game, you increase the difficulty to hard.

At the start of each player turn (before any other effects apply), you lose 1 hit point. If this brings you to or below 0 hit points, you lose.

With the same starting stats for you and the boss, what is the least amount of mana you can spend and still win the fight?

2.2.2 Solution

While the first part of the solution took a considerable amount of time, the second one was very easy, as we simply had to add another game step. This time we understood the instructions properly and just added a flag to the algorithm to determine which version we want to simulate.

get_lowest_mana(puzzle_data$stats, puzzle_data$spells, TRUE)
## [1] 1309