DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’» is a community of 968,873 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Create account Log in
Cover image for RPG Simulator 20XX
Robert Mion
Robert Mion

Posted on

RPG Simulator 20XX

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)

In defense of the modern web

I expect I'll annoy everyone with this post: the anti-JavaScript crusaders, justly aghast at how much of the stuff we slather onto modern websites; the people arguing the web is a broken platform for interactive applications anyway and we should start over;

React users; the old guard with their artisanal JS and hand authored HTML; and Tom MacWright, someone I've admired from afar since I first became aware of his work on Mapbox many years ago. But I guess that's the price of having opinions.