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
źródło
Odpowiedzi:
Pyth,
55535250 bajtówWypró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.
Oto wstępna analiza.
Tak więc dane wejściowe
"{W},{R},{R} {2/W},{W/B}"
są konwertowane na['w,r,r', '2/w,w/b']
.Co to robi? Nakład kosztów
'2/w,w/b'
zostaje przekształcony w: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.
źródło
True
iFalse
.K
. Umieść,Kc-rz0"{}")
gdzieK
jest używane po raz pierwszy, i usuń początkowe przypisanie doK
.Python 2.7, 412 znaków
Ta funkcja
f
wykonuje tę kontrolę. Bierze pulę many i koszt jako argumenty łańcuchowe i drukuje,1
gdy mana spełnia koszt i w0
inny sposób. Na przykładf('{R},{R},{G},{B},{R}', '{4},{R}')
drukuje1
.Bez golfa, w zasadzie wygląda to tak
źródło