Will I make it out in time?

Question

Inspired by this.

Background

The evil farmer has decided to burn your wheat field down in order to drive up the prices. To ensure total destruction, he has also soaked your field in gasoline. Even more unfortunately, you happened to be walking on the field when it was lit on fire, and you must get out quickly to survive.

Challenge

Given a field containing wheat, fire and your location, determine if you can make it out of the field in time.

A field consists of wheat (here represented by .) and fire (F). Here your location is marked with a O. For example:

...F...F
F.......
........
.F......
....O...
...F....
........
.F....F.

Every second you move to any adjacent cell (but not diagonally), and every fire spreads to every adjacent cell. If you can't move to a cell that will not be on fire, you die. If you make it out of the field, you survive. Let's see what happens in this example:

...F...F
F.......
........
.F......
....O...
...F....
........
.F....F.

..FFF.FF
FF.F...F
FF......
FFF.....
.F.F.O..
..FFF...
.F.F..F.
FFF..FFF

FFFFFFFF
FFFFF.FF
FFFF...F
FFFF....
FF.FF.O.
.FFFFFF.
FFFFFFFF
FFFFFFFF

FFFFFFFF
FFFFFFFF
FFFFF.FF
FFFFF.FF
FFFFFFFO
FFFFFFFF
FFFFFFFF
FFFFFFFF

FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFFO <-- you made it out and survived, barely
FFFFFFFF
FFFFFFFF
FFFFFFFF

Rules

• Your input is the field as a grid. You may choose any input format, including a string with line separators or a 2D array.
  • You may not take as input the locations for fire and/or yourself.
  • You may use any 3 distinct values as wheat, fire and your position, including non-strings for array input.
  • Fields are always at least 1x1 in size, rectangular and contain no invalid characters.
  • Any field will contain exactly one of the value representing your location, and every other position may or may not be fire.
• Your output is one of two distinct values for "you survive" or "you die", as usual in decision-problem.
• Standard code-golf rules apply.

Test cases

Survived

O

....
.O..
....

FFFFF
.....
..O..
.....

FFFF
FFFO
FFFF

.F....
......
......
.F....
..O...
.FF...
.F....
..FF..

...F...F
F.......
........
.F......
....O...
...F....
........
.F....F.

Didn't survive

FFF
FOF
FFF

F.F
.O.
F.F

....F
.....
..O..
.....
F....

.F....F.
........
........
F..O....
........
.....F..

...F...F
F......F
........
.F......
....O...
...F....
........
.F....F.

F..F
.O..
FF..

Answer 1

Snails, 15 bytes

\Oo!{.,fee7.,\F

Try it online!

1 means survival while 0 means death.

Since it is impossible to outrun the fire, it is never useful to try to go around it. The best route is always a straight line. So there are only four possible choices of escape route. To determine if a direction is safe, we check for any F in the "fire cone" pointing in that direction.

Answer 2

Python 2, 283 218 209 208 bytes

lambda F:f(F)&f(F[::-1])
def f(F):l=F.split();w=len(l[0])+1;i=F.index('O');x,y=i/w,i%w;r=range(len(l));return all('F'in''.join(n)for n in[[l[i][x+abs(i-y):]for i in r],[l[i][max(0,y+x-i):i+x-y+1]for i in r]])

Try it online!

Takes input as a newlines separated string, and returns True/False for Dead/Alive

Works by checking each direction(udlr) for Fire in by looking outward:

Example:

Input:

FFFFF
.....
..O..
.....

Fire checks:

Up:       Down:     Left:     Right:

FFFFF               F             F
 ...                ..           ..
  O         O       ..O         O..
           ...      ..           ..

If all directions contain fire you die, otherwise there is an escape.

Edit: Back to taking a string as input, and now only checks for up/right, but also checks the input backwards (giving down/left)

Saved a lot of bytes thanks to Mr. Xcoder and Felipe Nardi Batista

Answer 3

JavaScript, 174 bytes

a=>+(t=>g=a=>t--?g(a.map((l,y)=>l.map((c,x)=>(h=v=>[(a[y-1]||[])[x],(a[y+1]||[])[x],a[y][x+1],a[y][x-1],c].includes(v),!c&&h()?p=1:[2,0,1].find(h))))):p)((p=a+'!').length)(a)

Input format:

• Array of Array of Integers
• 2 for F, 1 for ., 0 for O

Output:

• Truthy value (1) for survive
• Falsy value (NaN) for die

Try It:

f=a=>+(t=>g=a=>t--?g(a.map((l,y)=>l.map((c,x)=>(h=v=>[(a[y-1]||[])[x],(a[y+1]||[])[x],a[y][x+1],a[y][x-1],c].includes(v),!c&&h()?p=1:[2,0,1].find(h))))):p)((p=a+'!').length)(a)
t=s=>f(s.trim().split('\n').map(x=>x.split('').map(n=>({F:2,'.':1,O:0}[n]))))

console.log(t(`
FFFFF
.....
..O..
.....
`))

console.log(t(`
FFFF
FFFO
FFFF
`))

console.log(t(`
.F....
......
......
.F....
..O...
.FF...
.F....
..FF..
`))

console.log(t(`
...F...F
F.......
........
.F......
....O...
...F....
........
.F....F.
`))

console.log(t(`
FFF
FOF
FFF
`))

console.log(t(`
F.F
.O.
F.F
`))

console.log(t(`
....F
.....
..O..
.....
F....
`))

console.log(t(`
.F....F.
........
........
F..O....
........
.....F..
`))

console.log(t(`
...F...F
F......F
........
.F......
....O...
...F....
........
.F....F.
`))

Consider a cellular automaton. There are 3 states for a cell O (reachable by people), F (catch fired), . (nothing just happened). The rule for create next generation is:

for each cell:
  me and my 4 neighborhoods,
    if anyone is `F` then result is `F`,
    otherwise, if anyone is `O` then result is `O`
    otherwise, keep state `.`

Once there is an cell on edge has O state, the people survive. If this not happened in enough amount generation, then the people died.

// check for all neighbors:
h=v=>[(a[y-1]||[])[x],(a[y+1]||[])[x],a[y][x+1],a[y][x-1],c].includes(v)
// if me == 'O' and i'm edge (neighbors contain _undefined_), then survive
!c&&h()?p=1
// Otherwise apply the given rule
:[2,0,1].find(h)

Answer 4

Octave, 71 bytes

@(a)(A=blkdiag(0,a,0))<3||any((bwdist(A>2,'ci')>bwdist(A==2,'ci'))(!A))

Try it online!

or

Verify all test cases!

Input format:

• 2D array of integers
• 1 for ., 2 for O and 3 for F

Output:

• true and false

Explanation:

Explanation:

A=blkdiag(0,a,0)    % add a boundary of 0s around the array
A<3                 % return truthy when there is no fire
bwdist(A>2,'ci')    % city block distance transform of binary map of fire
bwdist(A==2,'ci')   % city block distance transform of binary map of your location
any(...)(!A)        % check if there is at least one element on the boundary of 
                    % the fire distance map has its distance greater than 
                    % that of distance map of your location

Answer 5

Retina, 243 bytes

^.*O(.|¶)*|(.|¶)*O.*$|(.|¶)*(¶O|O¶)(.|¶)*
O
m`^((.)*) (.*¶(?<-2>.)*(?(2)(?!))O)
$1#$3
m`^((.)*O.*¶(?<-2>.)*(?(2)(?!))) 
$1#
T`p`\O`#| ?O ?
+m`^((.)*)[O ](.*¶(?<-2>.)*(?(2)(?!))F)
$1#$3
+m`^((.)*F.*¶(?<-2>.)*(?(2)(?!)))[O ]
$1#
}T`p`F`#|.?F.?
O

Try it online! Requires the background to be spaces rather than .s (or some other regexp-safe character could be used). Explanation:

^.*O(.|¶)*|(.|¶)*O.*$|(.|¶)*(¶O|O¶)(.|¶)*
O

If there is an O on any edge, delete everything else (survival case)

m`^((.)*) (.*¶(?<-2>.)*(?(2)(?!))O)
$1#$3

Place a # in any space above an existing O.

m`^((.)*O.*¶(?<-2>.)*(?(2)(?!))) 
$1#

And a # in any space below an existing O.

T`p`\O`#| ?O ?

Change the #s to Os, and also any space to the left or right of an existing O.

+m`^((.)*)[O ](.*¶(?<-2>.)*(?(2)(?!))F)
$1#$3

Place #s above any existing Fs. These can overwrite Os as well as spaces.

+m`^((.)*F.*¶(?<-2>.)*(?(2)(?!)))[O ]
$1#

Place #s below any existing Fs, also overwriting Os as well as spaces.

}T`p`F`#|.?F.?

Change the #s to Fs, and also any O or space to the left or right of an existing F. Repeat until the Fs have consumed everything.

O

Return 1 for survival, 0 if not.

Answer 6

APL, 81 chars

{e←↓⍉2 4⍴2⌽(⌽,⍉↑s s←⊃s f←⍸¨'OF'=⊂⍵),1,(⌽⍴⍵),1⋄0=∧/+⌿↑(f{+/¨|⍵-⊂⍺}¨⊂e)≤⊂+/¨|e-⊂s}

Answer 7

JavaScript (Node.js), 125 bytes

M=>(g=$=>M.map((X,i)=>X.map((c,j)=>c--?$?c&&(h=(a,b,k)=>k&&h(b,-a,k>>1,g|=a>b|a>-b?0:k))(i-$,j-y,8):c||g([i],y=j):0)))()|g>14

Try it online!

Four sector check. g reused to store 4 flags.

$ is used because it was g<"15" so a function is smaller than the number