13
\$\begingroup\$

I am a big fan of the game Creeper World, and especially the sequel. You don't need to know how this game works to answer the question, I just wanted to mention where my question originated from.

In the game, your objective is to destroy the Emitters that are spawning Creeper, using a weapon known as a nullifier.

Nullifiers can destroy any emitter in this radius:

 eee
eeeee
eenee
eeeee
 eee

Each nullifier CAN target multiple Emitters.

Your objective

Given an array simulating a 2D map consisting of nothing and emitters with whatever characters you like, could be spaces and e or numbers - just be sure they are distinguishable, output the same map with the optimal amount of nullifiers n (or what you would like) placed, so that the emitters are destroyed with the least amount of nullifiers.

If there are multiple optimal ways of doing it, just outputting one would be fine. If, however, the task is not solvable, say there are so many emitters that no layout will ever hit all of them, you must output a distinguishably different something, null will suffice

Quick Rules:

  • Input: multidimensional array
  • Input will contain two characters, meaning nothing and emitter, include what is what in your answer
  • Output: multidimensional array
  • Output will contain three characters, meaning nothing, emitter and nullifier OR a distinguishable output if the input is unsolvable
  • You may only replace the nothing character with a nullifier
  • A nullifier can hit multiple emitters, and will always hit all that are in range
  • A nullifier can hit in the area specified above, and will always hit all emitters that it can target
  • Shortest answers in bytes win
  • standard loopholes forbidden

Examples

Input:

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

Output:

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

Input:

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

Output:

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

Input:

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

Output (This output is hand-made, and might not be the optimal output):

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

Input:

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

Output:

null
Improve this question
\$\endgroup\$
11
  • \$\begingroup\$ Can I use 0, 1 and 2 or similar? \$\endgroup\$
    – DELETE_ME
    Jun 30, 2018 at 6:59
  • \$\begingroup\$ @user202729 Yes, as long as you specify what is what, and keep it consistent, I.E. if an emitter is 1 in input, then likewise it must be 1 in the output \$\endgroup\$
    – Troels M. B. Jensen
    Jun 30, 2018 at 7:02
  • 1
    \$\begingroup\$ I loved Creeper World, it was always satisfying to finally eradicate the final traces of creeper \$\endgroup\$
    – Jo King ♦
    Jun 30, 2018 at 10:54
  • 1
    \$\begingroup\$ @edc65 The whole point of code-golf is to minimize code size without caring about runtime. \$\endgroup\$
    – DELETE_ME
    Jun 30, 2018 at 16:37
  • 2
    \$\begingroup\$ I love creeper world too! \$\endgroup\$
    – orlp
    Jun 30, 2018 at 18:33

3 Answers 3

Reset to default
4
\$\begingroup\$

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

Try it online!

It's very loopy, but I don't know enough about Python to optimize it further. I did learn some things from ovs's answer, so that was fun.

The input (modified to make it easier to write test cases) expects ' ' or 'e', while the output uses ' ', 'n' for nullifier, and 'x' for a nullified emitter. The function takes the expected input that was described in the question.

I set the e, w, n, and d variables outside because they could be easily replaced with numbers and, if the input and output were modified to use numbers as well, it would print out the same thing. I used letters because they made it more readable while working on it.

Fun question, OP! Creeper World is great and it was a cool inspiration for the question :)

Edit: -47 bytes thanks to Erik the Outgolfer

Improve this answer
\$\endgroup\$
3
  • 8
    \$\begingroup\$ Sorry, but it looks like this isn't a seriously competing entry. I recommend deleting it until you have time to optimize it. \$\endgroup\$
    – Erik the Outgolfer
    Jun 30, 2018 at 10:07
  • 2
    \$\begingroup\$ Oops, my bad! Edited to the best of my ability \$\endgroup\$
    – GammaGames
    Jun 30, 2018 at 22:41
  • 1
    \$\begingroup\$ You don't actually need 2 spaces for each level of indentation, 1 is enough. \$\endgroup\$
    – Erik the Outgolfer
    Jun 30, 2018 at 23:38
3
\$\begingroup\$

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)

Try it online!

0 for emitter, 2 for nullifier and 1 for empty space.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 173 168 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]]]

Try it online!

Solves the largest test case in 1 second.

Full program. As a function, it's shorter, only 130 bytes.

Use 0 for  , 1 for n and 2 for e.

This program can be used to convert from the input format in the challenge.

If there are no solution it will print error message lpdim like this, or lpsnf like this.

Version using Outer (although more readable) is 2 bytes longer, despite the short name of Outer: Try it online!

Explanation.

Note that this can be reduced to an integer linear programming problem.

Each e cell is fixed at 2, each empty cell is an integer variable, which can be either 0 (empty) or 1 (nullifier). The list of coordinates of variables are stored in variable p. (the Positions in t that is 0)

The objective is to minimize the number of nullifier used, so the sum of those integer variables must be minimized. (1&/@p, a vector consists of all 1 and with length equal to p's length, indicates the objective function)

The constraints are, for each emitter (2) (their positions are stored in q), there must be at least a nullifier in the range around it, or to be precise, have an Euclidean distance to it of at most \$\sqrt 6\$.

This is formulated with the matrix m = (xBoole[Norm[x-#]^2<6]&/@p)/@q (for each element in q, create a row with elements being 1 if the squared distance (Norm) to the corresponding coordinate in p is less than 6) and the vector b = 1&/@q.

After that ReplacePart and Thread "applies" the variable values to t and print it.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Echo can be used instead of Print but the output contains a preceding >>. \$\endgroup\$
    – DELETE_ME
    Jun 30, 2018 at 7:51
  • \$\begingroup\$ Unfortunately 1^p doesn't work (instead of 1&/@p). \$\endgroup\$
    – DELETE_ME
    Jun 30, 2018 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.