Ich bin ein großer Fan des Spiels Creeper World und besonders der Fortsetzung. Sie müssen nicht wissen, wie dieses Spiel funktioniert, um die Frage zu beantworten. Ich wollte nur erwähnen, woher meine Frage stammt.

Im Spiel besteht Ihr Ziel darin, die Emittenten, die Creeper spawnen, mit einer als Nullifier bekannten Waffe zu zerstören.

Nullifier können jeden Emitter in diesem Radius zerstören:

 eee
eeeee
eenee
eeeee
 eee

Jeder Nuller KANN mehrere Emitter ansteuern.

Dein Ziel

Bei einem Array, das eine 2D-Karte simuliert, die aus Nichts und Emittern mit beliebigen Zeichen besteht, könnten Leerzeichen und e oder Zahlen sein - stellen Sie nur sicher, dass sie unterscheidbar sind, und geben Sie dieselbe Karte mit der optimalen Anzahl von Nullifizierern n aus (oder was Sie möchten) ) platziert, so dass die Emitter mit der geringsten Menge an Nullern zerstört werden.

Wenn es mehrere optimale Möglichkeiten gibt, wäre es in Ordnung, nur eine auszugeben. Wenn die Aufgabe jedoch nicht lösbar ist, wenn beispielsweise so viele Emitter vorhanden sind, dass kein Layout alle von ihnen trifft, müssen Sie ein deutlich unterschiedliches Element ausgeben. Null ist ausreichend

Kurzregeln:

• Eingabe: Mehrdimensionales Array
• Die Eingabe enthält zwei Zeichen, dh nichts, und der Sender enthält , was in Ihrer Antwort steht
• Ausgabe: Mehrdimensionales Array
• Die Ausgabe enthält drei Zeichen, dh nichts , Emitter und Nullifier ODER eine unterscheidbare Ausgabe, wenn die Eingabe nicht lösbar ist
• Sie dürfen das Zeichen nothing nur durch einen Nullifier ersetzen
• Ein Nullifier kann mehrere Emitter treffen und trifft immer alle, die sich in Reichweite befinden
• Ein Nuller kann in dem oben angegebenen Bereich treffen und trifft immer alle Emitter, auf die er zielen kann
• Kürzeste Antworten in Bytes gewinnen
• Standardlücken verboten

Beispiele

Eingang:

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

Ausgabe:

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

Eingang:

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

Ausgabe:

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

Eingang:

[[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, ]]

Ausgabe (Diese Ausgabe ist handgemacht und möglicherweise nicht die optimale Ausgabe):

[[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, ]]

Eingang:

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

Ausgabe:

null

Python 3 , 558 511 509 Bytes

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

Probieren Sie es online!

Es ist sehr umständlich, aber ich weiß nicht genug über Python, um es weiter zu optimieren. Aus der Antwort von ovs habe ich einiges gelernt, das hat Spaß gemacht.

Die Eingabe (geändert, um das Schreiben von Testfällen zu vereinfachen ) erwartet '' oder 'e', ​​während die Ausgabe '', 'n' für Nullifier und 'x' für einen nullifizierten Emitter verwendet. Die Funktion übernimmt die erwartete Eingabe, die in der Frage beschrieben wurde.

Ich habe die Variablen e, w, n und d außerhalb gesetzt, da sie leicht durch Zahlen ersetzt werden können. Wenn die Eingabe und Ausgabe so geändert werden, dass auch Zahlen verwendet werden, wird das Gleiche ausgegeben. Ich habe Briefe verwendet, weil sie die Lesbarkeit bei der Arbeit verbessert haben.

Lustige Frage, OP! Creeper World ist großartig und es war eine coole Inspiration für die Frage :)

Edit: -47 Bytes dank Erik dem Outgolfer

Python 2 , 267 263 Bytes

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)

Probieren Sie es online!

0für Emitter, 2für Nullifier und 1für Leerraum.

Wolfram Language (Mathematica) , 173 Bytes

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

Probieren Sie es online!

Löst den größten Testfall in 1 Sekunde .

Volles Programm. Als Funktion ist es kürzer, nur 130 Bytes .

Verwenden Sie 0für  , 1für nund2 für e.

Dieses Programm kann das Eingabeformat in der Challenge konvertiert werden.

Wenn es keine Lösung ist , wird es Fehlermeldung aus, lpdimwie diese , oder lpsnfwie diese .

Die verwendete Version Outer(obwohl besser lesbar) ist 2 Byte länger, trotz des Kurznamens von Outer: Online ausprobieren!

Erläuterung.

Beachten Sie, dass dies zu einem ganzzahligen linearen Programmierproblem führen kann.

Jede eZelle ist fest auf 2 eingestellt, jede leere Zelle ist eine Ganzzahlvariable, die entweder 0(leer) oder 1(nullifier) ​​sein kann. Die Liste der Koordinaten von Variablen wird in Variable gespeichert p. (das Positions tdarin ist 0)

Das Ziel besteht darin, die Anzahl der verwendeten Nullifier zu minimieren, sodass die Summe dieser ganzzahligen Variablen minimiert werden muss. ( 1&/@pEin Vektor besteht aus allen 1und mit einer Länge, die gleich der pLänge ist, gibt die Zielfunktion an.)

Die Einschränkungen sind, dass für jeden Emitter ( 2) (in dem seine Positionen gespeichert sind q) mindestens ein Nuller im Bereich um ihn herum vorhanden sein muss, oder genauer gesagt, ein euklidischer Abstand von höchstens$\sqrt 6$.

Dies wird mit der Matrix m= (xBoole[Norm[x-#]^2<6]&/@p)/@q(für jedes Element in q, erstellen Sie eine Zeile mit Elementen, 1wenn der quadratische Abstand ( Norm) zur entsprechenden Koordinate in pkleiner als 6) und der Vektor b= ist 1&/@q.

Danach ReplacePartund Thread„gilt“ die Variablenwerte tund ausdrucken.