Counting fading

Question

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):

One step of fading algorithm:

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

Example of fading step:

Task:

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

About size of board

Since the figure can only fade, we just have to deal with the board, just one strip padding figure' bounding box.
UPD - About minimal input
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

Answer 1

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!

Answer 2

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).

Answer 3

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.

Answer 4

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.

Answer 5

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)

Answer 6

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.

Answer 7

Wolfram Language (Mathematica), 44 42 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}}.

Answer 8

Retina 0.8.2, 89 bytes

s`1.*
$&_
}`(?<=(.)*)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.

s`1.*
$&_

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.

Answer 9

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

Answer 10

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
        Ƭ   - start with X=C and collect up while distinct applying:
       `    -   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

Answer 11

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

J, alternate, 34 bytes

[:>./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

Answer 12

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!

Answer 13

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.

Answer 14

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.

Answer 15

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.

Answer 16

05AB1E, 28 bytes

Δ2Fø0δ.ø}2Fø€ü3}εεÅsyøÅs«ß]N

Input as a bit-matrix.

Try it online or verify all test cases.

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)

Answer 17

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