Fire propagation simulator

Question

Suppose we have a matrix like this:

11111
12221
12321
12221
11111

This matrix represents a terrain, and each cell represents a portion of terrain. The number in each cell represents the time the portion of terrain needs to be completely burnt (in minutes, if a measurement unit is needed), according to its combustibility. If a fire starts at any given position (cell), that cell needs to be completely burnt before the fire propagates to the adjacent cells (horizontal and vertical only, not diagonal). So, if a fire is started at the center position, the fire needs:

11111        11111        11111        11011        10001        00000
12221  3 m.  12221  2 m.  12021  1 m.  11011  1 m.  00000  1 m.  00000
12321 -----> 12021 -----> 10001 -----> 00000 -----> 00000 -----> 00000
12221        12221        12021        11011        00000        00000
11111        11111        11111        11011        10001        00000

Explanation:

• Fire starts at [2,2] (0-based), which has a burn time of 3.
• After 3 minutes, [1,2],[2,1],[2,3],[3,2] start to burn.
• After 2 minutes, those cells end burning and fire propagates to all adjacent cells, but [0,2],[2,0],[2,4],[0,4] need only 1 more minute to burn, so
• After 1 minute, those cells are burnt and the cell propagates to their adjacent cells.
• After 1 more minute, the rest of cells from step 3 end burning and fire propagates to their adjacent cells (that are already burnt, so nothing happens).
• After 1 last minute, fire ends burning the whole terrain.

So the solution to that case is 8 minutes. If the fire starts in the top leftmost cell [0,0]:

11111     01111     00111     00011     00001     00000
12221  1  12221  1  02221  1  01221  1  00121  1  00011   1
12321 --> 12321 --> 12321 --> 02321 --> 01321 --> 00321  -->
12221     12221     12221     12221     02221     01221
11111     11111     11111     11111     11111     01111

00000     00000     00000     00000     00000
00000  1  00000  1  00000  1  00000  1  00000
00221 --> 00110 --> 00000 --> 00000 --> 00000
00221     00121     00020     00010     00000
00111     00011     00001     00000     00000

So now the total time is 10 minutes.

The challenge

Given a NxM matrix (N>0, M>0) of integer values that represent the time every cell needs to be completely consumed, write the shortest program/function that takes that matrix and a pair of integers with the position the fire starts in, and returns/prints the time needed for the fire to completely consume the whole terrain.

• Every cell will have a positive (non-zero) burn time. You cannot assume a maximum value for the cells.
• The matrix does not need to be square nor symmetric.
• The matrix can be 0-indexed or 1-indexed, as you like.
• The position can be given as a single parameter with a tuple of integers, two separate parameters of whatever other reasonable format.
• The dimensions of the matrix cannot be specified as input parameters.
• You do not need to output every intermediate step, just the amount of time asked. But I won't complain if the steps are visualized in any way.

Another example:

Fire starts at [1,1] (a '>' represents a minute):

4253   4253   4253   4153   4043   3033   2023    0001   0000
2213 > 2113 > 2013 > 1003 > 0002 > 0001 > 0000 >> 0000 > 0000 
1211   1211   1211   1111   1001   0000   0000    0000   0000

Output: 9

This is code-golf, so may the shortest program for each language win!

Answer 1

Matlab, 235 257 190 182 178 bytes

Input: Matrix A, 1x2 vector p containing the starting coordinates.

function t=F(A,p)
[n,m]=size(A);x=2:n*m;x(mod(x,n)==1)=0;B=diag(x,1)+diag(n+1:n*m,n);k=sub2ind([n m],p(1),p(2));t=max(distances(digraph(bsxfun(@times,((B+B')~=0),A(:))'),k))+A(k)

Explanation:

Instead of simulating the the fire propagation, we can also understand this as a "find the longest shortest path" problem. The matrix is converted into a weighted directed graph. The weights of the paths to a single node correspond to the time to burn said node. E.g. for a matrix

5   7   7   10
5   2   2   10
4   5   2   6

we get the connected graph:

Where node 1 is the upper left matrix element and node 12 the lower right element. Given starting coordinates p, the shortest path to all other nodes is calculated. Then the length of the longest path of those shortest paths + the time to burn the initial node equals to the time to burn the whole matrix.

Ungolfed and commented version with sample starting values:

% some starting point
p = [3 2];
% some random 5x6 starting map, integers between 1:10
A = randi(10,5,6); 

function t=F(A,p)
% dimensions of A
[n,m] = size(A);
% create adjacency matrix
x=2:n*m;
x(mod(x,n)==1)=0;
B = diag(x,1)+diag(n+1:n*m,n);
B = B+B';
B = bsxfun(@times,(B~=0),A(:))';
% make graph object with it
G = digraph(B);
% starting node
k = sub2ind([n m], p(1), p(2));
% calculate the shortest distance to all nodes from starting point
d = distances(G,k);
% the largest smallest distance will burn down last. Add burntime of initial point
t = max(d)+A(k);

Answer 2

JavaScript (ES6), 156 152 146 144 143 bytes

Saved 1 byte thanks to Kevin Cruijssen

A rather naive implementation. Takes input in currying syntax (a)(s), where a is a 2D-array and s is an array of two integers [x, y] representing the 0-based coordinates of the starting position.

a=>s=>(g=t=>(a=a.map((r,y)=>r.map((c,x)=>(z=(h,v)=>(a[y+~~v]||[])[x+h]<1)(-1)|z(1)|z(0,-1)|z(0,1)|x+','+y==s&&c?u=c-1:c),u=-1),~u?g(t+1):t))(0)

Formatted and commented

a => s => (                                // given a and s
  g = t => (                               // g = recursive function with t = time counter
    a = a.map((r, y) =>                    // for each row r of the input array:
      r.map((c, x) =>                      //   for each cell c in this row:
        (                                  //     z = function that takes
          z = (h, v) =>                    //         2 signed offsets h and v and checks
            (a[y + ~~v] || [])[x + h] < 1  //         whether the corresponding cell is 0
        )(-1) | z(1) |                     //     test left/right neighbors
        z(0, -1) | z(0, 1) |               //     test top/bottom neighbors
        x + ',' + y == s                   //     test whether c is the starting cell
        && c ?                             //     if at least one test passes and c != 0:
          u = c - 1                        //       decrement the current cell / update u
        :                                  //     else:
          c                                //       let the current cell unchanged
      ),                                   //   end of r.map()
      u = -1                               //   start with u = -1
    ),                                     // end of a.map() --> assign result to a
    ~u ?                                   // if at least one cell was updated:
      g(t + 1)                             //   increment t and do a recursive call
    :                                      // else:
      t                                    //   stop recursion and return t
  )                                        // end of g() definition
)(0)                                       // initial call to g() with t = 0

Test cases

let f =

a=>s=>(g=t=>(a=a.map((r,y)=>r.map((c,x)=>(z=(h,v)=>(a[y+~~v]||[])[x+h]<1)(-1)|z(1)|z(0,-1)|z(0,1)|x+','+y==s&&c?u=c-1:c),u=-1),~u?g(t+1):t))(0)

console.log(f([
  [1,1,1,1,1],
  [1,2,2,2,1],
  [1,2,3,2,1],
  [1,2,2,2,1],
  [1,1,1,1,1]
])([2, 2]))

console.log(f([
  [1,1,1,1,1],
  [1,2,2,2,1],
  [1,2,3,2,1],
  [1,2,2,2,1],
  [1,1,1,1,1]
])([0, 0]))

console.log(f([
  [4,2,5,3],
  [2,2,1,3],
  [1,2,1,1]
])([1, 1]))

Answer 3

Octave, 67 bytes

function n=F(s,a)n=0;do++n;until~(s-=a|=imdilate(~s,~(z=-1:1)|~z')

Try it online!

To visualize intermediate results you can Try this!

A function that take as input matrix of terrain a and initial coordinate as a matrix of 0&1 with the same size as terrain.

Actually there is no need to endfunction however to run the example in tio it should be added.

Explanation:

Repeatedly apply morphological image dilation on the terrain and subtract the burned areas from it.

Ungolfed answer:

function n = Fire(terrain,burned)
    n = 0;
    mask = [...
            0  1  0
            1  1  1
            0  1  0];
    while true
        n = n + 1;
        propagation = imdilate(~terrain, mask);
        burned = burned | propagation;
        terrain = terrain - burned;
        if all(terrain(:) == 0)
            break;
        end
    end
end

Answer 4

MATL, 26 25 bytes

I really wanted to see some more answers using the golfiest languages around here

`yy)qw(8My~1Y6Z+fhy0>z}@&

Input format is:

• First input is a matrix using ; as row separator.

• Second input is a single number which addresses an entry of the matrix in 1-based column-major order (allowed by the challenge). For example, the column-major coordinate of each entry in a 3×4 matrix is given by

  1  4  7 10
  2  5  8 11
  3  6  9 12
  

  So for instance 1-based coordinates (2,2) correspond to 5.

Try it online! Or verify all test cases.

Explanation

The code maintains a list of entries that are burning. At each iteration, all entries of that list are decremented. When an entry reaches zero, its neighbouring entries are added to the list. To save bytes, entries that reach zero are not removed from the list; instead, they keep "burning" with negative values. The loop is exited when none of the entries have positive values.

See the program running step by step with slightly modified code.

Commented code:

`      % Do...while
  yy   %   Duplicate top two arrays (matrix and array of positions to be decremented)
       %   In the first iteration this implicitly takes the two inputs
  )    %   Reference indexing. This gives the values that need to be decremented
  q    %   Decrement
  w    %   Swap. This brings the array of positions that have been decremented to top
  (    %   Assignment indexing. This writes the decremented values back into their
       %   positions
  8M   %   Push array of positions again
  y    %   Duplicate decremented matrix
  ~    %   Negate. This replaces zeros by 1, and nonzeros by 0
  1Y6  %   Push predefined literal [0 1 0; 1 0 1; 0 1 0] (4-neighbourhood)
  Z+   %   2D convolution, maintaining size
  f    %   Find: gives column-major indices of neighbours of totally burnt entries
  h    %   Concatenate. This updates the array of positions to be decremented
  y    %   Duplicate decremented matrix
  0>   %   This gives 1 for positive entries, and 0 for the rest
  z    %   Number of nonzeros. This is the loop condition (*)
}      % Finally (execute before exiting loop)
  @    %   Push iteration number. This is the output
  &    %   Specify that the final implicit display function will display only the top
       %   of the stack
       % Implicit end. If the top of the stack (*) is not 0 (i.e. there are entries
       % that have not been totally burnt) the loop proceeds with the next iteration.
       % Else the "finally" branch is executed and the loop is exited
       % Implicit display (only top of the stack)

Answer 5

Python 3, 277 266 bytes

def f(m,s):
 p={s};w=len(m);t=0
 while sum(sum(m,[])):
  t+=1;i=0
  for x,y in p:
   try:m[x][y]=max(0,m[x][y]-1)
   except:0
  for v in sum(m,[]):
   if v<1:
    for l in[(1,0),(-1,0),(0,1),(0,-1)]:a,b=max(0,i%w+l[0]),max(0,i//w+l[1]);p.add((a,b))
   i+=1
 print(t)

Try it online!

Defines a function f that takes a 2D matrix and a tuple of points. The first thing the function does is define a set of tuples containing the initial tuple value passed in: p={s}. The function then goes through every tuple of points in p and subtracts one from the matrix m at that point, unless the value is already zero. It then loops through m again finding all points with the value zero and adding the four neighbors of that point to the set p. This is why I chose to use a set, because sets in Python don't allow duplicate values (which would screw up the subtraction a lot). Unfortunately, due to list index wrapping (e.g: list[-1] == list[len(list)-1]) the indices need to be constrained so they do not go negative and add the wrong coordinates to p.

Nothing special, still getting used to golfing. Definitely room for improvement here, I'm going to keep cracking at it.

Answer 6

Python 2, 170 bytes

s,m=input()
t={s}
r=0
while max(sum(m,[]))>0:
 r+=1
 for a,b in t|t:
	try:a<0<x;b<0<x;m[a][b]-=1;t|=m[a][b]==0and{(a+1,b),(a-1,b),(a,b+1),(a,b-1)}or t^t
	except:0
print r

Try it online!

Answer 7

APL (Dyalog), 93 66 57 bytes

{⍵{^/,0≥⍺:0⋄1+x∇⍵∨{∨/,⍵∧⍲/¨2|⍳3 3}⌺3 3⊢0=x←⍺-⍵}(⊂⍺)≡¨⍳⍴⍵}

Try it online! or Visualize it online!

---

This function takes the terrain matrix as right argument and the coordinates (1-based) of first fire as left argument. Returns the number of minutes needed to burn everything.

---

Updates

Finally found a way to golf down the spread function.
*Sigh* it would be so much easier if the world was toroidal.

---

TIO just upgraded to Dyalog 16.0, which means now we have the shiny new stencil operator

Answer 8

Python 2, 268 bytes

def f(m,y,x):t,m[y][x]=m[y][x],0;g(m,t)
def g(m,t):
	n,h,w=map(lambda r:r[:],m),len(m),len(m[0])
	for l in range(h*w):r,c=l/h,l%h;n[r][c]-=m[r][c]and not all(m[r][max(c-1,0):min(c+2,w+1)]+[m[max(r-1,0)][c],m[min(r+1,h-1)][c]])
	if sum(sum(m,[])):g(n,t+1)
	else:print t

Try it online!

Recursively iterate over time steps in which every tile's number is reduced if it is cardinally adjacent to a 0. Very straightforward algorithm that, I believe, can still be golfed for boolean efficiency...

*note: my 'Try it online!' code includes bonus debug logging in the footer. I like to watch the algorithm progress.

Answer 9

Haskell, 138 133 bytes

u#g|all((<=0).snd)g=0|2>1=1+(u:[[(x+1,y),(x-1,y),(x,y-1),(x,y+1)]|((x,y),0)<-n]>>=id)#n where n=d<$>g;d p|elem(fst p)u=pred<$>p|2>1=p

Try it online!

Assumes input is a list of ((x,y),cell). Ungolfed:

type Pos = (Int, Int)

ungolfed :: [Pos] -> [(Pos, Int)] -> Int
ungolfed burning grid
  | all ((<=0).snd) grid = 0 
  | otherwise = 1 + ungolfed (burning ++ newburning) newgrid
 where
  newgrid = map burn grid
  burn (pos,cell) | pos `elem` burning = (pos, cell - 1)
                  | otherwise = (pos, cell)
  newburning = do
    ((x,y),cell) <- newgrid
    guard (cell <= 0)
    [(x+1,y),(x-1,y),(x,y-1),(x,y+1)]