Simple and correct algorithm for determining colors of Magic: the Gathering deck

This sounds like something completely trivial, but every single site including deckbox, tappedout etc. is doing it wrong, so I'm writing this public as a public service announcement.

Wrong algorithms everybody uses

There are two very popular algorithms:

• Check colored symbols on lands, use that as deck's colors
• Check colored symbols in mana cost, use that as deck's colors

This sounds about right, but it fails on anything more complicated than a core set intro pack:

• Phyrexian mana a deck has no way to pay for other than with life counts - so all Pod decks ever were suddenly "/u" because of 1-of Phyrexian Metamorph, half of UW Delver decks were "/r" because of some sideboard Gut Shots etc.
• Hybrid mana makes a deck all its colors, so deck with no mana sources but basic Mountains which contains and some Boros Reckoners and Rakdos Cacklers is somehow an R/b/w deck.
• Reanimator decks which literally cannot cast half of their off-color fatties still count their colors.

And in addition to extra colors this logic would also miss a lot of cases, like non-land mana sources, sources of "any" colored mana like Cavern of Souls, off-color activated abilities and so on.

Basically, a total disaster. Now if there was no way to do it correctly or the algorithm to do so was too complicated that would be excusable, but it turns out it's really simple.

Simple and correct algorithm

So here's a simple definition which deals with all these problems. X is one of the colors of a deck, if the deck:

• Can use one of its cards to generate mana in color X
• Can pay colored mana cost X to cast one of its cards or pay for ability on one of its cards (colorless mana costs don't count, hybrid, 2/c, and Phyrexian mana costs are all treated the same as normal costs)

And the algorithm is correspondingly simple:

• Take all cards of the deck, including its sideboard
• List all colors any of these cards could produce
• List all colors any of these cards could use
• Intersection of these two lists is the answer

And that's all! It's really simple, and deals with all problems I mentioned.

Thanks to Oracle using very regular templating it just takes a few regular expressions to make a list of colors card generates and can use. I even put the list on github as .tsv file.

Possible and impossible improvements

There are some decks for which simple algorithm given here doesn't work perfectly, but for such cases I haven't been able to find any consistent answers, and any more complex algorithm just lead to different problems.

The monored deck mentioned before with Boros Reckoners and Rakdos Cacklers is correctly identified as monored, but if we include Cavern of Souls in it, it's now R/w/b, since you can now tap Caverns for white/black and use it to cast Reckoner/Cackler - you have no real reason not to tap it for red, but the algorithm doesn't know that.

The algorithm could instead try to find the smallest group of mana colors fully cast everything, but then if you for some inexplicable reason put Cavern of Souls and Boros Reckoner in otherwise monogreen deck, minimal coloring for this deck would be both G/r and G/w - G/r/w the algorithm gives wouldn't be minimal, and G would be incorrect. There's simple mathematical proof based on lattices that explains why this won't work if you want to do some theory. The algorithm could check if lattice's least upper bound is also a solution, and if so give it, otherwise give greatest upper bound, but it's fairly inelegant.

One way the algorithm could be improved but at cost of quite a bit of complexity is by tracking entire costs as an unit, not each symbol. So an otherwise monogreen deck with Progenitus, Quicksilver Amulet, and Noble Hierarch will be treated as G/w/u (since w/u are in colors of Progenitus, and Hierarch can pay for them), even though it's literally impossible to hardcast Progenitus. This is one area where a better algorithm is possible, but it doesn't seem to be worth sacrificing simplicity.

The algorithm doesn't track number of colored mana sources, so otherwise monogreen deck with 4 Birds of Paradise and Progenitus is treated as 5-color deck, even if it doesn't have any way of casting hard-Progenitus without 8 Birds. This is difficult to fix, since any kind of "another mana of the same color" effects, untap effects, blink effects, clones, etc. can all increase amount of colored mana, and we'd need to track them. Right now we don't need to care since they never add another color.

And then of course there could be crazy decks. Maybe your plan is to Act of Treason someone else's guildmage and your 5-color mana sources are meant for paying that? Or maybe you're planning to steal some Birds of Paradise for your off-color flashback costs which you have full intention of paying? With enough crazy it's possible to come up with a deck that breaks every algorithm.

Available on github now

I put script implementing algorithm described in the post on github. Feel free to use it any way you wish.