Exam time again. I’ve tried to produce exam questions for my current algorithms design class themed after Blizzard’s collectible card game Hearthstone. For a variety of reasons I decided to abandon the idea for the exam, but the ideas are cute enough for a blog post. Here are the first three. The target audience are algorithms design students struggling with Chapters 1–8 of Kleinberg and Tardos’s Algorithms Design book (so: graph traversal, greedy, divide and conquer, dynamic programming, network flow, NP-hardness). Enjoy!

Hearthstone Basics

Each card in the game Hearthstone depicts a minion. Each minion has 3 values: Attack, Health and Cost, given as integers a, h, and c. Here’s a minion with Attack 3, Health 2, and Cost 4:

For the purpose of these exercises, these values are unbounded, positive integers. During the game, both players have a number of minions in play. In a turn of Heartstone, the player assigns his minions to fight enemy minions. Each minion gets to target a single enemy minion, initiating a fight between the two minions. When a minion with Attack A fights a minion with Health H, the other minion’s Health is reduced to max{0,H-A}. Note that both minions fight, and each deals damage to the other, regardless of who initiated the fight. Also note that an enemy minion can be involved in many fights each turn, when it is repeatedly targeted. When a minion’s Health is reduced to 0, it is removed from play.

For each of the problems below, state which algorithmic design technique should be used, or if the problem is NP-hard. Also give the best asymptotic worst-case running time.

Cleanup

You and ZombieMage02 both have the same number of minions in play. It is your turn. Can you take them all the enemy minions in one sweep?

Input:
The enemy minions (a₁,h₁),…,(a_n,h_n) ∈ N² and your minions (a₁′,h₁′),…,(a_n′,h_n′) ∈ N²

Output: “Yes,” if your minions can take out all enemy minions this turn. “No,” otherwise.

Tanks

TwoOrcsOneCup has two minions in play. Both completely overpowered and powerful enough to wipe out your hero when it becomes TwoOrcsOneCup’s turn again. You have n minions in play. Can you take out both minions this turn?

Input: The enemy minions (a₁,h₁),(a₂,h₂) ∈ N² and your minions (a₁′,h₁′),…,(a_n′,h_n′) ∈ N²

Output: “Yes” if your minions can take out both enemy minions this turn.

Charge!

Showdown time. Your hero has almost no Health left and OprahWindfury’s mage keeps pummeling you with fireballs. This has been going on for hours—time to end this! Luckily your hand is full of high-powered cards with Charge, which can attack immediately.
Get out as many of these guys as you can afford!

Input Your available mana K. The minions with Charge on your hand, (a₁,h₁,c₁),…,(a_n,h_n,c_n) ∈ N².

Output: The total number of Attack points you can play this round.

---

Cards generated using achievementgen.com