Magic: the Gathering to gra karciana, w której gracze grają między innymi w karty przedstawiające stworzenia, które mogą następnie zaatakować drugiego gracza lub obronić się przed atakami drugiego gracza, blokując.

W tym wyzwaniu polegającym na grze w golfa Twój program zastąpi magiczny gracz decydujący o sposobie blokowania w walce.

Każde stworzenie ma dwa istotne atrybuty: Moc i wytrzymałość. Moc stworzenia to ilość obrażeń, jakie może zadać w walce, a jego wytrzymałość to ilość obrażeń niezbędnych do jego zniszczenia. Moc zawsze wynosi co najmniej 0, a wytrzymałość zawsze wynosi co najmniej 1.

Podczas walki w Magii gracz, którego tura jest zadeklarowana, atakuje przeciwnika niektóre ze swoich stworzeń. Następnie drugi gracz, znany jako obrońca, może przypisać swoje stworzenia jako blokerów. Stworzenie może zablokować tylko jedno stworzenie na walkę, ale wszystkie stworzenia mogą zablokować to samo stworzenie.

Po ogłoszeniu blokady, atakujący gracz decyduje, dla każdego atakującego stwora, który został zablokowany, jak rozłożyć obrażenia (równe jego mocy), które stwór zadaje stworom blokującym je.

Następnie zadawane są obrażenia. Każde stworzenie zadaje obrażenia równe swojej mocy. Atakowane stworzenia, które zostały zablokowane, zadają obrażenia, jak opisano powyżej. Odblokowane atakujące stworzenia zadają obrażenia broniącemu się graczowi. Blokujące stworzenia zadają obrażenia stworzeniu, które zablokowały. Stworzenia należące do broniącego się gracza, które nie blokowały, nie zadają żadnych obrażeń. (Nie trzeba blokować stworzeń).

Wreszcie każde stworzenie zadające obrażenia równe lub większe niż jego wytrzymałość jest niszczone i usuwane z pola bitwy. Żadna ilość obrażeń mniejsza niż wytrzymałość stworzenia nie ma wpływu.

Oto przykład tego procesu:

Istota o mocy P i wytrzymałości T jest reprezentowana jako P/T

Attacking:
2/2, 3/3
Defending player's creatures:
1/4, 1/1, 0/1
Defending player declares blockers:
1/4 and 1/1 block 2/2, 0/1 does not block.
Attacking player distributes damage:
2/2 deals 1 damage to 1/4 and 1 damage to 1/1
Damage is dealt:
2/2 takes 2 damage, destroyed.
3/3 takes 0 damage.
1/1 takes 1 damage, destroyed.
1/4 takes 1 damage.
0/1 takes 0 damage.
Defending player is dealt 3 damage.

Broniący się gracz ma 3 cele w walce: Zniszcz stwory przeciwnika, zachowaj własne stwory i zadaj jak najmniej obrażeń. Ponadto, stworzenia o większej mocy i wytrzymałości są cenniejsze.

Aby połączyć je w jedną miarę, powiemy, że wynik broniącego się gracza podczas walki jest równy sumie mocy i twardości ocalałych stworzeń, minus suma mocy i twardości ocalałych przeciwników, minus jeden połowa obrażeń zadawanych obrońcy. Broniący gracz chce zmaksymalizować ten wynik, podczas gdy atakujący gracz chce go zminimalizować.

W pokazanej powyżej walce wynik był następujący:

Defending player's surviving creatures:
1/4, 0/1
1 + 4 + 0 + 1 = 6
Attacking player's surviving creature:
3/3
3 + 3 = 6
Damage dealt to defending player:
3
6 - 6 - 3/2 = -1.5

Gdyby obrońca nie blokował się wcale w opisanej powyżej walce, wynik byłby taki

8 - 10 - (5/2) = -4.5

Optymalnym wyborem dla broniącego się gracza byłoby zablokowanie za 2/2pomocą 1/1i 1/4, i zablokowanie za 3/3pomocą 0/1. Gdyby to zrobili, tylko 1/4i oni 3/3przeżyliby, a obrońca nie zadałby żadnych obrażeń, dzięki czemu uzyskałby wynik

5 - 6 - (0/2) = -1

Twoim wyzwaniem jest napisanie programu, który wygeneruje optymalny wybór blokowania dla broniącego się gracza. „Optymalny” oznacza wybór, który maksymalizuje wynik, biorąc pod uwagę, że przeciwnik rozdziela obrażenia w sposób, który minimalizuje wynik, biorąc pod uwagę sposób zablokowania.

Jest to maksymalny: maksymalny wynik w rozkładzie obrażeń, który minimalizuje wynik dla każdej kombinacji blokującej.

Wkład: Dane wejściowe będą się składały z dwóch list 2-krotek, przy czym każda 2-krotka ma postać (Moc, Wytrzymałość). Pierwsza lista będzie zawierać moce i wytrzymałość każdego atakującego stwora (stworów przeciwnika). Druga lista będzie zawierać moce i wytrzymałość każdego z twoich stworzeń.

Krotki i listy mogą być reprezentowane w dowolnym dogodnym formacie, takim jak:

[[2, 2], [3, 3]]
[[1, 4], [1, 1], [0, 1]]

Wyjście: Wyjście będzie składało się z serii 2 krotek w formie (blokujące stworzenie, zablokowane stworzenie) - to znaczy jedno z twoich stworów, po którym następuje jedno z ich stworzeń. Do stworzeń będzie odwoływał się ich indeks na listach wejściowych. Indeksy mogą być indeksowane 0 lub 1. Ponownie, każdy wygodny format. Każde zamówienie jest w porządku. Na przykład optymalny scenariusz blokowania z góry, biorąc pod uwagę powyższe dane wejściowe, można przedstawić jako:

[0, 0]    # 1/4 blocks 2/2
[1, 0]    # 1/1 blocks 2/2
[2, 1]    # 0/1 blocks 3/3

Przykłady:

Input:
[[2, 2], [3, 3]]
[[1, 4], [1, 1], [0, 1]]
Output:
[0, 0]
[1, 0]
[2, 1]

Input:
[[3, 3], [3, 3]]
[[2, 3], [2, 2], [2, 2]]
Output:
[1, 0]
[2, 0]
or
[1, 1]
[2, 1]

Input:
[[3, 1], [7, 2]]
[[0, 4], [1, 1]]
Output:
[1, 0]
or
[0, 0]
[1, 0]

Input:
[[2, 2]]
[[1, 1]]
Output:

(No output tuples).

Wejścia i wyjścia mogą odbywać się za pośrednictwem STDIN, STDOUT, CLA, funkcji wejścia / powrotu itp. Obowiązują standardowe luki . To jest code-golf: wygrywa najkrótszy kod w bajtach.

Aby wyjaśnić specyfikację i przedstawić początkowe pomysły, ta pasta stanowi rozwiązanie referencyjne w języku Python. Ta best_blockfunkcja stanowi przykładowe rozwiązanie tego problemu, a uruchomienie programu zapewni bardziej szczegółowe dane wejściowe i wyjściowe.

JavaScript (ES7),  354  348 bajtów

Pobiera dane wejściowe jako ([attackers], [defenders]).

(a,d,O,M)=>eval(`for(N=(A=a.push([,0]))**d.length;N--;)O=a[X='map'](([P,T],i)=>S-=((g=(n,l)=>n?l[X](([t,S],i)=>g(n-1,b=[...l],b[i]=[t-1,S])):m=l[X](([t,S])=>s+=t>0&&S,s=0)&&s>m?m:s)(P,l[n=0,i][X](m=([p,t])=>[t,p+t,n+=p])),n<T&&P+T)+(l[i]<1?T/2:-m),S=0,d[X]((x,i)=>l[(j=N/A**i%A|0)<A-1&&o.push([i,j]),j].push(x),o=[],l=a[X](_=>[])))&&S<M?O:(M=S,o)`)

Wypróbuj online!

Mniej golfa i sformatowane

Ten kod jest identyczny z wersją golfową, tylko bez mapaliasów i eval()opakowania dla czytelności.

(a, d, O, M) => {
  for(N = (A = a.push([, 0])) ** d.length; N--;)
    O =
      a.map(([P, T], i) =>
        S -=
          (
            (g = (n, l) =>
              n ?
                l.map(([t, S], i) => g(n - 1, b = [...l], b[i] = [t - 1, S]))
              :
                m = l.map(([t, S]) => s += t > 0 && S, s = 0) && s > m ? m : s
            )(
              P,
              l[n = 0, i].map(m = ([p, t]) => [t, p + t, n += p])
            ),
            n < T && P + T
          ) + (
            l[i] < 1 ? T / 2 : -m
          ),
        S = 0,
        d.map((x, i) =>
          l[
            (j = N / A ** i % A | 0) < A - 1 && o.push([i, j]),
            j
          ].push(x),
          o = [],
          l = a.map(_ => [])
        )
      ) && S < M ? O : (M = S, o)
  return O
}

W jaki sposób?

Inicjalizacja i główna pętla

$0$push$A$

A = a.push([, 0])

Zamierzamy zablokować to obojętne stworzenie zamiast nie blokować żadnego stworzenia. Pozwala to na pewne uproszczenia w kodzie.

$A^D$$D$$N$

for(N = (A = a.push([, 0])) ** d.length; N--;)

$S$$M$$o$$O$ .

$M$$O$

O = (...) && S < M ? O : (M = S, o)

Budowanie naszej obrony

$l$

d.map((x, i) =>              // for each defender x at position i:
  l[                         //   update l[]:
    (j = N / A ** i % A | 0) //     j = index of the attacker that we're going to block
    < A - 1 &&               //     if this is not the 'dummy' creature:
    o.push([i, j]),          //       add the pair [i, j] to the current solution
    j                        //     use j as the actual index to update l[]
  ].push(x),                 //   push x in the list of blockers for this attacker
  o = [],                    //   initialize o to an empty list
  l = a.map(_ => [])         //   initialize l to an array containing as many empty lists
                             //   that there are attackers
)                            // end of map()

Optymalizacja ataku

Decyzje atakujących są ze sobą niezwiązane. Globalne optimum dla strony atakującej jest sumą lokalnych optymów dla każdego atakującego.

$P$$T$$i$

a.map(([P, T], i) => ...)

$l[i]$

l[n = 0, i].map(m = ([p, t]) => [t, p + t, n += p])

$n$

$g$$P$

(g = (n, l) =>            // n = remaining damage points; l = list of blockers
  n ?                     // if we still have damage points:
    l.map(([t, S], i) =>  //   for each blocker of toughness t and score S at index i:
      g(                  //     do a recursive call:
        n - 1,            //       decrement the number of damage points
        b = [...l],       //       create a new instance b of l
        b[i] = [t - 1, S] //       decrement the toughness of blocker i
      )                   //     end of recursive call
    )                     //   end of map()
  :                       // else:
    m =                   //   update the best score m (the lower, the better):
      l.map(([t, S]) =>   //     for each blocker of toughness t and score S:
        s += t > 0 && S,  //       add S to s if this blocker has survived
        s = 0             //       start with s = 0
      ) &&                //     end of map()
      s > m ? m : s       //     set m = min(m, s)
)                         //

Aktualizacja wyniku obrońcy

Po każdej iteracji atakującego aktualizujemy wynik obrońcy o:

S -= (n < T && P + T) + (l[i] < 1 ? T / 2 : -m)

Lewa część odejmuje wynik atakującego, jeśli przeżył. Prawa część odejmuje połowę wytrzymałości atakującego, jeśli atak w ogóle nie został zablokowany, lub dodaje najlepszy wynik atakującego w przeciwnym razie (który jest najgorszy z punktu widzenia strony broniącej się).