Magic: the Gathering is a trading card game where, among other things, players play cards representing creatures, which can then attack the other player, or defend against the other player's attacks by blocking.
In this code-golf challenge, your program will be in the place of a Magic player deciding how to block in combat.
Each creature has two relevant attributes: Power, and toughness. A creature's power is the amount of damage it can deal in a combat, and its toughness is the amount of damage necessary to destroy it. Power is always at least 0, and toughness is always at least 1.
During combat in Magic, the player whose turn it is declares some of their creatures to be attacking the opponent. Then, the other player, known as the defending player, may assign their creatures as blockers. A creature may block only one creature per combat, but multiple creatures may all block the same creature.
After blockers are declared, the attacking player decides, for each attacking creature that was blocked, how to distribute the damage (equal to its power) that that creature deals to the creatures blocking it.
Then, damage is dealt. Each creature deals damage equal to its power. Attacking creatures that were blocked deal damage as descibed above. Unblocked attacking creatures deal damage to the defending player. Blocking creatures deal damage to the creature they blocked. Creatures belonging to the defending player that did not block deal no damage. (Creatures are not required to block.)
Finally, any creature dealt damage equal to or greater than its toughness is destroyed, and removed from the battlefield. Any amount of damage less than a creature's toughness has no effect.
Here's an example of this process:
A creature with power P and toughness T is represented as
Attacking: 2/2, 3/3 Defending player's creatures: 1/4, 1/1, 0/1 Defending player declares blockers: 1/4 and 1/1 block 2/2, 0/1 does not block. Attacking player distributes damage: 2/2 deals 1 damage to 1/4 and 1 damage to 1/1 Damage is dealt: 2/2 takes 2 damage, destroyed. 3/3 takes 0 damage. 1/1 takes 1 damage, destroyed. 1/4 takes 1 damage. 0/1 takes 0 damage. Defending player is dealt 3 damage.
The defending player has 3 goals in combat: Destroy the opponent's creatures, preserve one's own creatures, and be dealt as little damage as possible. In addition, creatures with more power and toughness are more valuable.
To combine these into a single measure, we will say that the defending player's score from a combat is equal to the sum of the powers and toughnesses of their surviving creatures, minus the sum of the powers and toughnesses of their opponent's surviving creatures, minus one half of the amount of damage dealt to the defending player. The defending player wants to maximize this score, while the attacking player wants to minimize it.
In the combat shown above, the score was:
Defending player's surviving creatures: 1/4, 0/1 1 + 4 + 0 + 1 = 6 Attacking player's surviving creature: 3/3 3 + 3 = 6 Damage dealt to defending player: 3 6 - 6 - 3/2 = -1.5
If the defending player had not blocked at all in the combat described above, the score would have been
8 - 10 - (5/2) = -4.5
The optimal choice for the defending player would have been to block the
2/2 with the
1/1 and the
1/4, and to block the
3/3 with the
0/1. If they had done so, only
1/4 and the
3/3 would have survived, and no damage would have been dealt to the defending player, making the score
5 - 6 - (0/2) = -1
Your challenge is to write a program which will output the optimal blocking choice for the defending player. "Optimal" means the choice which maximizes the score, given that the opponent distributes damage in the way which minimizes the score, given how you blocked.
This is a maximin: The maximum score over the damage distributions which minimize score for each blocking combination.
Input: The input will consist of two lists of 2-tuples, where each 2-tuple is of the form (Power, Toughness). The first list will contain the powers and toughnesses of each attacking creature (you opponent's creatures). The second list will contain the powers and toughnesses of each of your creatures.
Tuples and lists may be represented in any convenient format, such as:
[[2, 2], [3, 3]] [[1, 4], [1, 1], [0, 1]]
Output: The output will consist of a series of 2-tuples, in the form (blocking creature, blocked creature) - that is, one of your creatures followed by one of their creatures. Creatures will be refered to by their index in the input lists. Indexes may be 0 or 1 indexed. Again, any convenient format. Any order is fine. For example, the optimal blocking scenario from above, given the above input, might be represented as:
[0, 0] # 1/4 blocks 2/2 [1, 0] # 1/1 blocks 2/2 [2, 1] # 0/1 blocks 3/3
Input: [[2, 2], [3, 3]] [[1, 4], [1, 1], [0, 1]] Output: [0, 0] [1, 0] [2, 1] Input: [[3, 3], [3, 3]] [[2, 3], [2, 2], [2, 2]] Output: [1, 0] [2, 0] or [1, 1] [2, 1] Input: [[3, 1], [7, 2]] [[0, 4], [1, 1]] Output: [1, 0] or [0, 0] [1, 0] Input: [[2, 2]] [[1, 1]] Output: (No output tuples).
Input and output may be via STDIN, STDOUT, CLA, function input/return, etc. Standard loopholes apply. This is code-golf: shortest code in bytes wins.
To clarify the spec and provide initial ideas, this pastebin provides a reference solution in Python. The
best_block function is a sample solution to this challenge, and running the program will provide more verbose input and output.