24
\$\begingroup\$

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):
enter image description here

One step of fading algorithm:

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

Example of fading step:
enter image description here

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
\$\endgroup\$
13
  • 1
    \$\begingroup\$ Seems like 3 steps are enough for the 4th test case. \$\endgroup\$
    – Arnauld
    Commented Apr 22, 2023 at 18:23
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Arnauld
    Commented Apr 22, 2023 at 18:27
  • 2
    \$\begingroup\$ "Fading" is also known as morphological erosion \$\endgroup\$
    – att
    Commented Apr 22, 2023 at 18:41
  • 3
    \$\begingroup\$ Will the outer edge always be empty? \$\endgroup\$
    – Neil
    Commented Apr 22, 2023 at 19:59
  • 1
    \$\begingroup\$ @JonathanAllan, Yes sure! \$\endgroup\$
    – lesobrod
    Commented Apr 23, 2023 at 3:57

17 Answers 17

9
\$\begingroup\$

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!

\$\endgroup\$
9
\$\begingroup\$

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).
\$\endgroup\$
8
\$\begingroup\$

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.

\$\endgroup\$
0
7
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ I was also thinking about this way. But will it be correct if in the process the whole figure is divided into disconnected parts? \$\endgroup\$
    – lesobrod
    Commented Apr 23, 2023 at 4:54
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – AndrovT
    Commented Apr 23, 2023 at 7:58
7
\$\begingroup\$

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)
\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ With a recursion to keep track of the count, and using Bools: 48 bytes Try it online! \$\endgroup\$
    – MarcMush
    Commented Apr 23, 2023 at 9:57
  • \$\begingroup\$ @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. \$\endgroup\$
    – Kirill L.
    Commented Apr 24, 2023 at 12:55
6
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ It exactly what I expected for Mathematica, thank you! \$\endgroup\$
    – lesobrod
    Commented Apr 23, 2023 at 4:03
5
\$\begingroup\$

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.

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

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
\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
4
  • \$\begingroup\$ Is it any shorter to calculate the taxicab distance between every element (rather than all the ones) to the positions of all the zeros? \$\endgroup\$
    – Neil
    Commented Apr 23, 2023 at 7:51
  • \$\begingroup\$ @Neil I don’t think that would save bytes, but isn’t possible it would give a different answer as well? \$\endgroup\$
    – Jonah
    Commented Apr 23, 2023 at 15:18
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Neil
    Commented Apr 23, 2023 at 16:16
  • \$\begingroup\$ Ah I got you now, good idea though I don't see a way to make it help. \$\endgroup\$
    – Jonah
    Commented Apr 24, 2023 at 4:18
4
\$\begingroup\$

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!

\$\endgroup\$
3
  • \$\begingroup\$ Ajax1234, so False eq answer 0 and True - 1? \$\endgroup\$
    – lesobrod
    Commented Apr 22, 2023 at 18:42
  • 1
    \$\begingroup\$ @lesobrod Correct \$\endgroup\$
    – Ajax1234
    Commented Apr 22, 2023 at 18:42
  • \$\begingroup\$ 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) \$\endgroup\$
    – Mr. Xcoder
    Commented Apr 22, 2023 at 19:39
4
\$\begingroup\$

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.

\$\endgroup\$
0
4
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 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 \$\endgroup\$
    – lesobrod
    Commented Apr 23, 2023 at 4:06
  • \$\begingroup\$ @lesobrod Golly has an Android version, but it does not support Python scipts. \$\endgroup\$
    – alephalpha
    Commented Apr 23, 2023 at 4:36
3
\$\begingroup\$

Charcoal, 29 bytes

W⊙θ⁼⊕⊗×ⅈ⊕ⅈLΦ講Σ↔Eμ⁻ξ§κπⅈM→Iⅈ

Try it online! Link is to verbose version of code. Takes input as a list of points. Explanation:

W⊙θ⁼⊕⊗×ⅈ⊕ⅈLΦ講Σ↔Eμ⁻ξ§κπⅈ

While there exists a point in the set with enough near (by taxicab distance) neighbours to survive another iteration, ...

M→

... increment the iteration count.

Iⅈ

Output the final iteration count.

30 bytes taking input as a list of newline-terminated strings:

WS⊞υιI⌈Eυ⌈Eι⌊Eυ⌊E⌕Aν0⁺↔⁻πμ↔⁻ξκ

Try it online! Link is to verbose version of code. Explanation:

WS⊞υι

Input the strings.

I⌈Eυ⌈Eι⌊Eυ⌊E⌕Aν0⁺↔⁻πμ↔⁻ξκ

Calculate the taxicab distance from each point to the nearest 0, and output the maximum of those.

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

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)
\$\endgroup\$
2
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Apr 25, 2023 at 6:31
  • \$\begingroup\$ Ah, interesting. \$\endgroup\$
    – DLosc
    Commented Apr 25, 2023 at 6:32
1
\$\begingroup\$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.