To start us off, here is a fun fact about this task: out of the 2111 tests, 1295 were hand-crafted and all implementations were checked against human-provided answers for those :)
Our solution will begin with a very simple first phase: tap everything where you don’t have to make a decision. In other words, tap all basic lands (for 1 mana each), all bounce lands (for 2 mana each), and all Tron pieces (for some amount of colorless mana). Subtract the mana produced this way from the requirements. From this point on, we can ignore the lands mentioned above. This leaves us with roughly one half of the original card pool.
If we don’t have any fetch lands on the battlefield, we get to ignore the entire library. Only the lands on the battlefield matter.
For now, let’s ignore the lands that can hurt us, and let’s just focus on making the right decisions. How can we tell which land should produce which mana color?
There are various ways to approach this question, for instance, a lot of case analysis. Our preferred way is one that uses a more advanced tool but has no special cases: network flow. Indeed, network flow is a good way to model our situation.
We will have a node for each land on the battlefield. For each of these nodes, there is an edge from the source to the node with capacity 1. This means that this land can generate at most 1 mana. Next, we will have 7 nodes: one for each mana type (5 colors + colorless) and one for generic mana. Each land-node will be connected to those type-nodes that correspond to the colors that can be produced by that particular land. Additionally, each of the six mana type nodes has an outgoing edge leading into the generic mana node. This edge (with infinite capacity) represents that any mana can be used to pay the generic mana requirement. Finally, each of the seven mana-type-nodes has an edge to the sink, and the capacity of this edge is the required amount of mana of that type.
Clearly, flows in this network correspond to all possible ways to tap some of the lands we have for mana and to use that mana to pay the required amounts. We can cast the spell if and only if the maximum flow in our network saturates all the edges that lead into the sink.
We are almost done with the easy subproblem. All that remains are the pain lands, and City of Brass. These can sometimes hurt us. How do we incorporate them into the previous solution?
First of all, we may tap some of the pain lands for colorless mana without loss of life. We will try all possibilities for the number of such lands and evaluate each of those separately.
We will now add two more nodes to our flow network: a node D that represents all mana that gives us damage when produced, and a node P that only represents pain lands. The capacity of the edge from source to D will be one less than our current life total, as we cannot produce more painful mana than that amount. Each City of Brass will have an edge from D to its own node with capacity 1. Additionally, there will be an edge from D to P and the capacity of this edge will be the number of pain lands we didn’t tap for colorless mana. Finally, we’ll have edges from P to each pain land, and from each pain land to the colors it can produce.
Now that we are done with the easy subproblem, it’s fetching time. The main issue here is the extra damage dealt by fetched shock lands. How to deal with these?
The thing that will save us here is the amount of life we have. Fetching an untapped shock land costs 3 life. The highest allowed life total is 20. Hence we can fetch at most 6 shock lands. With 6 fetch lands on the battlefield, this leaves us with at most 28 shock lands in the library, and therefore at most ${28\choose 6} < 400,000$ ways to choose which specific 6 lands to fetch. (Actually, it’s much fewer, as there are only 10 distinct shock lands.) Again, we can afford to try all of these and see whether any of those possibilities gives us a working solution.
Once we choose a specific set of shock lands to fetch, we will subtract 2 times their count from our life total. We will now add a new part to our flow network. The node D that represents damage taken will now also have edges of capacity 1 into nodes that correspond to fetch lands. There will be new nodes for fetchable lands in the library. Each fetch land will have edges to lands it can fetch. Each fetchable land node will have capacity 1 (to model that it can only be fetched once, even if multiple fetch lands allow fetching it). All fetchable land nodes have edges into mana type nodes, just like any other lands.
Above: a sample subset of the flow graph.
For a slightly alternate solution with even less cases and an even more advanced algorithm, all loss of life can be modeled as costs, and then we can find the minimum cost maximum flow and check that both the size is optimal and the cost is lower than your starting life total. With this approach, Tron is actually the only thing you need to special-case.