Meine Nullifier optimieren

12

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
Troels MB Jensen
quelle
Kann ich 0, 1und 2oder ähnliches?
user202729
@ user202729 Ja, solange Sie angeben, was was ist, und es konsistent halten, IE, wenn ein Emitter 1 in der Eingabe ist, dann muss es ebenfalls 1 in der Ausgabe sein
Troels MB Jensen
1
Ich habe Creeper World geliebt, es war immer befriedigend, die letzten Spuren von Creeper endgültig zu beseitigen
Jo King,
1
@ edc65 Der Sinn von Code-Golf besteht darin, die Codegröße zu minimieren, ohne sich um die Laufzeit zu kümmern.
user202729
2
Ich liebe Creeper World auch!
Orlp

Antworten:

4

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

GammaGames
quelle
8
Es tut uns leid, aber es sieht so aus, als ob dies kein ernsthaft konkurrierender Eintrag ist. Ich empfehle es zu löschen, bis Sie Zeit haben, es zu optimieren.
Erik der Outgolfer
2
Ups, mein Schlimmes!
Nach
1
Sie brauchen eigentlich nicht 2 Leerzeichen für jede Einrückungsstufe, 1 ist genug.
Erik der Outgolfer
3

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.

ovs
quelle
1

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öchstens6.

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.

user202729
quelle
Echokann anstelle von verwendet werden, Printaber die Ausgabe enthält ein vorangestelltes >>.
user202729
Funktioniert leider 1^pnicht (statt 1&/@p).
user202729