The evil Ice King has sent his army of penguins

$($

all named Gunther

$)$

$$to attack the Candy Kingdom

$.$

$1$

$$The

Candy Kingdom

$$

s wise ruler, Princess Bubblegum, has devised a defence to ward off the invading penguin

army. Princess Bubblegum

$$

s

$$

Fish

$-$

a

$-$

pult

$$

$$will lob barrels of fish onto the battlefield. This will cover an area

of the battlefield with fish within which the penguins will stop to feed, and then, too full to fight, will retreat

for an afternoon nap.

Suppose we have a

$2$

D integer array representing the battlefield. Each array value represents the number

of penguins currently in a

$1$

$$square meter area of the battlefield. Thus, a

$1$

$0$

$0$

$$by

$1$

$0$

$0$

$$array would represent

a

$1$

$0$

$0$

m by

$1$

$0$

$0$

m battlefield, and each value in the array is the number of penguins in the corresponding

one square meter.

The Fish

$-$

a

$-$

pult can fire barrels of fish of different weights. The weight of the fish barrel determines the size

of the square area

$2$

that will be covered by fish when the barrel explodes on impact. If a barrel weighs n

pounds, then it covers a square area

$2$

n

$+$

$1$

$$meters on each side. Thus, a

$1$

$-$

pound barrel of fish will cover

a

$3$

m square area

$($

corresponding to a

$3$

$$by

$3$

$$slice of the array!

$)$

$.$

Your Task

Your job is to write a part of the targeting software for the Fish

$-$

a

$-$

pult.

Write a function called find

$\_$

target

$\_$

location which has the following parameters:

$$

$$battlefield: a

$2$

D integer array representing the current state of the battlefield

$($

containing the number of penguins at each location, as above

$)$

$$

$$fish

$\_$

weight: an integer representing the weight of the barrel of fish to be fired. The weight also

determines the size of the area covered by fish, as above.

Your function should return the optimal target location

$($

as described below

$)$

$$as a tuple, i

$.$

e

$,$

$$the pair of

array offsets corresponding to the location. If there is more than one location tied for the most number of

penguins, it does not matter which one you return.

Your task is to determine the optimal target location for a given quantity of fish. The optimal location is the

battlefield target location which, if hit with a barrel weighing fish

$\_$

weight pounds, will distract the most

penguins. In other words, if the fish

$\_$

weight is n pounds, then find the center of the

$2$

n

$+$

$1$

$$by

$2$

n

$+$

$1$

$$square

on the battlefield containing the most penguins. This can be done fairly easily using loops and slicing. You

will also find the numpy.sum

$($

$)$

$$function useful.

You need not consider locations where the fish would land outside of the battlefield

$$

$$these cannot be

optimal locations. A target location where the entire detonation area lies within the battlefield grid will

always be as good as or better than a target location where the detonation area falls off the grid because

we know there are zero penguins outside the grid.

If fish

$\_$

weight equals or exceeds either half of the battlefield width

$($

not rounded

$)$

$,$

$$or half of the battlefield

height

$($

not rounded

$)$

$,$

$$then this means that the detonation area is larger than the entire battlefield. Thus,

there are no target locations where the detonation area falls entirely within the battlefield grid. In such a

case, return None. Firing more fish than needed to cover the entire battlefield is a waste of tasty fish!