Je suis un grand fan du jeu Creeper World, et surtout de la suite. Vous n'avez pas besoin de savoir comment ce jeu fonctionne pour répondre à la question, je voulais juste mentionner l'origine de ma question.

Dans le jeu, votre objectif est de détruire les émetteurs qui engendrent Creeper, en utilisant une arme connue sous le nom d'annulation.

Les annulateurs peuvent détruire n'importe quel émetteur dans ce rayon:

 eee
eeeee
eenee
eeeee
 eee

Chaque annuleur PEUT cibler plusieurs émetteurs.

Votre objectif

Étant donné un tableau simulant une carte 2D composée de rien et d' émetteurs avec les caractères que vous aimez, pourraient être des espaces et des e ou des nombres - assurez-vous simplement qu'ils sont distinguables, sortez la même carte avec le nombre optimal d'annulateurs n (ou ce que vous souhaitez ) placés, afin que les émetteurs soient détruits avec le moins de nullifiants.

S'il existe plusieurs façons optimales de le faire, il suffit de produire un seul. Si, cependant, la tâche n'est pas résoluble, disons qu'il y a tellement d'émetteurs qu'aucune disposition ne les touchera tous, vous devez sortir quelque chose de différent, null suffira

Règles rapides:

• Entrée: tableau multidimensionnel
• L'entrée contiendra deux caractères, ce qui signifie rien et l' émetteur , incluez ce qui est quoi dans votre réponse
• Sortie: tableau multidimensionnel
• La sortie contiendra trois caractères, ce qui signifie rien , l' émetteur et l' annuleur OU une sortie distincte si l'entrée est insoluble
• Vous ne pouvez remplacer le caractère rien par un nullificateur
• Un annuleur peut toucher plusieurs émetteurs et touchera toujours tous ceux qui sont à portée
• Un nullificateur peut frapper dans la zone spécifiée ci-dessus et frappera toujours tous les émetteurs qu'il peut cibler
• Les réponses les plus courtes en octets gagnent
• échappatoires standard interdites

Exemples

Contribution:

[[ , ,e, , ],
 [ , , , , ],
 [e, , , ,e],
 [ , , , , ],
 [ , ,e, , ]]

Production:

 [[ , ,e, , ],
  [ , , , , ],
  [e, ,n, ,e],
  [ , , , , ],
  [ , ,e, , ]]

Contribution:

[[e,e,e,e,e],
 [e, , , ,e],
 [e, , , ,e],
 [e, , , ,e],
 [e,e,e,e,e]]

Production:

[[e,e,e,e,e],
 [e, ,n, ,e],
 [e, , , ,e],
 [e, ,n, ,e],
 [e,e,e,e,e]]

Contribution:

[[e, , , , , , ,e, ,e, , , ,e, ,e, ,e, ,e],
 [ , ,e, , ,e, , , ,e,e, , , , ,e, , , , ],
 [ , ,e, , , ,e, ,e, ,e, ,e, ,e, ,e, , , ],
 [e, , , ,e, ,e, , , , , , , , , , , ,e, ],
 [e, , ,e, , , , , ,e, ,e, ,e, ,e, , , ,e],
 [ , , ,e, ,e, ,e, , , , , , , , , ,e, , ],
 [ ,e,e, ,e, , , ,e, ,e,e, ,e, ,e, ,e, , ],
 [ , ,e, , , ,e, , , , , , , , ,e,e, ,e, ],
 [ , , ,e, , , , ,e,e, , , , , , , , ,e, ],
 [e, , , , , , ,e, , , ,e,e, ,e, , , , , ],
 [ ,e,e, , ,e, , , , ,e, , , , , , ,e, , ],
 [ , , ,e,e, ,e, ,e, , , ,e,e, ,e, ,e, ,e],
 [e,e, , , , ,e, , , ,e, , , , , , , , , ],
 [ , , ,e, , , , , ,e, , ,e, ,e, ,e, ,e, ],
 [ , , , ,e, ,e, , , , , , , , , , , , , ],
 [e,e, , ,e,e, , ,e, , ,e, ,e, ,e, ,e, ,e],
 [e, ,e, ,e, , ,e,e,e, , ,e, , , ,e, , ,e],
 [ , , , ,e, , , , , ,e, , , ,e, , , , , ],
 [ , ,e, , , ,e, ,e, , , ,e, , , , ,e, , ],
 [ , , ,e, ,e, ,e, , ,e,e, , ,e,e, , ,e, ]]

Sortie (cette sortie est faite à la main et peut ne pas être la sortie optimale):

[[e, , , , , , ,e, ,e, , , ,e, ,e, ,e, ,e],
 [ , ,e, , ,e, , ,n,e,e, , , ,n,e, , , , ],
 [ ,n,e, , ,n,e, ,e, ,e, ,e, ,e, ,e, ,n, ],
 [e, , , ,e, ,e, , , , , , , , , , , ,e, ],
 [e, , ,e, , , , , ,e, ,e, ,e, ,e, , , ,e],
 [ , ,n,e, ,e, ,e, , , ,n, , , , , ,e, , ],
 [ ,e,e, ,e, ,n, ,e, ,e,e, ,e, ,e,n,e, , ],
 [ , ,e, , , ,e, , , , , , , , ,e,e, ,e, ],
 [ , , ,e, , , , ,e,e, , , , , , , , ,e, ],
 [e, ,n, , , , ,e, , , ,e,e, ,e, , , , , ],
 [ ,e,e, , ,e,n, , ,n,e, , , ,n, , ,e,e, ],
 [ , , ,e,e, ,e, ,e, , , ,e,e, ,e, ,e, ,e],
 [e,e, , , , ,e, , , ,e, , , , , , , , , ],
 [ , , ,e, ,n, , , ,e, , ,e, ,e, ,e, ,e, ],
 [ ,n, , ,e, ,e, , , , , , , ,n, , , ,n, ],
 [e,e, , ,e,e, , ,e,n, ,e, ,e, ,e, ,e, ,e],
 [e, ,e, ,e, , ,e,e,e, , ,e, , , ,e, , ,e],
 [ , , , ,e, , , , , ,e, ,n, ,e, , ,n, , ],
 [ , ,e, ,n, ,e, ,e, , , ,e, ,n, , ,e, , ],
 [ , , ,e, ,e, ,e, ,n,e,e, , ,e,e, , ,e, ]]

Contribution:

[[e,e],
 [e,e]]

Production:

null

Python 3 , 558 511 509 octets

from itertools import*
E=enumerate
L=len
def s(s):
 q=[(x,y)for y,r in E(s)for x,k in E(r)if k==w]
 for i in range(1,L(q)):
  for c in combinations(q,i):
   m=[l*1for l in s]
   for p in c:
    m[p[1]][p[0]]=n
    for y,r in E([list(r) for r in' xxx ,xxxxx,xxnxx,xxxxx, xxx '.split(',')]):
     for x,k in E(r):
      o=(p[0]-x+2,p[1]-y+2)
      if k==d and-1<o[0]<L(m[0])and-1<o[1]<L(m)and m[o[1]][o[0]]==e:
       m[p[1]-y+2][p[0]-x+2]=d
   if e not in ','.join([''.join(r)for r in m]):return(m)
print(s(m))

Essayez-le en ligne!

C'est très bouclé, mais je ne connais pas suffisamment Python pour l'optimiser davantage. J'ai appris certaines choses de la réponse des ovules, donc c'était amusant.

L'entrée (modifiée pour faciliter l'écriture des cas de test ) attend '' ou 'e', ​​tandis que la sortie utilise '', 'n' pour nullifier et 'x' pour un émetteur annulé. La fonction prend l'entrée attendue décrite dans la question.

J'ai défini les variables e, w, n et d à l'extérieur car elles pourraient être facilement remplacées par des nombres et, si l'entrée et la sortie étaient également modifiées pour utiliser des nombres, cela imprimerait la même chose. J'ai utilisé des lettres parce qu'elles les rendaient plus lisibles tout en travaillant dessus.

Question amusante, OP! Creeper World est génial et c'était une bonne inspiration pour la question :)

Edit: -47 octets grâce à Erik l'Outgolfer

Python 2 , 267 263 octets

from itertools import*
m=input()
E=enumerate
e=[(x,y)for y,a in E(m)for x,e in E(a)if e]
for n in count():
 for p in combinations(e,n):
	k=[l*1for l in m]
	for x,y in p:k[y][x]=2
	all(e+any(8>(y-Y)**2+(x-X)**2for X,Y in p)for y,a in E(m)for x,e in E(a))>0>exit(k)

Essayez-le en ligne!

0pour l'émetteur, 2pour l'annulateur et 1pour l'espace vide.

Langue Wolfram (Mathematica) , 173 168 octets

t=ToExpression@$ScriptInputString
P=Position
p=t~P~0
q=t~P~2
Print@ReplacePart[t,Thread[p->LinearProgramming[1&/@p,(xBoole[Norm[x-#]^2<6]&/@p)/@q,1&/@q,0,Integers]]]

Essayez-le en ligne!

Résout le plus grand cas de test en 1 seconde .

Programme complet. En fonction, il est plus court, seulement 130 octets .

Utilisez 0pour  , 1pour net 2pour e.

Ce programme peut être utilisé pour convertir à partir du format d'entrée dans le défi.

S'il n'y a pas de solution, il affichera un message d'erreur lpdimcomme celui -ci ou lpsnfcomme ceci .

La version utilisant Outer(bien que plus lisible) est plus longue de 2 octets, malgré le nom court de Outer: Essayez-le en ligne!

Explication.

Notez que cela peut être réduit à un problème de programmation linéaire entier.

Chaque ecellule est fixée à 2, chaque cellule vide est une variable entière, qui peut être 0(vide) ou 1(nullifier). La liste des coordonnées des variables est stockée dans variable p. (le Positions dans tc'est 0)

L'objectif est de minimiser le nombre de nullificateurs utilisés, de sorte que la somme de ces variables entières doit être minimisée. ( 1&/@p, un vecteur composé de tous 1et de longueur égale à pla longueur de, indique la fonction objectif)

Les contraintes sont, pour chaque émetteur ( 2) (leurs positions sont stockées dans q), il doit y avoir au moins un nullificateur dans la plage qui l'entoure, ou pour être précis, avoir une distance euclidienne à lui d'au plus .$\sqrt 6$

Ceci est formulé avec la matrice m= (xBoole[Norm[x-#]^2<6]&/@p)/@q(pour chaque élément dans q, créez une ligne avec les éléments étant 1si la distance au carré ( Norm) à la coordonnée correspondante en pest inférieure à 6) et le vecteur b= 1&/@q.

Après cela ReplacePartet Thread"applique" les valeurs des variables à tet l'imprimer.