Magic: the Gathering est un jeu de cartes à échanger où, entre autres, les joueurs jouent des cartes représentant des créatures, qui peuvent ensuite attaquer l'autre joueur, ou se défendre contre les attaques de l'autre joueur en bloquant.

Dans ce défi de code-golf, votre programme sera à la place d'un joueur Magic décidant comment bloquer au combat.

Chaque créature a deux attributs pertinents: la puissance et l'endurance. La puissance d'une créature est la quantité de dégâts qu'elle peut infliger dans un combat, et son endurance est la quantité de dégâts nécessaires pour la détruire. La puissance est toujours d'au moins 0 et la ténacité est toujours d'au moins 1.

Pendant le combat en magie, le joueur dont c'est le tour déclare que certaines de ses créatures attaquent l'adversaire. Ensuite, l'autre joueur, connu sous le nom de joueur défenseur, peut assigner ses créatures comme bloqueurs. Une créature ne peut bloquer qu'une seule créature par combat, mais plusieurs créatures peuvent toutes bloquer la même créature.

Une fois les bloqueurs déclarés, le joueur attaquant décide, pour chaque créature attaquante qui a été bloquée, comment répartir les dégâts (égaux à sa puissance) que cette créature inflige aux créatures qui la bloquent.

Ensuite, les dégâts sont infligés. Chaque créature inflige des blessures égales à sa puissance. Les créatures attaquantes qui ont été bloquées infligent des dégâts comme décrit ci-dessus. Les créatures attaquantes non bloquées infligent des blessures au joueur défenseur. Les créatures bloqueuses infligent des blessures à la créature qu'elles ont bloquée. Les créatures appartenant au joueur défenseur qui n'ont pas bloqué n'infligent pas de dégâts. (Les créatures ne sont pas obligées de bloquer.)

Enfin, toute créature infligeant des blessures égales ou supérieures à son endurance est détruite et retirée du champ de bataille. Toute quantité de dégâts inférieure à l'endurance d'une créature n'a aucun effet.

Voici un exemple de ce processus:

Une créature avec la puissance P et l'endurance T est représentée comme 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.

Le joueur défenseur a 3 buts en combat: détruire les créatures de l'adversaire, préserver ses propres créatures et subir le moins de dégâts possible. De plus, les créatures avec plus de puissance et d'endurance sont plus précieuses.

Pour les combiner en une seule mesure, nous dirons que le score du joueur défenseur d'un combat est égal à la somme des pouvoirs et des forces de leurs créatures survivantes, moins la somme des pouvoirs et des forces des créatures survivantes de leur adversaire, moins un la moitié du montant des dégâts infligés au joueur défenseur. Le joueur défenseur veut maximiser ce score, tandis que le joueur attaquant veut le minimiser.

Dans le combat montré ci-dessus, le score était:

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

Si le joueur défenseur n'avait pas bloqué du tout dans le combat décrit ci-dessus, le score aurait été

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

Le choix optimal pour le joueur défenseur aurait été de bloquer le 2/2avec le 1/1et le 1/4, et de bloquer le 3/3avec le 0/1. S'ils l'avaient fait, seulement 1/4et 3/3ils auraient survécu, et aucun dommage n'aurait été infligé au joueur défenseur, ce qui aurait permis de marquer

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

Votre défi est d'écrire un programme qui produira le choix de blocage optimal pour le joueur défenseur. "Optimal" signifie le choix qui maximise le score, étant donné que l'adversaire répartit les dégâts de la manière qui minimise le score, compte tenu de la façon dont vous avez bloqué.

Il s'agit d'un maximin: le score maximum sur les distributions de dégâts qui minimise le score pour chaque combinaison de blocage.

Entrée: L'entrée consistera en deux listes de 2-tuples, où chaque 2-tuple est de la forme (Puissance, Robustesse). La première liste contiendra les pouvoirs et les forces de chaque créature attaquante (les créatures de votre adversaire). La deuxième liste contiendra les pouvoirs et les forces de chacune de vos créatures.

Les tuples et les listes peuvent être représentés dans n'importe quel format pratique, tel que:

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

Sortie: La sortie consistera en une série de 2 tuples, sous la forme (créature bloquante, créature bloquée) - c'est-à-dire une de vos créatures suivie par une de leurs créatures. Les créatures seront référencées par leur index dans les listes d'entrée. Les index peuvent être indexés 0 ou 1. Encore une fois, tout format pratique. Toute commande est très bien. Par exemple, le scénario de blocage optimal vu ci-dessus, compte tenu de l'entrée ci-dessus, peut être représenté comme suit:

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

Exemples:

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

L'entrée et la sortie peuvent être via STDIN, STDOUT, CLA, entrée / retour de fonction, etc. Des échappatoires standard s'appliquent. C'est le code-golf: le code le plus court en octets gagne.

Pour clarifier la spécification et fournir des idées initiales, cette boîte à pâte fournit une solution de référence en Python. La best_blockfonction est un exemple de solution à ce défi, et l'exécution du programme fournira des entrées et des sorties plus détaillées.

JavaScript (ES7),  354  348 octets

Prend l'entrée comme ([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)`)

Essayez-le en ligne!

Moins golfé et formaté

Ce code est identique à la version golfée, juste sans les mapalias et le eval()wrapping pour plus de lisibilité.

(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
}

Comment?

Initialisation et boucle principale

$0$push$A$

A = a.push([, 0])

Nous allons bloquer cette créature factice au lieu de bloquer aucune créature du tout. Cela permet quelques simplifications dans le code.

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

Construire notre défense

$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()

Optimiser l'attaque

Les décisions des attaquants ne sont pas corrélées les unes aux autres. L'optimum global pour l'attaquant est la somme des optima locaux pour chaque attaquant.

$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)
)                         //

Mise à jour du score du défenseur

Après chaque itération sur un attaquant, nous mettons à jour le score du défenseur avec:

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

La partie gauche soustrait le score de l'attaquant s'il a survécu. La partie droite soustrait la moitié de la ténacité de l'attaquant si l'attaque n'a pas été bloquée du tout, ou ajoute le meilleur score de l'attaquant dans le cas contraire (qui est le pire du point de vue du côté défenseur).