30
\$\begingroup\$

Disclaimer: The story told within this question is entirely fictional, and invented solely for the purpose of providing an intro.

I am an evil farmer, and to drive up the price of wheat in my area, I've decided to burn the fields of all the farmers around me. I would really like to see the fields go up in flames (so I can use my evil laugh and rub my hands together with glee), but I also don't want to be caught watching, so I need you to simulate the field being incinerated for me.

Your Task:

Write a program or function that takes as input a field, and returns the stages of it burning until the entire field is ash. A specific section of the field that is on fire is represented by an integer representing the intensity of the flame. A fire starts at "1" and moves on to "2" and then "3", and so on. Once a fire reaches "4", it catches any directly (not diagonally) adjacent areas that are flammable on fire. Once it reaches "8", it burns out on the next iteration, and turns into ash, represented by an "A". When an area has not yet been touched by fire, it is represented by a "0". For example, if the field looks like this:

100
000

Your program should output this:

100
000

200
000

300
000

410
100

520
200

630
300

741
410

852
520

A63
630

A74
741

A85
852

AA6
A63

AA7
A74

AA8
A85

AAA
AA6

AAA
AA7

AAA
AA8

AAA
AAA

If you wish, you may replace the above symbols with any set of symbols you choose, as long as they are consistent and distinct from each other.

Input:

The starting position of the field, in any standard form, such as a newlined-delimated string as above.

Output:

The field in every iteration as it burns, either as an array, or as a string delimited by some character.

Test Cases:

0301
000A
555
 |
 v
0301
000A
555

1412
010A
666

2523
020A
777

3634
030A
888

4745
141A
AAA

5856
252A
AAA

6A67
363A
AAA

7A78
474A
AAA

8A8A
585A
AAA

AAAA
6A6A
AAA

AAAA
7A7A
AAA

AAAA
8A8A
AAA

AAAA
AAAA
AAA

Scoring:

This is , lowest score in bytes wins!

\$\endgroup\$
  • 1
    \$\begingroup\$ How much can the shape vary? Are the non-rectangular parts always "holes" on the right edge, or can there be spaces in the field? \$\endgroup\$ – PurkkaKoodari Aug 8 '17 at 8:08
  • 3
    \$\begingroup\$ So something that hits 4 starts a fire in adjacent squares, but something that starts out at 4 or higher doesn't? That's not very realistic. \$\endgroup\$ – laszlok Aug 8 '17 at 8:13
  • 14
    \$\begingroup\$ "Disclaimer: The story told within this question is entirely fictional, and invented solely for the purpose of providing an intro." -> Starts with "I'm an evil farmer [who wants to do evil stuff]." Very clever. No one will relate the burning fields to you now. \$\endgroup\$ – J_F_B_M Aug 8 '17 at 10:09
  • 3
    \$\begingroup\$ Is it possible for initial ash to separate the field in two, so that part of it will never burn? \$\endgroup\$ – aschepler Aug 8 '17 at 10:58
  • 9
    \$\begingroup\$ If the fire not spreading above 4 is too upsetting, imagine that 1-4 is the fire gaining intensity and 5-A represents it burning out. \$\endgroup\$ – Jeremy Weirich Aug 8 '17 at 12:32

14 Answers 14

1
\$\begingroup\$

APL (Dyalog), 52 bytes*

Assumes ⎕IO←0 which is default on many systems. Takes field using 0 for empty slots, 1 for non-burning field, 2 for new fire, 5 for spreading fire, and 10 for ash. Input must be at least 3×3, which isn't a problem as additional rows and columns may be padded with zeros (spaces in OP's format).

{}{1=c←4⊃r←,⍵:1+4∊r/⍨9⍴⍳2⋄10⌊c+×c}⌺3 3⍣{⍺≡⎕←⍵}

Try it online!

My format makes it hard to check for correctness, so here is a version with added pre- and post-processing to translate from and to OP's format.

⍣{} repeat until:

 the next generation

 is identical to

⎕←⍵ the current generation, outputted

{}⌺3 3 replace each cell with the result of this function applied to its Moore neighborhood:

 ,⍵ ravel (flatten) the argument; gives nine-element list

r← assign to r

4⊃ pick the fourth element; the center, i.e. the original cell value

c← assign to c

1= is one equal to that?

: if so, then:

  ⍳2 first to ɩntegers; 0 1

  9⍴reshape to length nine; 0 1 0 1 0 1 0 1 0

  r/⍨ use that to filter r (this gets just the orthogonal neighbors)

  4∊ is four a member of that? (i.e. will there be a five in the next generation?)

  1+ add one; 1 if not caught fire or 2 if caught fire

 else (i.e the current value is 0 or ≥ 2)

  ×c the signum of c

  c+c plus that (i.e. increase by one if on fire)

  10⌊ minimum of ten and that (as ash doesn't burn on)


* In Dyalog Classic, using ⎕U233A instead of .

\$\endgroup\$
  • \$\begingroup\$ Small, but doesn't deal with board changes. Stuck to a 3x3. \$\endgroup\$ – Suamere Aug 9 '17 at 13:29
  • \$\begingroup\$ @Suamere What? The board doesn't change size, does it? \$\endgroup\$ – Adám Aug 9 '17 at 13:30
  • \$\begingroup\$ Sorry, I wasn't clear. Your answer is awesome, but I am of the understanding that the solution should allow for a variable sized board which may or may not have gaps "on the right". Gaps in the middle are not required to be handled. "On the Right" seems to mean a size-15 board would be built as a 4x4, except the right-most bottom piece is missing. And a size-8 board would be built as a 3x3, except the right-most bottom piece is missing, etc. That's how I read the challenge requirements. Your answer is currently the shortest, but only works with a 3x3. \$\endgroup\$ – Suamere Aug 9 '17 at 13:59
  • \$\begingroup\$ @Suamere OP clearly states that input is 2D. I take input as a numeric matrix and allow "empty" slots anywhere, in the form of zeros. While I require the input to be minimum 3×3 (OP allowed this) I accept input of any larger size. In fact, if you click the here link, you'll see that my second example case is 2×3 with the bottom right cell empty. \$\endgroup\$ – Adám Aug 9 '17 at 14:07
  • \$\begingroup\$ Gotcha. Not sure why, but the Try It Here link has issues (Probably my fault), though your new formatted link works well. E.G.: fire '0A000\n0A0A0\n0A0A0\n000A1' works perfect on the formatted one, but I can't get an equivalent to work with the first link. I'm probably doing something wrong. This doesn't work for me: f ↑(0 0 0)(0 1 0)(0 0 0) \$\endgroup\$ – Suamere Aug 9 '17 at 14:25
15
\$\begingroup\$

Python 3, 232 bytes

def f(j):
 k=[[int(min(9,j[x][y]+(j[x][y]>0)or 3in(lambda k,x,y:[k[i][j]for i,j in[[x-1,y],[x+1,y],[x,y-1],[x,y+1]]if(-1<i<len(k))and(-1<j<len(k[i]))])(j,x,y)))for y in range(len(j[x]))]for x in range(len(j))]
 if k!=j:print(k);f(k)

Try it online!

-3 bytes thanks to officialaimm by merging the other lambda into f (looks messy but saves bytes and that's all we care about)
-8 bytes thanks to Mr. Xoder
-26 bytes thanks to ovs
-6 bytes thanks to ppperry

\$\endgroup\$
  • \$\begingroup\$ How do I add a blank space, like that in the example? \$\endgroup\$ – tuskiomi Aug 9 '17 at 15:51
10
\$\begingroup\$

JavaScript (ES6), 217 210 207 204 193 192 190 bytes

Saved 2 bytes thanks to @Shaggy's suggestion of using 9 as A.

f=F=>[F,...(t=[],y=0,g=x=>(r=F[y])?(x||(t[y]=[]),r[x]+1)?(t[y][x]=r[x]<8?r[x]+(r[x]>0|[r[x-1],r[x+1],F[y-1]&&F[y-1][x],F[y+1]&&F[y+1][x]].includes(3)):9,g(x+1)):g(0,y++):t)(0)+""!=F?f(t):[]]

// test code
test=s=>{
  var test = document.querySelector("#in").value.split`\n`.map(e => Array.from(e).map(e => parseInt(e)));
  var out = f(test);
  document.querySelector("#out").innerHTML = out.map(e => e.map(e => e.join``).join`\n`).join`\n\n`;
};window.addEventListener("load",test);
<textarea id="in" oninput="test()">0301&#10;0009&#10;555</textarea><pre id="out"></pre>

Uses 9 instead of A. Input as a 2D array of integers. Output as an array of such arrays.

\$\endgroup\$
  • \$\begingroup\$ Could you save anything by using 9 instead of A? \$\endgroup\$ – Shaggy Aug 8 '17 at 9:27
7
\$\begingroup\$

Simulating the World (in Emoji), 1407 bytes?

Don't you love using an explorable explanation as a programming language? The downside to this is there's usually not a very well defined program, so in this case, I'm using the JSON it exports. (if you have any better ideas, let me know)

{"meta":{"description":"","draw":1,"fps":1,"play":true},"states":[{"id":0,"icon":"0","name":"","actions":[{"sign":">=","num":1,"stateID":"4","actions":[{"stateID":"1","type":"go_to_state"}],"type":"if_neighbor"}],"description":""},{"id":1,"icon":"1","name":"","description":"","actions":[{"stateID":"2","type":"go_to_state"}]},{"id":2,"icon":"2","name":"","description":"","actions":[{"stateID":"3","type":"go_to_state"}]},{"id":3,"icon":"3","name":"","description":"","actions":[{"stateID":"4","type":"go_to_state"}]},{"id":4,"icon":"4","name":"","description":"","actions":[{"stateID":"5","type":"go_to_state"}]},{"id":5,"icon":"5","name":"","description":"","actions":[{"stateID":"6","type":"go_to_state"}]},{"id":6,"icon":"6","name":"","description":"","actions":[{"stateID":"7","type":"go_to_state"}]},{"id":7,"icon":"7","name":"","description":"","actions":[{"stateID":"8","type":"go_to_state"}]},{"id":8,"icon":"8","name":"","description":"","actions":[{"stateID":"9","type":"go_to_state"}]},{"id":9,"icon":"A","name":"","description":"","actions":[]}],"world":{"update":"simultaneous","neighborhood":"neumann","proportions":[{"stateID":0,"parts":100},{"stateID":1,"parts":0},{"stateID":2,"parts":0},{"stateID":3,"parts":0},{"stateID":4,"parts":0},{"stateID":5,"parts":0},{"stateID":6,"parts":0},{"stateID":7,"parts":0},{"stateID":8,"parts":0},{"stateID":9,"parts":0}],"size":{"width":9,"height":9}}}

Try it here or here:

<iframe width="100%" height="450" src="http://ncase.me/simulating/model/?remote=-Kr2X939XcFwKAunEaMK" frameborder="0"></iframe>

\$\endgroup\$
6
\$\begingroup\$

Retina, 103 96 88 bytes

^
¶
;{:`

T`0d`d
(?<=¶(.)*)0(?=4|.*¶(?<-1>.)*(?(1)_)4|(?<=40|¶(?(1)_)(?<-1>.)*4.*¶.*))
1

Try it online! Uses 9 for ash; this can be changed at a cost of 4 bytes using T`1-8`2-8A. Edit: Saved 6 bytes thanks to @MartinEnder. Explanation:

^
¶

Add a separator so that the outputs don't run into each other. (Also helps when matching below.)

;{:`

Don't print the final state (which is the same as the previous state which has already been printed). Repeat until the pass does not change the state. Print the current state before each pass.

T`0d`d

Advance the intensity of all the fire.

(?<=¶(.)*)0(?=4|.*¶(?<-1>.)*(?(1)_)4|(?<=40|¶(?(1)_)(?<-1>.)*4.*¶.*))
1

Light unlit fields as appropriate. Sub-explanation:

(?<=¶(.)*)

Measure the column number of this unlit field.

0

Match the unlit field.

(?=4

Look for a suitable field to the right.

  |.*¶(?<-1>.)*(?(1)_)4

Look for a suitable field in the same column (using a balancing group) in the line below. Note that if the input could be guaranteed rectangular then this could be simplified to |.*¶(?>(?<-1>.)*)4 for a saving of 3 bytes.

  |(?<=40

Look for a suitable field to the left. (Since we're looking from the right-hand side of the field, we see the unlit field as well.)

      |¶(?(1)_)(?<-1>.)*4.*¶.*))

Look for a suitable field in the same column in the line above. Since this is a lookbehind and therefore a right-to-left match, the balancing group condition has to appear before the columns that have been matched by the balancing group.

\$\endgroup\$
5
\$\begingroup\$

Perl 5, 365 bytes

@a=map{[/./g]}<>;do{say@$_ for@a;say;my@n=();for$r(0..$#a){$l=$#{$a[$r]};for(0..$l){$t=$a[$r][$_];$n[$r][$_]=($q=$n[$r][$_])>$t?$q:$t==9?9:$t?++$t:0;if($t==4){$n[$r-1][$_]||=1if$r&&$_<$#{$a[$r-1]};$n[$r+1][$_]||=1if$r<$#a&&$_<$#{$a[$r+1]};$n[$r][$_-1]||=1if$_;$n[$r][$_+1]||=1if$_<$l}}}$d=0;for$r(0..$#a){$d||=$a[$r][$_]!=$n[$r++][$_]for 0..$#{$a[$r]}}@a=@n}while$d

Try it online!

Uses '9' instead of 'A' to indicated a burned out location.

Explained

@a=map{[/./g]}<>;   # split input into a 2-D array

do{
say@$_ for@a;say;   # output the current state
my@n=();            # holds the next iteration as it's created
for$r(0..$#a){      # loop through rows
  $l=$#{$a[$r]};    # holder for the length of this row
  for(0..$l){
    $t=$a[$r][$_];  # temporary holder for current value
    $n[$r][$_]=($q=$n[$r][$_])>$t?$q:$t==9?9:$t?++$t:0; #update next iteration
    if($t==4){      # ignite the surrounding area if appropriate
      $n[$r-1][$_]||=1if$r&&$_<$#{$a[$r-1]};
      $n[$r+1][$_]||=1if$r<$#a&&$_<$#{$a[$r+1]};
      $n[$r][$_-1]||=1if$_;
      $n[$r][$_+1]||=1if$_<$l
    }
  }
}
$d=0;              # determine if this generation is different than the previous
for$r(0..$#a){$d||=$a[$r][$_]!=$n[$r++][$_]for 0..$#{$a[$r]}}
@a=@n              # replace master with new generation
}while$d
\$\endgroup\$
4
\$\begingroup\$

Haskell, 162 bytes

import Data.List
i x|x<'9'=succ x|1<2=x
f('3':'@':r)="30"++f r
f(x:r)=x:f r
f e=e
a%b=a.b.a.b
g=map(i<$>).(transpose%map(reverse%f))
h x|y<-g x,y/=x=x:h y|1<3=[x]

Try it online! Usage: h takes a field as a list of lines and returns a list of fields. An unburned field is indicated by @ and ash by 9, the different fires are the digits 1 to 8.

  • f manages the spreading of the fire from left to right by replacing all unburned @ fields which are right to a burning 3 field with 0.
  • i increments each digit as long as it is less than 9.
  • g applies f to each line, then reverses the line, applies f again and reverses back. Then the list of of lines is transposed and again on each line and its reverse f is applied.
  • h applies g to the input until it no longer changes and collects the results.
\$\endgroup\$
  • \$\begingroup\$ Fails on input ""@3@1\n@@@9\n555@@@@@@@@@@@@@@@@@@@", as for some reason the long line of @s switches to the top line after the first iteration. Fixing that would be great, thanks! \$\endgroup\$ – Gryphon Aug 8 '17 at 16:30
  • \$\begingroup\$ @Gryphon The displacement is caused by transposing the character matrix. It works if the other lines are brought to the same length with some character which represents neither a field, fire or ash, e.g. _. If this is not acceptable then I'm afraid I'd have to delete the answer, because it's centered around the usage of transpose and I don't see a way to easily fix it without introducing tons of bytes. \$\endgroup\$ – Laikoni Aug 10 '17 at 11:37
4
\$\begingroup\$

C (gcc), 308 305 299 297 295 291 bytes

#define F B[i][v]
m(A,B,k,y,m,U,i,v)char**B;{do{for(i=k=y=0;i<A;puts(""),++i)for(v=0;v<(m=strlen(B[i]));F=(U=F)>48&&F<56?F+1:F>55?65:(i+1<A&&B[i+1][v]==51||v+1<m&&B[i][v+1]==51||v-1>-1&&B[i][v-1]==52||i-1>-1&&B[i-1][v]==52)&&U<49?49:F,putchar(U),k+=U<49||U>64,++y,++v);puts("");}while(k-y);}

This program defines a function which takes two inputs, a pointer to an array of strings preceded by its length, as allowed by this I/O default. Outputs to STDOUT with a trailing newline.

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Runs forever on input 80. \$\endgroup\$ – aschepler Aug 8 '17 at 11:04
  • \$\begingroup\$ @aschepler Sorry! I assumed that all the characters must turn into As, but apparently I assumed wrong. Anyways, thanks for the information. It's fixed now. \$\endgroup\$ – R. Kap Aug 8 '17 at 11:37
  • \$\begingroup\$ -6 bytes! Tio Link \$\endgroup\$ – Giacomo Garabello Aug 8 '17 at 14:35
  • \$\begingroup\$ @GiacomoGarabello I can't believe I forgot about that tactic. Thanks for reminding me! :) \$\endgroup\$ – R. Kap Aug 8 '17 at 18:33
4
\$\begingroup\$

Octave, 72 69 bytes

a=input(''),do++a(a&a<9);a+=imdilate(a==4,~(z=-1:1)|~z')&~a,until a>8

The input is taken as a 2D array of numbers, and empty spots marked with Inf. 'A' has been replaced with 9. Intermediate results (as array of numbers) implicitly printed .

Try it online!

Explanation:

In a loop the function imdilate (morphological image dilation) from the image package is used to simulate fire propagation.

\$\endgroup\$
  • 1
    \$\begingroup\$ This works with boards of all sizes, and even with a bunch of holes. E.G.: [0 Inf 0 0 0;0 Inf 0 Inf 0;0 Inf 0 Inf 0;0 0 0 Inf 1] - Very Nice \$\endgroup\$ – Suamere Aug 9 '17 at 13:28
1
\$\begingroup\$

Python 2, 325 Bytes

def f(x):
 while{i for m in x for i in m}>{9,''}:
    yield x;i=0
    for l in x:
     j=0
     for c in l:
        if 0<c<9:x[i][j]+=1
        j+=1
     i+=1
    i=0
    for l in x:
     j=0
     for c in l:
        if c==0 and{1}&{x[k[1]][k[2]]==4for k in[y for y in[[i,i-1,j],[i<len(x)-1,i+1,j],[j,i,j-1],[j<len(l)-1,i,j+1]]if y[0]]}:x[i][j]+=1
        j+=1
     i+=1
 yield x

f takes the input as a 2D array of integers, and empty spots marked with ''. 'A' has been replaced with 9. The function outputs a generator of all the fields over time in the same format.

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Octave, 212 bytes

function r(f)b=48;f-=b;c=-16;l=f~=-c;d=17;p=@(x)disp(char(x+b));g=@()disp(' ');p(f);g();while~all(any(f(:)==[0 d c],2))m=f>0&l;f(m)+=1;k=conv2(f==4,[0 1 0;1 0 1;0 1 0],'same')&~m&l;f(k)+=1;f(f>8&l)=d;p(f);g();end

To run, specify a character array such as:

f = ['0301','000A','555 '];

... then do:

r(f)

Explanation of the code to follow...

Try it online!

Note: I tried to run this code with tio.run, but I wasn't getting any output. I had to use another service.

\$\endgroup\$
  • \$\begingroup\$ Really just at the moment I want to post an octave answer you answer before me.. \$\endgroup\$ – Michthan Aug 9 '17 at 7:08
1
\$\begingroup\$

PHP, 226 212 210 209 185 177 bytes

for($f=file(m);$f!=$g;print"
")for($g=$f,$y=0;$r=$f[$y++];)for($x=-1;~$c=$r[++$x];$f[$y-1][$x]=$c=="0"?strstr($g[$y-2][$x].$r[$x-1].$f[$y][$x].$r[$x+1],51)/3:min(++$c,9))echo$c;

takes input with a trailing newline from a file named m; 9 for ashes.

Run with -nr or try it online.


first approach: PHP 7.0, 209 bytes

for($f=$g=file(m);trim(join($f),"A
");print"
".join($f=$g))for($y=-1;(a&$c=$r[++$x])||$r=$f[$y-=$x=-1];)for(+$c&&$g[$y][$x]=++$c<9?$c:A,$a=4;$a--;$q=$p)$c-4|($w=&$g[$y+$p=[1,0,-1][$a]])[$q+=$x]!="0"||$w[$q]=1;

takes input with a trailing newline from a file named m.

Run with -nr or try it online.

PHP version notes (for old approach)

  • for PHP older than 7.0, replace everything after $c-4| with $g[$y+$p=[1,0,-1][$a]][$q+=$x]!="0"||$g[$y+$p][$q]=1;
  • for PHP older than 5.5, replace [1,0,-1][$a] with $a%2*~-($a&2)
  • for PHP newer than 7.0, replace a&$c with ""<$c, +$c with 0<$c and $c-4 with $c!=4
\$\endgroup\$
0
\$\begingroup\$

Octave, 419 312 bytes

M=input('') %take a matrix M as input
[a, b]=size(M); %size M for later
while mean(mean(M))!=9 %while the whole matrix M isn't ashes
M=M+round(M.^0.001); %if there is a nonzero int add 1 to it
for i=1:a %loop over all values of M
for j=1:b
if(M(i,j)==4) %if a value of 4 is found, ignite the zeros around it
if(M(max(i-1,1),j)==0) M(i-1,j)++;end
if(M(min(i+1,a),j)==0) M(i+1,j)++;end
if(M(i,max(j-1,1))==0) M(i,j-1)++;end      
if(M(i,min(j+1,b))==0) M(i,j+1)++;end
elseif(M(i,j)==10) M(i,j)--;
end
end
end
M %display the matrix
end

Try it online!

This is my version it works, so now I still need to golf it. I think it can be a lot shorter if I find a way to find the indices of the 4 in a matrix, but I don't know how.
PS: A is a 9 in my code.

\$\endgroup\$
  • 2
    \$\begingroup\$ Instead of endif endfor and endwhile you can write end \$\endgroup\$ – rahnema1 Aug 9 '17 at 7:38
0
\$\begingroup\$

Stencil (-mode), 22 bytes

S≡8:'A'⋄0::S⋄(3∊N)⌈S+s

Try it online!

Just like in the test input, use integers separated by spaces for 0-8, ' ' for blank and 'A' for A. Remember to add trailing blanks too.

\$\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.