38
\$\begingroup\$

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..
Improve this question
\$\endgroup\$
13
  • 2
    \$\begingroup\$ I don't see why someone downvoted \$\endgroup\$ Commented Aug 8, 2017 at 12:35
  • 3
    \$\begingroup\$ To both downvoters, please explain why my challenge is bad. \$\endgroup\$ Commented Aug 8, 2017 at 13:14
  • 6
    \$\begingroup\$ @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. \$\endgroup\$ Commented Aug 8, 2017 at 13:16
  • 2
    \$\begingroup\$ I agree with Pietu1998, I also feel that the restriction is highly appropriate. \$\endgroup\$ Commented Aug 8, 2017 at 13:19
  • 2
    \$\begingroup\$ @LuisMendo If it is possible to escape when the farmer turns, it's always possible for him/her to escape in a straight line. For instance, let's say the farmer is trying to escape to the right of the field. When the farmer moves one space down, some fire will spread downwards; then, the farmer's situation is the same as the initial position (plus more fire). \$\endgroup\$ Commented Aug 8, 2017 at 16:30

7 Answers 7

Reset to default
27
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
7
  • 1
    \$\begingroup\$ O_o Can you provide a testing link? This seems very short. \$\endgroup\$ Commented Aug 8, 2017 at 14:09
  • 10
    \$\begingroup\$ The code is almost saying: "Oy!"... "phew"... \$\endgroup\$ Commented Aug 8, 2017 at 14:24
  • 26
    \$\begingroup\$ Because snails are the perfect choice for, you know, outrunning a fire... \$\endgroup\$ Commented Aug 8, 2017 at 14:25
  • 6
    \$\begingroup\$ @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.." \$\endgroup\$ Commented Aug 8, 2017 at 22:19
  • 3
    \$\begingroup\$ tio.run/##K85LzMwp/v8/xr9SsVpPJy21XE8nxu3/fzc9PTcuPX89PS43IBMA \$\endgroup\$ Commented Aug 8, 2017 at 22:33
13
\$\begingroup\$

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

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

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)
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.

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

APL, 81 chars

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

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

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.