# Can you cast the spell?

In Magic: the Gathering, mages (known as "planeswalkers") battle each other by casting spells. Spells cost mana. Five colors of mana exist: White, Blue, Black, Red, and Green, represented as {W}, {U}, {B}, {R}, and {G}, respectively.

A spell's cost is slightly more complex. The cost can be any combination of the following:

• One or more colors
• One or more colorless, represented as {X}, where X is a positive integer
• One or more hybrids, represented as {Y/Z}, where Y and Z are either a color (represented by one of the five letters) or colorless, represented by a positive integer

The following rules apply when attempting to cast a spell:

• A color in a cost must be satisfied by one mana of that color
• A colorless cost {X} may be satisfied by X mana of any color
• A hybrid cost {Y/Z} may be satisfied by satisfying either Y or Z
• Note that braces are not nested
• Y and Z are not hybrid

Write a program or function that, given a pool of mana and a cost, prints or returns true (or some truthy value) if and only if the mana in that pool can satisfy the cost, else false (or some falsy value).

A mana pool is a non-empty string of the format:

Color1,Color2,Color3,...,Colorn-1,Colorn

A cost is a non-empty string of the format:

Cost1,Cost2,Cost3,...,Costn-1,Costn

Examples

In the format Pool Cost -> ExpectedOutput (with a space between Pool and Cost):

{R},{R},{G},{B},{R} {4},{R} -> True
{G},{G},{G},{G},{W},{W},{W} {2/W},{2/U},{2/B},{2/R},{2/G} -> False
{G},{G},{R} {R/G},{G/B},{B/R} -> True
{R},{R},{R},{G} {1},{G},{2/G}-> True
{R} {R},{R},{R},{R},{R} -> False
{W},{R},{R} {2/W},{W/B} -> True
{U},{U} {1} -> True
{W},{R},{G} {1},{2} -> True

• Is it possible to have colorless mana in the pool? – nutki May 6 '15 at 14:56
• @nutki In the real game, yes. In the challenge, no. Only the five colors defined in the challenge exist for the purposes of the challenge. – Rainbolt May 6 '15 at 14:59
• I've been away from magic too long. Hybrid costs?!? – Sparr May 6 '15 at 17:38
• @Sparr They were introduced in Ravnica, back in 2005 – murgatroid99 May 6 '15 at 17:41
• @murgatroid99 I quit when 6E came out. None of my friends were willing to adapt to the new rules :( – Sparr May 6 '15 at 18:08

# Pyth, 555352 50 bytes

FN*Fmsm?k}kG^Gvkcd\/ceKc-rz0Hd\,#=sN)I!.-NhK1B)E0


Try it online: Demonstration or Test harness

Notice that the time and memory complexity is really bad. So the second example doesn't work. I allocates about 1.6 GB of Ram before it crashes on my machine.

### Explanation

The explanation is for the 53 solution. The only difference is, that the initial parsing happens in the middle instead of the beginning.

Kc-rz0"{}"dFN*Fmsm?k}kG^Gvkcd\/ceKc-rz0H\,#=sN)I!.-NhK1B)E0


So here's the initial parsing.

Kc-rz0Hd
rz0     convert input() to lowercase
-   H   remove all curly brackets (H = "{}")
c      d  split at the space
K          assign to K


So the input "{W},{R},{R} {2/W},{W/B}" gets converted into ['w,r,r', '2/w,w/b'].

m               ceK\,    map each cost d of the costs split by "," to:
s                         the sum of
m         cd\/           map each value k of cost split by "/" to:
k                        k
? }kG                     if k in "abcdef...xyz" else
^Gvk                 Cartesian product with "abc...yz" of int(k) repeats


So what does this do? The cost input '2/w,w/b' gets converted into:

[['aa', 'ab', 'ac', ..., 'zx', 'zy', 'zz', 'w'], 'wb']


Every string in ['aa', 'ab', 'ac', ..., 'zx', 'zy', 'zz', 'w'] satisfies {2/W} and every char in 'wb' satisfies {w/b}.

Now we generate the Cartesian product of these lists (or strings) and see, if any combination can be produced with the mana-pool.

FN*F...              )      for N in Cartesian product of ...:
#   )                   while 1:
=sN                      N = sum(N)
this flattens N
I!.-NhK            if not (subtract mana pool from N):
1             print 1 (True)
B            break
E      else:
0       print 0 (False)

• truthy and falsy values are allowed, not just True and False. – isaacg May 6 '15 at 21:54
• You can save a character by inling the assignment to K. Put Kc-rz0"{}") where K is first used, and remove the initial assignment to K. – isaacg May 6 '15 at 23:27
• @isaacg Oh, should have seen that. Thanks. – Jakube May 6 '15 at 23:58
• @Rainbolt You accepted a non-working solution. Well it worked when I posted it, but Pyth changed a lot. I updated it and also saved 2 more bytes. – Jakube Jun 18 '15 at 18:10
• @Jakube Thanks, but this answer needs to work using an interpreter that was available at the time the challenge was posted, not some new updated interpreter. – Rainbolt Jun 18 '15 at 19:22

# Python 2.7, 412 characters

import re,collections as C
r,C=re.findall,C.Counter
def g(m,h,c,v):
try:return t(m,h,c+int(v))
except:
if m[v]:return t(m-C({v:1}),h,c)
def t(m,h,c):return any(g(m,h[1:],c,v)for v in h[0].split('/'))if h else sum(m.values())>=c
def f(m,c):m=C(r(r'\w',m));c=[filter(None, x)for x in zip(*r(r'(\w+/\w+)|(\d+)|(\w)',c))];m.subtract(C(c[2]));print all(x>=0 for x in m.values())*t(m,c[0],sum(int(x)for x in c[1]))


The function f is the one that does the check. It takes the mana pool and cost as string arguments, and prints 1 when the mana satisfies the cost and 0 otherwise. For example, f('{R},{R},{G},{B},{R}', '{4},{R}') prints 1.

Ungolfed, it basically looks like this

import re
from collections import Counter
def helper(mana, hybrids, colorless, option):
try:
option = int(option) # See if option is an integer
# For colorless hybrid, just add the value to the colorless amount
# to check at the end.
return check_hybrids(mana, hybrids, colorless + option)
except ValueError: # Option is a mana letter
# For colored hybrid costs, check if any of that color is
# available, then try to pay the rest of the cost with 1 less
# of that color.
if mana[option] >= 0:
return check_hybrids(mana - Counter({option: 1}), hybrids, colorless)
else:
return False
def check_hybrids(mana, hybrids, colorless):
'''Check whether the given mana pool can pay the given hybrid costs and colorless costs'''
if hybrids:
# For each option in the first hybrid cost, check whether the
# rest of the cost can be paid after paying that cost
return any(helper(mana, hybrids[1:], colorless, option) for option in hybrids[0].split('/'))
else:
# When there are no remaining hybrid costs, if there is enough
# remaining mana to pay the colorless costs, we have success
return sum(m.values()) > colorless
def can_cast(mana_str, cost_str):
mana = Counter(re.findall(r'\w', mana_str))
# transpose to get separate lists of hybrid, colorless, and colored symbols
cost = zip(*re.findall(r'(\w+/\w+)|(\d+)|(\w)',cost_str))
cost = [filter(None, sublist) for sublist in cost] # Remove unfound symbols
mana.subtract(Counter(cost[2]))
# After subtracting the single-colored cost from the mana pool, if
# anything in the mana pool is negative, we didn't have enough to
# pay for that color.
if any(x <=0 for x in mana.values()):
return False
return check_hybrids(mana, cost[0], sum(int(x)for x in cost[1]))
`