Magic: The Gathering, Paying for Spells

Question

^{For more MtG-goodness: Magic: The Gathering Combat with Abilities}

Premise:

In Magic: the Gathering, you cast spells by paying their mana cost by tapping lands for the required amount. These lands can produce one of the five colors which are:

• White (W)
• Blue (U)
• Black (B)
• Red (R)
• Green (G)

The cost is made up of two parts: a number which is the generic mana requirement, and a series of symbols representing the colored mana requirement. The number is the generic mana cost and can use any color of mana to satisfy it, e.g. (3) can be paid with WGG. The symbols are a 1:1 requirement of a specific color. e.g. WWUBR would require 2 white mana, 1 blue, 1 black and 1 red. The Generic part will always come before the Colored part. As a reminder, (0) is a valid cost and must be handled.

You can have costs that are entirely generic, or entirely colored, or both. For example, the following card has a cost of 4BB and is be paid with 4 of whatever colored mana and 2 black mana:

Lands in this challenge will each produce one mana. However, we will consider lands that can produce multiple colors but still only yield 1 mana. E.g. G will produce a green mana, WG can produce either 1 white or 1 green.

Input:

You will be given two inputs, a card's cost and a list of lands.

The card's cost can either be a string, or a tuple containing a number and a string for the colored part. If there's no generic part, you can pad the string/tuple with a 0.

The land list will be a list of strings where each one is what a given land can produce. This list can be empty (you have no lands). You can also take this as a list of ints using bit-mask logic but post your scheme if you do. Order is also up to you if it matters, otherwise it'll be assumed in WUBRG order.

#Example input formats
"4BB", ("WG","B","B") #
(4,"BB"), (7,3,3)     #Both should return falsy

Output:

A truthy value if you can successfully pay the cost given your lands and a falsey value if you cannot.

Rules:

• You'll be guaranteed valid input
• Mana will be assumed to always be in "WUBRG" order. If you want a different order, state so in your answer.
• Colors will always be grouped in the cost, e.g. "WWUBBRG"
• Input will use either all Uppercase or all lowercase, your choice.
• You should be able to handle regex 127[WUBRG]{127} and 254 lands.
• Standard loopholes forbidden
• This is code-golf, shortest answer per language wins

Examples:

"0", ("")                => 1
"1BB", ("WG","B","B")    => 1
"BB", ("WG","B","B")     => 1
"WB", ("WG","B","B")     => 1
"1UB", ("W","U","B")     => 1
"1BB", ("WB","WB","WG")  => 1
"1", ("WG","B","B")      => 1
"1BB", ("WGR","WB","WB") => 1
"WUBRG", ("W","U","B","R","G")  => 1
"1WWUBB", ("W","WG","U","B","B","R")  => 1
"10BB", ("WGR","WB","WB","B","B","B","B","B","B","B","B","B") => 1

"R", ("")                => 0
"4", ("WG","B","B")      => 0
"1BB", ("WG","WB")       => 0
"1UB", ("WG","W","UB")   => 0
"1UBR", ("W","WG","UBR") => 0
"WUBRG", ("WUBRG")       => 0
"1WWUBB", ("W","WG","U","B","B")  => 0
"10UU", ("WGR","WB","WB","B","B","B","B","B","B","B","B","B") => 0

Answer 1

JavaScript (ES6), 91 bytes

Takes input as (cost)(lands):

• \$cost\$ is a list of characters in BGRUW order, prefixed with the generic part, even when it's \$0\$
• \$lands\$ is a list of strings.

a=>g=([c,...r],n=0,s=e='')=>[...n+s].sort()+e==a|(c&&[e,e,...c].some((c,i)=>g(r,n+!i,s+c)))

Try it online!

Commented

a =>                        // main function taking the array a[] describing the cost
  g = (                     // g = recursive function taking:
    [c, ...r],              //   c = next land string; r[] = remaining land strings
    n = 0,                  //   n = generic mana, initialized to 0
    s = e = ''              //   s = generated cost string, initialized to e = empty string
  ) =>                      //
    [...n + s].sort() + e   // prepend n to s, split, sort and force coercion to a string
    == a | (                // if this is matching a[], the test is successful
      c &&                  // if c is defined:
      [                     //   try the following recursive calls:
        e,                  //     - increment n and append nothing to s
        e,                  //     - do nothing
        ...c                //     - leave n unchanged and append a character to s
      ].some((c, i) =>      //   for each c at position i in the above array:
        g(r, n + !i, s + c) //     process the recursive call
      )                     //   end of some()
    )                       // end of the recursive part

Answer 2

Python 2, 131 129 bytes

lambda (g,c),m:any(all(c[i]in p[i]for i in range(l(c)))for p in permutations(m,l(c)))*(g<=l(m)-l(c))
l=len
from itertools import*

Try it online!

Answer 3

Retina, 60 bytes

\d+
*
~["^("|'|]")*\n"1,L$`(?<=(^|.*¶)+).*
(?($#1)^|([_$&]))

Try it online! Link includes test cases. Explanation:

\d+
*

Convert the generic mana to unary. This uses repeated _s.

1,L`.*

Match all lines after the first, i.e. the list of lands. (This would normally match again at the very end of the input, but the lookbehind prevents that.)

(?<=(^|.*¶)+)

Capture the 1-indexed line number in $#1.

$
(?($#1)^|([_$&]))

Replace each land with a regex that captures costs matching that land or generic costs, but only once.

|'|

Join the resulting regexes with |s.

["^("]")*\n"

Wrap the regex in ^( and )*\n (I can't seem to insert a ¶ here).

~

Count the number of matches of that regex on the current value.

Example: For the case of 1BB¶WB¶WB¶WG the generated regex is:

^((?(2)^|([_WB]))|(?(3)^|([_WB]))|(?(4)^|([_WG])))*\n

which _BB¶WB¶WB¶WG matches as required.

Answer 4

Jelly, 21 bytes

Œpµ®œ-)Ạ
L<⁴Ṫ©L+Ḣ¤ȯçṆ

Try it online!

Outputs

The input format is what really makes this hard for Jelly. Because Ṫ and Ḣ modify the array, we need to use © and ® in addition. With 3 separate inputs this would be 18 bytes. (Although I'm sure there's 14 or so byte solution waiting to be posted by one of the Jelly masterminds.)

Answer 5

Pyth, 25 bytes

&glQ+hAElH}k.-LHusM*GHQ]k

Try it online!

If Pyth had a "Cartesian product of array" function like Jelly's Œp, this would easily beat my Jelly solution. Currently that is done by usM*GHQ]k.

Answer 6

Perl 6, 56 46 bytes

{(1 x*~*).comb.Bag⊆any [X] $(1 X~$_)>>.comb}

Try it online!

Curried function. Takes input as (@lands)($generic_cost, $colored_costs) with an explicit 0 for generic cost. The basic idea is to introduce a new symbol 1 representing generic mana and use Perl 6 Bags (multisets) to check whether it's possible to obtain the required mana from lands.

Explanation

{ ... }  # Anonymous block returning WhateverCode
  # Preprocess cost
  1 x*    # '1' for generic mana repeated times generic cost
      ~*  # Concat with colored costs
 (      ).comb  # Split into characters
              .Bag  # Convert to a Bag (multiset)
                             # Preprocess lands
                             1 X~$_   # Prepend '1' to each land
                           $(      )  # Itemize to make 1-element lists work
                                    >>.comb  # Split each into chars
                       [X]  # Cartesian product, yields all possible ways
                            # to select colors from lands
                  # Finally check if the cost Bag is a subset of any possible
                  # color selection (which are implicitly converted to Bags)
                  ⊆any

Answer 7

Haskell, 94 bytes

x#[]=[]
x#(s:t)|x`elem`s=t|0<1=s:x#t
(e,[])?s=length s>=e
(e,x:y)?s|x#s==s=0>1|0<1=(e,y)?(x#s)

Try it online!

We rely on the fact that all colors will be given in the same order in the cost and in the land list. First we tap the lands giving the required colored mana and after that just check that we still have enough lands to pay the colorless cost.