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 .
  • Standard 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..
  • 2
    I don't see why someone downvoted – Oliver Ni Aug 8 '17 at 12:35
  • 3
    To both downvoters, please explain why my challenge is bad. – Pietu1998 Aug 8 '17 at 13:14
  • 1
    Why is there this restriction: "You may not take as input the locations for fire and/or yourself."? It just adds task to find O and Fs in input – Dead Possum Aug 8 '17 at 13:14
  • 5
    @DeadPossum Because I feel like it would simplify the challenge too much and make it a bit too broad. Feel free to disagree, though; if others agree with you I might change the restriction. – Pietu1998 Aug 8 '17 at 13:16
  • 2
    I agree with Pietu1998, I also feel that the restriction is highly appropriate. – Mr. Xcoder Aug 8 '17 at 13:19
up vote 28 down vote accepted

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.

  • 1
    O_o Can you provide a testing link? This seems very short. – Mr. Xcoder Aug 8 '17 at 14:09
  • 10
    The code is almost saying: "Oy!"... "phew"... – Magic Octopus Urn Aug 8 '17 at 14:24
  • 26
    Because snails are the perfect choice for, you know, outrunning a fire... – Timtech Aug 8 '17 at 14:25
  • 6
    @feersum In the "try it online" link, I tried the following 3-line wheat field, which should be death, but the program thinks you can survive it: "F..F", ".O..", "FF.." – Xantix Aug 8 '17 at 22:19
  • 3

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

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)

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

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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