7
\$\begingroup\$

Inspired by this and this which was inspired by the first question.

I've set my farmers' fields on fire, but unfortunately they saw me do it! If I don't deal with this situation they could report me and then I'd get arrested! So, that shouldn't be too hard. All I have to do is kill them with fire!

The field will be an m*n grid with odd m and n where both are one greater than a multiple of 4. The farmer starts out in the middle of the field. Each "tick", the farmer can move to an adjacent square (edge or corner) and any space on fire will ignite every grid adjacent to it in a 3x3 space (edge or corner again).

Note: fires and farmers can move diagonally.

The grid will be given as some 2D array of 3 unique values: Fire, .Wheat, and Human (Farmer). For example:

F...F
F...F
FFHFF
F...F
F...F

the farmer is doomed to DIE! >:-D

It would be easy if I could just light a fire right beside the farmer and set him on fire. However, he knows I am in the field with him and he has a gun. If he sees me, I'm dead. So, I can't light the fire within half of the distance between him and the edge, of him. Essentially, if you floordiv the width of the grid by 4, I must be within that many spaces from the edge, and same with the height.

I am immune to fire so I don't have to worry about getting myself out.

The question is:

Given a field with wheat, a farmer in the center, and potentially existing fires around the field, how many fires do I need to light to guarantee I can kill the farmer?

Test Cases

These test cases have input represented by a F . H grid and output as a single integer. You may take input in any other reasonable format and output a single integer.

FFFFF
F...F
F.H.F => 0, the farmer is doomed to die in 2 ticks anyway
F...F
FFFFF

FFFFF
F....
F....
F....
F.H.. -> 1 (just light a fire on the far right side of him)
F....
F....
F....
FFFFF

.....
.....
..H.. -> 4 (to ensure his demise, you would need to light 4 points around the perimeter (with rotational symmetry). Any 4 will do.
.....
.....

Rules

  • Standard Loopholes apply
  • You can take an array of 2 values if you would like, where you infer the farmer's position from the size (since the farmer will always be in the center)
\$\endgroup\$
  • \$\begingroup\$ tl;dr, +1 for title \$\endgroup\$ – FantaC Feb 4 '18 at 6:07
2
\$\begingroup\$

Python 3, 672 bytes

e=enumerate;H='H';F='F'
def f(m):
	q=m[0];h=len(m);w=len(q);o=0;g=lambda m,c:{(k,l)for i,r in e(m)for j,v in e(r)for k in range(i-1,i+2)for l in range(j-1,j+2)if v==c and k>=0and k<h and l>=0and l<w};n=lambda m,c,d:[[c if(k,l)in g(m,c)-g(m,d)else m[k][l]for(l,v)in e(r)]for(k,r)in e(m)];s=lambda m:H in[q]+[m[h-1]]+[r[0]for r in m]+[r[w-1]for r in m];l=lambda m:all(H not in r for r in m)
	while 1:
		a=m
		while not(s(a)or l(a)):a=n(n(a,H,F),F,1)
		if l(a):return o
		else:o+=1;z(m,a,h,w)
def z(m,a,h,w):
	for i in(0,h-1):
		for j,v in e(a[i]):
			if v==H:m[i][j+(h-1)//2]=F;return
	for j in(0,w-1):
		for i,v in e(r[j] for r in a):
			if v==H:m[i+(w-1)//2][j]='F';return

Try it online!

It's very long (I've done my best to golf it), and the solution is not optimal. Here is the general idea:

  1. First, let's see if the farmer burns in the original situation. The matrix a is filled with Fs when the fire grows and with Hs if the farmer can reach a position (a=n(n(a,H,F),F,1)).

  2. If the farmer escapes (s(a)), look a the border of a. There must be at least a H. It takes (h-1)/2 ticks to reach the top or the bottom, and (w-1)/2 ticks to reach the left or right border. As soon as we find a H on the top, we put a fire at (h-1)/2 cases on its left. In (h-1)/2 ticks, an F will be there and it may also "burn" other Hs. The same applies for the left and right borders.

The solution is not optimal because:

  • there are some edge cases, in particular when a fire will burn two borders of the field.
  • considering top and bottom borders before right and left borders is not necessarily the best solution
  • going from left to right and top to bottom to find a H is not necessarily the best solution.
\$\endgroup\$

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.