### Background

Being in a philosophical mood, I remembered one old idea. I think it is suitable for CG. Duplicates are not found, but it's of course just a kind of totalistic cellular automaton or erosion.

Given an infinite board filled with empty (let 0) cells. We create a figure - a finite set of non-empty (let 1) cells. Figure may be with holes, disconnected, random etc. But the bounding box of the figure is finite.

We call the border of a figure a subset of its cells that have at least one empty neighbor (in this model we use 4 neighbors: top, left, right, bottom).

Example of border (blue):

1. Define a figure boundary
2. Eliminate it, replacing by empty cells

Determine how many described steps it takes to completely disappear a given figure.

Since the figure can only fade, we just have to deal with the board, just one strip padding figure' bounding box.
So strictly speaking the minimal board is [[0, 0], [0, 0]] - empty board with no figure. And as mentioned in comments, you may not handling an empty array; sorry that made that point clear just now.

### Input:

Figure in any appropriate form:

• binary array (all board)
• array of strings (too)
• sparse array (list of positions of non-empty cells and dimensions)

### Output:

Non-negative number of steps, totally eliminating a figure.

### Notes:

Of course, the literal passage of the algorithm to fixed point and counting steps is an acceptable solution. But I've got at least two addition ideas:

• Some built-ins of Mathematica ;) But I can't configure it properly (
• Perhaps one can analyze the maximum distances to the border, and get the answer only by a given array

### Test cases:

[[0, 0], [0, 0]] → 0

[[0, 0 ,0], [0, 1, 0], [0, 0, 0]] → 1

[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0],
[0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0],
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
[0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0],
[0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] → 3

Example of string input:
00000000
01111110
01111110
01111110  → 3
01111110
01111110
01111110
00000000

Example of sparse array input (dimensions and non-empty cells):
[16, 16],
[[2, 2], [2, 3], [2, 4], [2, 13], [2, 14], [2, 15], [3, 2], [3, 3], [3, 4], [3, 5], [3, 8], [3, 9], [3, 10], [3, 12], [3, 13], [3, 14], [3, 15], [4, 2], [4, 3], [4, 4], [4, 5], [4, 8], [4, 9], [4, 10], [4, 12], [4, 13], [4, 14], [4, 15], [5, 3], [5, 4], [5, 5], [5, 8], [5, 9], [5, 10], [5, 12], [5, 13], [5, 14], [6, 8], [6, 9], [6, 10], [7, 7], [7, 8], [7, 9], [7, 10], [8, 7], [8, 8], [8, 9], [8, 10], [9, 7], [9, 8], [9, 9], [9, 10], [11, 2], [11, 3], [11, 4], [12, 2], [12, 3], [12, 4], [12, 5], [12, 6], [12, 7], [12, 8], [12, 9], [12, 10], [12, 11], [12, 12], [12, 13], [12, 14], [13, 2], [13, 3], [13, 4], [13, 5], [13, 6], [13, 7], [13, 8], [13, 9], [13, 10], [13, 11], [13, 12], [13, 13], [13, 14], [13, 15], [14, 3], [14, 4], [14, 5], [14, 6], [14, 7], [14, 8], [14, 9], [14, 10], [14, 11], [14, 12], [14, 13], [14, 14], [14, 15], [15, 13], [15, 14], [15, 15]] → 2

• Seems like 3 steps are enough for the 4th test case. Commented Apr 22, 2023 at 18:23
• Suggested test case: [[1, 1 ,1], [1, 0, 1], [1, 1, 1]] → 1. Because in all existing test cases, testing the neighbors without testing the cell itself gives the correct result. Commented Apr 22, 2023 at 18:27
• "Fading" is also known as morphological erosion
– att
Commented Apr 22, 2023 at 18:41
• Will the outer edge always be empty?
– Neil
Commented Apr 22, 2023 at 19:59
• @JonathanAllan, Yes sure! Commented Apr 23, 2023 at 3:57

# Python 2 or 3, 69 bytes

f=lambda c:c>[]and-~f([s for s in c if sum(1==abs(e-s)for e in c)>3])


A recursive function that accepts a list of positions on the Cartesian grid represented as complex numbers and returns the fading count. Returns False for zero as it quacks like zero in Python.

Try it online!

# MATLAB with Image Processing Toolbox, 45 29 bytes

@(x)max(max(bwdist(~x,'ci')))


Anonymous function that inputs a matrix and outputs a number. Try it online! (with Octave).

### Explanation

The code

1. computes the Manhattan (city-block) distance between each value and the nearest zero (bwdist(..., 'ci') applied to x negated);
2. takes the maximum (max, used twice because the image has two dimensions).

# MATLAB with Image Processing toolbox, 59 66 bytes

+7 bytes from @Luis Mendo

I={@(~)0,@(a)1+G(imerode(a,strel('dis',1)))}
G=@(a)I{2-~nnz(a)}(a)


Writing recursive code in MATLAB is surprisingly tricky; I'm using a workaround I found at this link to simulate an if-else statement inside of an anonymous function.

# Vyxal, 15 bytes

k□ẊṠ?Fv¨VεƛṠg;G


Try it Online!

Takes input as a list of coordinates.

Computes the taxicab distance of each point to the border and take the maximum.

k□ẊṠ?Fv¨VεƛṠg;G
k□              # push [[0,1],[1,0],[0,-1],[-1,0]]
Ẋ             # cartesian product with input
Ṡ            # vectorizing sum, this results in the shape inflated by one
?F          # remove all those that are in input, this results in the border of the shape
v¨Vε      # vectorized and right vectorized absolute difference
ƛ  ;  # map:
Ṡ    #   vectorizing sum
g   #   minimum
G # maximum


### 15 byte alternative

ÞT?0ÞIv¨VεƛṠg;G


Takes input as a list of lists.

• I was also thinking about this way. But will it be correct if in the process the whole figure is divided into disconnected parts? Commented Apr 23, 2023 at 4:54
• @lesobrod Each step, the distance of any given point to the border will decrease by one regardless of the shape so this approach works for any shape. Commented Apr 23, 2023 at 7:58

# MATL, 15 bytes

t4&3ZItb-z}x@q


Inputs a binary matrix and outputs a number. Try it online!! Or verify all test cases.

### Explanation

The program erodes the image until it doesn't change.

         % Do...while
t       %   Takes input (implicitly) the first time. Duplicate. Call this (*)
4&3ZI   %   Erode using 4-neighbourhood
t       %   Duplicate
b       %   Bubble up: moves (*) to the top of the stack
-       %   Subtract, element-wise
z       %   Number of non-zeros. Gives 0 if the last erosion didn't modify
%   the image. Call this (**)
}         % Finally (this code is run on loop exit)
x       %   Delete the image
@       %   Push number of current iteration (which is the last one)
q       %   Subtract 1
% End (implicit). A new iteration will be run if the top of stack (**)
% is not 0
% Display stack (implicit)


# Julia 0.6, 62 48 bytes

!m=any(m)&&1+!(conv2(1m,[0 1 0;1 1 1;0 1 0]).>4)


Try it online!

Performs erosion as 2D convolution with given 3x3 kernel.

14 bytes saved by MarcMush by switching to boolean inputs.

• With a recursion to keep track of the count, and using Bools: 48 bytes Try it online! Commented Apr 23, 2023 at 9:57
• @MarcMush that's really impressive, but I always hesitate playing with argument types in Julia, as it's often quite picky about them... But since bool really quacks like an integer, your trick looks good. Commented Apr 24, 2023 at 12:55

# Wolfram Language (Mathematica), 4442 41 bytes

-1 not handling empty input

Max@#/. 1:>1+#0@Erosion[#,CrossMatrix@1]&


Try it online!

Input a binary array of 0,1s.

I don't think there's a shorter way to generate {{0,1,0},{1,1,1},{0,1,0}}.

• It exactly what I expected for Mathematica, thank you! Commented Apr 23, 2023 at 4:03

# Retina 0.8.2, 89 bytes

s1.*
$&_ }(?<=(.)*)1(?=(.)*)(?=.*¶(?<-1>.)*(?(1)^)0|0|(?<=0(?(2)$)(?<-2>.)*¶.+|01))
0
_


Try it online! Takes input as an array of binary strings. Explanation: Loosely based on my original answer to Flood fill by distance.

s1.*
$&_  If there are any 1s remaining, then increase the iteration count. (?<=(.)*)1(?=(.)*)  For each matching 1, keeping track of its position, ... (?=.*¶(?<-1>.)*(?(1)^)0|0|(?<=0(?(2)$)(?<-2>.)*¶.+|01))


...that is either above, to the left, below, or to the right of a 0, using its captured position and .NET balancing groups in order to locate the relevant digit, ...

0


... erode one step.

}


Repeat until there is nothing left to do.

_


Convert the final iteration count to decimal.

# JavaScript (ES11), 88 bytes

Expects a binary matrix.

f=m=>m>(m=m.map((r,y)=>r.map((v,x)=>(g=d=>d+2?m[y+d--%2]?.[x+d%2]&g(d):v)(2))))?1+f(m):0


Attempt This Online!

### Commented

f =                      // f is a recursive function taking:
m =>                     //   m[] = input binary matrix
m > (                    // test whether m[] is lexicographically greater
m =                    // than its updated version
m.map((r, y) =>        // for each row r[] at index y in m[]:
r.map((v, x) =>      //   for each value v at index x in r[]:
( g =              //     g is a helper recursive function taking
d =>             //     a direction d in [-1 .. 2]
d + 2 ?          //     if d is not equal to -2:
m[y + d-- % 2] //       apply dy to y (decrement d afterwards)
?.[x + d % 2]  //       apply dx to x
& g(d)         //       and do a recursive call
:                //     else:
v              //       stop and return v
)(2)               //     initial call to g with d = 2
)                    //   end of inner map()
)                      // end of outer map()
) ?                      // if m[] was updated:
1 +                    //   increment the final result
f(m)                   //   and do a recursive call
:                        // else:
0                      //   stop


# Jelly,   23   11 bytes

ạỊS=5ðƇƬL’


A monadic Link that accepts a list of positions, as complex numbers, of non-empty cells and yields the fading count.

Try it online!

### How?

ạỊS=5ðƇƬL’ - Link: list of coordinates, C
    -   using X as both arguments of:
Ƈ     -     filter keep those c in X for which:
ð      -       the dyadic chain - f(c, X):
ạ           -         (c) absolute difference (X) (vectorises)
Ị          -         insignificant? -- less than or equal to 1?
S         -         sum -- number of neighbours + self
=5       -         equals five?
L  - length
’ - decrement -- as we've counted the empty list that then didn't change


# J, 26 bytes

_1+[:#(#~4=1#.1=|@-/~)^:a:


Try it online!

• Takes input as complex numbers
• Create a distance table between each element and all the others
• For each row, count how many values equal exactly 1 (only true for compass adjacency)
• Remove any whose count is not 4 (ie, remove any non-interior elements)
• Continue this process until a fixed point, keeping a list of intermediate results
• Return the length of this list minus 1

[:>./1<./"1@:#.]|@-"1/&($#:I.@,)-.  Try it online! Input is a binary matrix. We do a single calculation on the input, with no transforms, instead of iterating to simulate the fade: 1. Positions of all the ones 2. Positions of all the zeros 3. Manhattan distance between every element of each of those sets 4. Return the largest • Is it any shorter to calculate the taxicab distance between every element (rather than all the ones) to the positions of all the zeros? – Neil Commented Apr 23, 2023 at 7:51 • @Neil I don’t think that would save bytes, but isn’t possible it would give a different answer as well? Commented Apr 23, 2023 at 15:18 • No, the taxicab distance from any zero to the nearest zero is... zero, so it won't affect the maximum. I only mentioned it because it was easier to iterate over all the elements in Charcoal. – Neil Commented Apr 23, 2023 at 16:16 • Ah I got you now, good idea though I don't see a way to make it help. Commented Apr 24, 2023 at 4:18 # Python3, 177 bytes: E=enumerate def f(b): b=[(x,y)for x,r in E(b)for y,v in E(r)if v] c=0 while b:b=[(x,y)for x,y in b if all((x+X,y+Y)in b for X,Y in[(1,0),(0,1),(0,-1),(-1,0)])];c+=1 return c  Try it online! • Ajax1234, so False eq answer 0 and True - 1? Commented Apr 22, 2023 at 18:42 • @lesobrod Correct Commented Apr 22, 2023 at 18:42 • I think you can remove some redundant parantheses (for instance in the assignment t=(x+X,y+Y) or in the while(b:=...) line), also maybe use inline assignment for t: if(t:=(x+X,y+Y))in c:Q+=[t];c.remove(t) Commented Apr 22, 2023 at 19:39 # Excel (ms365), 122 bytes Assuming: • A range of cells as input; • Cells contain either a 0 or a 1. With Excel 365 one could create a named function which can call itself recursively. So let's create a function called 'z' which refers to: =LAMBDA(x,y,IF(OR(x),z(MAKEARRAY(ROWS(x),COLUMNS(x),LAMBDA(r,c,AND(TOROW(INDEX(x,r-{1,0,0,-1},c-{0,1,-1,0}),3)))),y+1),y))  Now one could call this function through: =z(<Range>,0)  Not sure if I was supposed to add the bytes to actually call the function. # Python script in Golly, 83 bytes from golly import* setrule("4/V") i=0 while not empty(): run(1) i+=1 show(str(i))  Takes input by drawing the figure in Golly. • cool! Do you know some port of Golly for Android? I've got some apps, but they don’t even allow you to change the number of neighbors Commented Apr 23, 2023 at 4:06 • @lesobrod Golly has an Android version, but it does not support Python scipts. Commented Apr 23, 2023 at 4:36 # Charcoal, 29 bytes Ｗ⊙θ⁼⊕⊗×ⅈ⊕ⅈＬΦθ¬›Σ↔Ｅμ⁻ξ§κπⅈＭ→Ｉⅈ  Try it online! Link is to verbose version of code. Takes input as a list of points. Explanation: Ｗ⊙θ⁼⊕⊗×ⅈ⊕ⅈＬΦθ¬›Σ↔Ｅμ⁻ξ§κπⅈ  While there exists a point in the set with enough near (by taxicab distance) neighbours to survive another iteration, ... Ｍ→  ... increment the iteration count. Ｉⅈ  Output the final iteration count. 30 bytes taking input as a list of newline-terminated strings: ＷＳ⊞υιＩ⌈Ｅυ⌈Ｅι⌊Ｅυ⌊Ｅ⌕Ａν0⁺↔⁻πμ↔⁻ξκ  Try it online! Link is to verbose version of code. Explanation: ＷＳ⊞υι  Input the strings. Ｉ⌈Ｅυ⌈Ｅι⌊Ｅυ⌊Ｅ⌕Ａν0⁺↔⁻πμ↔⁻ξκ  Calculate the taxicab distance from each point to the nearest 0, and output the maximum of those. # 05AB1E, 28 bytes Δ2Fø0δ.ø}2Fø€ü3}εεÅsyøÅs«ß]N  Input as a bit-matrix. Explanation: Δ # Loop until the result no longer changes, using the (implicit) input-matrix: 2Fø0δ.ø} # Add a border of 0s around the matrix: 2F } # Loop 2 times: ø # Zip/transpose; swapping rows/columns δ # Map over each inner row-list: 0 .ø # Surround it with both a leading and trailing 0 2Fø€ü3} # Convert the matrix into overlapping 3x3 blocks: 2F } # Loop 2 times again: ø # Zip/transpose; swapping rows/columns € # Map over each inner list: ü3 # Split it into triplets εεÅsyøÅs«ß # Get the minimum of each cross of each 3x3 block: εε # Nested map over the 3x3 blocks: Ås # Get the middle row-list of the current block y # Push the 3x3 block again ø # Zip/transpose; swapping rows/columns Ås # Push its middle column-list of this transposed block « # Merge the middle row and column together to a single list ß # Pop and push its minimum ] # Close the nested map and changes-loop N # Push the last 0-based index of the changes-loop # (which is output implicitly as result)  • @DLosc I'm afraid I still have to do it for every following iteration. The first iteration might go ok, but the iterations after that, it'll need the border of 0s again. :) You can try to remove that part of the code in the test suite and see it'll return the wrong value for all test cases unfortunately. Commented Apr 25, 2023 at 6:31 • Ah, interesting. Commented Apr 25, 2023 at 6:32 # Pip-x, 29 bytes YaWy&UiyFI:5={2>$+(aAD_)MSy}i


Takes input from the command-line as a string representing a Pip list of two-element lists, each of which represents the coordinates of a non-empty cell. Attempt This Online!

### Explanation

Port of Jonathan Allen's Jelly answer.

YaWy&UiyFI:5={2>$+(aAD_)MSy}i Ya ; Yank the input into global variable y Wy ; Loop while y is not empty &Ui ; (and increment i on each loop): yFI: ; Filter y by this function and assign back to y: { } ; (Inside the function, the function argument is a) MSy ; Map this function to y and sum the results: _ ; Each element of y (2-item list) aAD ; Absolute difference (itemwise) with a$+(    )      ;    Add the two elements of the result
2>              ;    1 if less than 2, 0 otherwise
;   This gives the number of cells in cell a's 5-cell
;   neighborhood (including the cell itself) that are
;   nonempty
5=                 ;   Return 1 if that fn's result is 5, 0 otherwise
;  This filters and keeps only the nonempty cells
;  that are surrounded by all nonempty cells
i ; After the loop, print the final value of i
`