W Magic: the Gathering magowie (znani jako „planeswalkers”) walczą ze sobą, rzucając zaklęcia. Zaklęcia kosztują manę. Istnieje pięć kolorów many: biały, niebieski, czarny, czerwony i zielony, reprezentowane odpowiednio jako {W}, {U}, {B}, {R} i {G}.

Koszt czaru jest nieco bardziej złożony. Koszt może być dowolną kombinacją następujących elementów:

• Jeden lub więcej kolorów
• Co najmniej jedna bezbarwna, reprezentowana jako {X}, gdzie X jest dodatnią liczbą całkowitą
• Jedna lub więcej hybryd, reprezentowanych jako {Y / Z}, gdzie Y i Z są albo kolorem (reprezentowanym przez jedną z pięciu liter) lub bezbarwnym, reprezentowanym przez dodatnią liczbę całkowitą

Podczas rzucania zaklęcia obowiązują następujące zasady:

• Kolor kosztu musi być zaspokojony przez jedną manę tego koloru
• Bezbarwny koszt {X} może zostać pokryty przez X many dowolnego koloru
• Koszt hybrydowy {Y / Z} może być spełniony przez spełnienie Y lub Z
  • Zauważ, że nawiasy klamrowe nie są zagnieżdżone
  • Y i Z nie są hybrydowe

Napisz program lub funkcję, która, biorąc pod uwagę pulę many i koszt, drukuje lub zwraca wartość true (lub pewną prawdziwą wartość) wtedy i tylko wtedy, gdy mana w tej puli może pokryć koszt, w przeciwnym razie false (lub pewną wartość fałszowania).

Pula many jest niepustym ciągiem formatu:

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

Koszt jest niepustym ciągiem formatu:

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

Przykłady

W formacie Pool Cost -> ExpectedOutput(ze spacją między pulą a kosztem):

{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

Pyth, 55 53 52 50 bajtów

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

Wypróbuj online: Demonstracja lub Uprząż testowa

Zauważ, że złożoność czasu i pamięci jest naprawdę zła. Drugi przykład nie działa. Przydzielam około 1,6 GB pamięci RAM, zanim ulegnie awarii na moim komputerze.

Wyjaśnienie

Wyjaśnienie dotyczy 53 rozwiązania. Jedyną różnicą jest to, że wstępne analizowanie odbywa się w środku zamiast na początku.

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

Oto wstępna analiza.

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

Tak więc dane wejściowe "{W},{R},{R} {2/W},{W/B}"są konwertowane na ['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

Co to robi? Nakład kosztów '2/w,w/b'zostaje przekształcony w:

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

Każdy ciąg znaków ['aa', 'ab', 'ac', ..., 'zx', 'zy', 'zz', 'w']spełnia {2/W}i każdy znak w'wb' spełnia {w/b}.

Teraz generujemy iloczyn kartezjański z tych list (lub łańcuchów) i sprawdzamy, czy można utworzyć dowolną kombinację z pulą many.

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)

Python 2.7, 412 znaków

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]))

Ta funkcja fwykonuje tę kontrolę. Bierze pulę many i koszt jako argumenty łańcuchowe i drukuje, 1gdy mana spełnia koszt i w 0inny sposób. Na przykład f('{R},{R},{G},{B},{R}', '{4},{R}')drukuje1 .

Bez golfa, w zasadzie wygląda to tak

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]))