First puzzle
Day 21 puzzle was just to warm up; here we are going to fight with magic. The combat is very similar in the sense that the player goes first, and they the player and the boss takes turns in to attack each other. In this case, the players attacks are with magic casting spells, and the boss continues to attack as in the previous day.
The player starts with 500 mana, and each spell cost a certain amount of it. If the player doesn’t have enough mana to cast a spell, it loses. Here are the list of spells:
- Magic Missile => Costs: 53 mana. Instant damage: 4.
- Drain => Costs: 73 mana. Instant damage: 2. Instant heal: 2 hit points.
- Shield => Costs: 113 mana. Effect last 6 turns. When active, it increases armor to 7 (the puzzle description said “by 7” instead of “to 7,” I prefer the later.)
- Poison => Costs: 173 mana. Effect last 6 turns. When active, it causes 3 damage per turn.
- Recharge => Costs 229 mana. Effect last 5 turns. When active, it gives 101 new mana per turn.
The effect rules:
- The effects start in the next turn they are cast. For example, after Poison, the boss will get 3 damage point on his turn not in the turn the spell was cast.
- You cannot cast a spell causing an effect that is active.
It is critical to understand the fight examples on the puzzle description. They don’t show all the possible scenarios, but it gives us a good idea of the situations. I won’t re-write them here because they are very long.
The solution of the puzzle is to find the least amount of mana we need to win the fight taking into account that the “recharged” mana is not negative mana. The total mana spent is the sum of all the mana spent on casting spells. The player has 50 hit points and 500 mana to start. The boss hit points, and the damage score is the puzzle’s input.
I tried the same idea of calculating all the possible games as it was done on Day 21 puzzle. It didn’t work because there are too many possible scenarios. Again, after a few days and a few hours per day trying to find a solution, I gave up and find help in Google. This is the second time translate a solution to Scala from Python, and the original Python (code)[https://github.com/ChrisPenner/Advent-Of-Code-Polyglot/tree/master/python/22] is fast and easy to understand.
The input parsing here is just the representation of the spells as a case class:
| case class Spell(mana: Int, damage : Int = 0, heal: Int = 0, armor: Int = 0, turns: Int = 0, rechargeMana: Int = 0) | |
| val spells = Map( | |
| "magic_missile" -> Spell(mana = 53, damage = 4), | |
| "drain" -> Spell(mana = 73, damage = 2, heal = 2), | |
| "shield" -> Spell(mana = 113, armor = 7, turns = 6), | |
| "poison" -> Spell(mana = 173, damage = 3, turns = 6), | |
| "recharge" -> Spell(mana = 229, turns = 5, rechargeMana = 101) | |
| ) |
In the end, I think the Python version is easier to understand. On my Scala version, I tried as much as possible to use immutable data structure and to pass the behavior as functions, but I think it didn’t add simplicity:
| case class Game( | |
| var winner: String = null, | |
| player: Player = Player(), | |
| boss: Boss = Boss(), | |
| var poison: Int = 0, | |
| var shield: Int = 0, | |
| var recharge: Int = 0 | |
| ) | |
| case class Boss(var hitPoints: Int, damage: Int) | |
| object Boss { | |
| def apply() : Boss = Boss(58, 9) | |
| implicit def BossToString(b : Boss ) : String = "boss" | |
| } | |
| case class Player(var hitPoints: Int, var mana: Int, var damage : Int = 0, var armor: Int = 0, var manaSpent: Int = 0) | |
| object Player { | |
| def apply() : Player = Player(50, 500) | |
| implicit def PlayerToString(p : Player ) : String = "player" | |
| } | |
| def calculateMinMana( gameGenerator: Game => List[Game]) : Int = { | |
| val stack : scala.collection.mutable.Stack[Game] = new scala.collection.mutable.Stack() | |
| stack.push(Game()) | |
| var min_mana_cost = Int.MaxValue | |
| var counter = 0 | |
| while ( stack.nonEmpty ) { | |
| val game = stack.pop() | |
| counter += 1 | |
| if ( game.player.manaSpent < min_mana_cost ) { | |
| if ( game.winner != null ) { | |
| if ( game.winner.toString == "player" ) { | |
| min_mana_cost = List(min_mana_cost, game.player.manaSpent).min | |
| } | |
| } else { | |
| gameGenerator(game).foreach( stack.push ) | |
| } | |
| } | |
| } | |
| min_mana_cost | |
| } | |
| def generateGameStates(playersAttack: (Game, String) => Unit, bossAttack: Game => Unit )(gamestate: Game): List[Game] = | |
| spells.map( s => { | |
| val ( spell, _ ) = s | |
| val game = gamestate.copy( player = gamestate.player.copy(), boss = gamestate.boss.copy() ) | |
| playersAttack(game, spell) | |
| if ( game.winner == null ) { | |
| bossAttack(game) | |
| } | |
| game | |
| }) | |
| .filter( g => g.winner == null || | |
| ( g.winner != null && g.winner.toString != "boss" ) | |
| ) | |
| .toList | |
| val myGameGenerator = generateGameStates(playerPlays, bossPlays)(_) | |
| def playerPlays(game: Game, spell: String): Unit = { | |
| if ( !isGameOver(game) ) { | |
| applySpells(game) | |
| if ( !isGameOver(game) ) { | |
| if ( game.player.mana < spells("magic_missile").mana ) { | |
| game.winner = game.boss | |
| } else { | |
| spell match { | |
| case "magic_missile" if game.player.mana >= spells(spell).mana => { | |
| game.player.mana -= spells(spell).mana | |
| game.player.manaSpent += spells(spell).mana | |
| game.boss.hitPoints -= spells(spell).damage | |
| } | |
| case "drain" if game.player.mana >= spells(spell).mana => { | |
| game.player.mana -= spells(spell).mana | |
| game.player.manaSpent += spells(spell).mana | |
| game.player.hitPoints += spells(spell).heal | |
| game.boss.hitPoints -= spells(spell).damage | |
| } | |
| case "shield" if game.shield == 0 && game.player.mana >= spells(spell).mana => { | |
| game.player.mana -= spells(spell).mana | |
| game.player.manaSpent += spells(spell).mana | |
| game.shield = spells(spell).turns | |
| } | |
| case "poison" if game.poison == 0 && game.player.mana >= spells(spell).mana => { | |
| game.player.mana -= spells(spell).mana | |
| game.player.manaSpent += spells(spell).mana | |
| game.poison = spells(spell).turns | |
| } | |
| case "recharge" if game.recharge == 0 && game.player.mana >= spells(spell).mana => { | |
| game.player.mana -= spells(spell).mana | |
| game.player.manaSpent += spells(spell).mana | |
| game.recharge = spells(spell).turns | |
| } | |
| case _ => game.winner = game.boss | |
| } | |
| isGameOver(game) | |
| } | |
| } | |
| } | |
| } | |
| def bossPlays(game: Game): Unit = { | |
| applySpells(game) | |
| if ( !isGameOver(game) ) { | |
| game.player.hitPoints -= List(game.boss.damage - game.player.armor, 1).max | |
| isGameOver(game) | |
| } | |
| } | |
| def isGameOver(game: Game): Boolean = { | |
| if ( game.player.hitPoints <= 0 ) { | |
| game.winner = game.boss | |
| true | |
| } else { | |
| if ( game.boss.hitPoints <= 0 ) { | |
| game.winner = game.player | |
| true | |
| } else { | |
| false | |
| } | |
| } | |
| } | |
| def applySpells(game: Game) : Game = { | |
| if ( game.shield > 0) { | |
| game.shield -= 1 | |
| game.player.armor = spells("shield").armor | |
| } else { | |
| game.player.armor = 0 | |
| } | |
| if ( game.poison > 0 ) { | |
| game.poison -= 1 | |
| game.boss.hitPoints -= spells("poison").damage | |
| } | |
| if ( game.recharge > 0 ) { | |
| game.recharge -= 1 | |
| game.player.mana += spells("recharge").rechargeMana | |
| } | |
| game | |
| } | |
| val minManaPuzzle1 = calculateMinMana(myGameGenerator) |
Second puzzle
The second part of the puzzle add another rule: At the start of each player turn, the player lose one hit point before any effect apply. In the case of our modeling, we just need to change the behavior the player and create a new game generator function:
| def playerPlays2(game: Game, spell: String) : Unit = { | |
| game.player.hitPoints -= 1 | |
| if ( !isGameOver(game) ) { | |
| playerPlays(game, spell) | |
| } | |
| } | |
| val myGameGenerator2 = generateGameStates(playerPlays2, bossPlays)(_) | |
| val minManaPuzzle2 = calculateMinMana(myGameGenerator2) |
You can find this code along with my input and puzzle answers at here.