RPG Simulator 20XX
Tags: adventofcode, algorithms, programming, javascript
Published: 2022-09-07 14:05:03

## [Advent of Code 2015 Day 21](https://adventofcode.com/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
```

- 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
```

Calculating scores:
```
Player:
5 - 2 = 3

Boss:
7 - 5 = 2
```

Rounds of battle:
```
   Boss  Player
0  12    8
1  9     6
2  6     4
3  3     2
4  0     0
```

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
```

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
```

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:
```js
let [BossHP, BossDmg, BossDef] = input.matchAll(/\d+/g)].map(el => +el[0])
```

Calculating the number of rounds survived:
```js
function calculateRounds(hp, dmg) {
  return hp % dmg == 0 
       ? hp / dmg 
       : 1 + ((hp - (hp % dmg)) / dmg)
}
```

Simulating the battle:
```js
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]
}
```

The parameter referenced above, `stats`, has this structure:
```js
{
  BossHP: BossHP,
  BossDmg: BossDmg,
  BossDef: BossDef,
  P1HP: 100,
  P1Dmg: 8,
  P1Def: 4
}
```

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!
```

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!
```

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
```

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!
```

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
```

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
```

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
```

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
```

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.