DEV Community

Cover image for RPG Simulator 20XX
Robert Mion
Robert Mion

Posted on

RPG Simulator 20XX

#adventofcode #algorithms #programming #javascript

Advent of Code 2015 Day 21

Why not attempt Day 22 first?

  • Any time a puzzle references another - earlier - puzzle, I try to solve the referenced puzzle(s) first...assuming there's important knowledge or skills to be gained from them that will help me solve the later one(s)

Part 1

  1. A finance-related boss battle? Exciting!
  2. A shortest-path combination puzzle
  3. How to do battle
  4. Studying the example scenario for the battle's math
  5. Writing an algorithm I could replay manually
  6. Playing out a few more battles

A finance-related boss battle? Exciting!

  • Defeat the boss!
  • But don't spend any more money than you have to to win!
  • Even though the instructions say you have plenty!

A shortest-path and permutation puzzle

  • I must find the combination of weapons-armor-rings that costs the least and still defeats the boss

The combinations:

  • 1 weapon (5), 0 armor, 0 rings = 5 options
  • 1 weapon (5), 0 armor, 1 ring (6) = 30 options
  • 1 weapon (5), 0 armor, 2 rings (6 * 5 = 30) = 150 options
  • 1 weapon (5), 1 armor (5), 0 rings = 25 options
  • 1 weapon (5), 1 armor (5), 1 ring (6) = 150 options
  • 1 weapon (5), 1 armor (5), 2 rings (30) = 750 options

Total possible combinations:
1110

Yikes!

How to do battle

  • The player goes first
  • Each attack damages the defender by at least 1 hit point
  • As soon as any player has 0 hit points, the battle ends
  • Each attacker's damage remains constant

Damage is calculated using this equation:

Attacker's damage score - Defender's armor score
Enter fullscreen mode Exit fullscreen mode
  • The boss's hit points and scores are provided in the input and do not change
  • The player's hit points are 100 and scores are decided based on the item(s) purchased
  • It seems the answer to this puzzle is identifying the cost of the items that cause the battle to a real nail-biter!

Studying the example scenario for the battle's math

Stats:

Player Hit Points: 8 Damage: 5 Armor: 5 Boss Hit Points: 12 Damage: 7 Armor: 2
Enter fullscreen mode Exit fullscreen mode

Calculating scores:

Player: 5 - 2 = 3 Boss: 7 - 5 = 2
Enter fullscreen mode Exit fullscreen mode

Rounds of battle:

 Boss Player 0 12 8 1 9 6 2 6 4 3 3 2 4 0 0
Enter fullscreen mode Exit fullscreen mode

Interesting:

  • In the example, both player's hit points were evenly divisible by their respective damage score 
12 % 3 == 0 8 % 2 == 0 12 / 3 == 4 8 / 2 == 4 If equal, Player wins Else, whoever's is smaller loses
Enter fullscreen mode Exit fullscreen mode

By my logic:

  • Check whether the reminder after dividing the starting hit points by the damage received is 0
  • If it is, calculate the quotient of the hit points and damage received
  • Else, calculate 1 + the quotient of the difference of hit points and the remainder, then the damage received

So, using the example:

12 % 3 == 0 ? 12 / 3 : 1 + ((12 - (12 % 3)) / 3) // 4 8 % 2 == 0 ? 8 / 2 : 1 + ((8 - (8 % 2)) / 2) // 4
Enter fullscreen mode Exit fullscreen mode

Then:

  • If boss's amount is less than or equal to player's, player wins
  • Else, boss wins

Writing an algorithm I could replay manually

Extracting the boss's stats:

let [BossHP, BossDmg, BossDef] = input.matchAll(/\d+/g)].map(el => +el[0])
Enter fullscreen mode Exit fullscreen mode

Calculating the number of rounds survived:

function calculateRounds(hp, dmg) { return hp % dmg == 0 ? hp / dmg : 1 + ((hp - (hp % dmg)) / dmg) }
Enter fullscreen mode Exit fullscreen mode

Simulating the battle:

function battle(stats) { let BossRounds = calculateRounds( stats.BossHP, stats.P1Dmg - stats.BossDef ) let P1Rounds = calculateRounds( stats.P1HP, stats.BossDmg - stats.P1Def ) return BossRounds <= P1Rounds ? ["P1 wins!", P1Rounds, BossRounds] : ["Boss wins!", BossRounds, P1Rounds] }
Enter fullscreen mode Exit fullscreen mode

The parameter referenced above, stats, has this structure:

{ BossHP: BossHP, BossDmg: BossDmg, BossDef: BossDef, P1HP: 100, P1Dmg: 8, P1Def: 4 }
Enter fullscreen mode Exit fullscreen mode

To replay, I just changed P1Dmg and P1Def:

P1Dmg: 4 P1Def: 0 Boss wins! P1Dmg: 5 P1Def: 0 Boss wins! P1Dmg: 6 P1Def: 0 Boss wins! P1Dmg: 7 P1Def: 0 Boss wins! P1Dmg: 8 P1Def: 0 Boss wins!
Enter fullscreen mode Exit fullscreen mode

Bummer. Looks like the player must carry more than just a weapon into battle to have a chance at winning!

Playing out a few more battles

It's not enough to do 8 damage and have no armor.

What about 8 damage and all the armor: 8?

  • As expected, player wins

Let's work backwards now until player loses:

P1Dmg: 8 P1Def: 8 P1 wins! P1Dmg: 8 P1Def: 7 P1 wins! P1Dmg: 8 P1Def: 6 P1 wins! P1Dmg: 8 P1Def: 5 P1 wins! P1Dmg: 8 P1Def: 4 P1 wins! P1Dmg: 8 P1Def: 3 Boss wins!
Enter fullscreen mode Exit fullscreen mode

The lowest cost thus far:

P1Dmg: 8 P1Def: 4 Weapon: Longsword (40 gold) Armor: Bandedmail (75 gold) Ring: Damage +1 (25 gold) Total cost: 140 gold
Enter fullscreen mode Exit fullscreen mode

What if player's damage is 9?

P1Dmg: 9 P1Def: 4 P1 wins! P1Dmg: 9 P1Def: 3 P1 wins! P1Dmg: 9 P1Def: 2 P1 wins! Barely! P1Dmg: 9 P1Def: 1 Boss wins!
Enter fullscreen mode Exit fullscreen mode

The lowest cost thus far:

P1Dmg: 9 P1Def: 2 Weapon: Longsword (40 gold) Armor: Chainmail (31 gold) Ring: Damage +2 (50 gold) Total cost: 121 gold
Enter fullscreen mode Exit fullscreen mode

It's worth a try at the correct answer...

...Yes! Correct answer!

Part 2

I guess I'll keep playing!

This time, I must identify:

the most amount of gold I can spend and still lose the fight

  • Seems smart to wear both the most expensive rings
  • And I have to buy a weapon

How about:

P1Dmg: 7 P1Def: 4 Boss wins! Weapon: Dagger (8 gold) Armor: Bandedmail (75 gold) Ring: Damage +3 (100 gold) Total cost: 183 gold
Enter fullscreen mode Exit fullscreen mode

Oh, and with two rings:

P1Dmg: 8 P1Def: 3 Boss wins! Weapon: Shortsword (10 gold) Ring: Defense +3 (80 gold) Ring: Damage +3 (100 gold) Total cost: 190 gold
Enter fullscreen mode Exit fullscreen mode

Is that the correct answer?

  • Nope. Too low.

Oh, another (7, 4) but with four items:

P1Dmg: 7 P1Def: 4 Boss wins! Weapon: Dagger (8 gold) Armor: Leather (13 gold) Ring: Defense +3 (80 gold) Ring: Damage +3 (100 gold) Total cost: 201 gold
Enter fullscreen mode Exit fullscreen mode

Is that the correct answer?

  • Yes, it is!

I did it!!

  • I solved both parts!
  • By first building a round-calculating algorithm that performed simple arithmetic!
  • Then, by building a battle-simulating algorithm!
  • And playing it with different damage and defense values!
  • And identifying the proper items that would tally to the winning - or losing - values!

If I hadn't stumbled on Part 1's correct answer so quickly, I was ready to write an algorithm using several nested for loops that simulated all 1110 of the options.

Thankfully, I didn't have to build such an algorithm!

Though, it may have been a fun - albeit frustrating and head-scratching - experience.

Top comments (0)