Check if all non-zero elements in a matrix are connected

Question

Input:

A matrix containing integers in the range [0 - 9].

Challenge:

Determine if all non-zero elements are connected to each other vertically and/or horizontally.

Output:

A truthy value if all are connected, and a falsy value if there are non-zero elements/groups that aren't connected to other elements/groups.

Test cases:

Test cases are separated by line. Test cases can be found in more convenient formats here (Kudos to Dada).

The following are all connected and should return a truthy value:

0
--- 
0 0
---
1 1 1
0 0 0
---
1 0 0
1 1 1
0 0 1
---
0 0 0 0 0 0
0 0 3 5 1 0
0 1 0 2 0 1
1 1 0 3 1 6
7 2 0 0 3 0
0 8 2 6 2 9
0 0 0 0 0 5

The following are all not-connected, and should return a falsy value:

0 1
1 0
---
1 1 1 0
0 0 0 2
0 0 0 5
---
0 0 5 2
1 2 0 0
5 3 2 1
5 7 3 2
---
1 2 3 0 0 5
1 5 3 0 1 1
9 0 0 4 2 1
9 9 9 0 1 4
0 1 0 1 0 0

This is code-golf, so the shortest submission in each language wins. Explanations are encouraged!

---

Inspired by this challenge.

Answer 1

Retina 0.8.2, 80 77 bytes

T`d`@1
1`1
_
+m`^((.)*)(1|_)( |.*¶(?<-2>.)*(?(2)(?!)))(?!\3)[1_]
$1_$4_
^\D+$

Try it online! Edit: Saved 1 byte thanks to @FryAmTheEggman. Explanation:

T`d`@1

Simplify to an array of @s and 1s.

1`1
_

Change one 1 to a _.

+m`^((.)*)(1|_)( |.*¶(?<-2>.)*(?(2)(?!)))(?!\3)[1_]
$1_$4_

Flood fill from the _ to adjacent 1s.

^\D+$

Test whether there are any 1s left.

Answer 2

MATL, 7 bytes

4&1ZI2<

This gives a matrix containing all ones as truthy output, or a matrix containing at least a zero as falsy. Try it online!

You can also verify truthiness/falsiness adding an if-else branch at the footer; try it too!

Or verify all test cases.

Explanation

4       % Push 4 (defines neighbourhood)
&       % Alternative input/output specification for next function
1ZI     % bwlabeln with 2 input arguments: first is a matrix (implicit input),
        % second is a number (4). Nonzeros in the matrix are interpreted as
        % "active" pixels. The function gives a matrix of the same size
        % containing positive integer labels for the connected components in 
        % the input, considering 4-connectedness
2<      % Is each entry less than 2? (That would mean there is only one
        % connected component). Implicit display

Answer 3

JavaScript (ES6), 136 135 bytes

Returns a boolean.

m=>!/[1-9]/.test((g=(y,x=0)=>1/(n=(m[y]||0)[x])&&!z|n?(m[y++][x]=0,z=n)?g(y,x)&g(--y-1,x)&g(y,x+1)||g(y,x-1):g(m[y]?y:+!++x,x):m)(z=0))

Test cases

let f =

m=>!/[1-9]/.test((g=(y,x=0)=>1/(n=(m[y]||0)[x])&&!z|n?(m[y++][x]=0,z=n)?g(y,x)&g(--y-1,x)&g(y,x+1)||g(y,x-1):g(m[y]?y:+!++x,x):m)(z=0))

console.log('[Truthy]')

console.log(f([
  [0]
]))
console.log(f([
  [0,0]
]))
console.log(f([
  [1,1,1],
  [0,0,0]
]))
console.log(f([
  [1,0,0],
  [1,1,1],
  [0,0,1]
]))
console.log(f([
  [0,0,0,0,0,0],
  [0,0,3,5,1,0],
  [0,1,0,2,0,1],
  [1,1,0,3,1,6],
  [7,2,0,0,3,0],
  [0,8,2,6,2,9],
  [0,0,0,0,0,5]
]))

console.log('[Falsy]')

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

Commented

The recursive function g() first looks for a non-zero cell (as long as the globally-defined flag z is set to 0) and then starts flood-filling from there (as soon as z != 0).

m =>                               // given the input matrix m
  !/[1-9]/.test((                  // test whether there's still a non-zero digit
    g = (y, x = 0) =>              //   after recursive calls to g(), starting at (x=0,y=0):
      1 / (n = (m[y] || 0)[x]) &&  //     n = current cell; if it is defined:
      !z | n ? (                   //       if z is zero or n is non-zero:
          m[y++][x] = 0,           //         we set the current cell to zero
          z = n                    //         we set z to the current cell
        ) ?                        //         if z is non-zero:
          g(y, x) &                //           flood-fill towards bottom
          g(--y - 1, x) &          //           flood-fill towards top
          g(y, x + 1) ||           //           flood-fill towards right
          g(y, x - 1)              //           flood-fill towards left
        :                          //         else:
          g(m[y] ? y : +!++x, x)   //           look for a non-zero cell to start from
      :                            //       else:
        m                          //         return the matrix
    )(z = 0)                       //   initial call to g() + initialization of z
  )                                // end of test()

Answer 4

Wolfram Language (Mathematica), 54 bytes

Saved 2 bytes thanks to user202729.

Max@MorphologicalComponents[#,CornerNeighbors->1<0]<2&

Try it online!

Answer 5

C, 163 bytes

Thanks to @user202729 for saving two bytes!

*A,N,M;g(j){j>=0&j<N*M&&A[j]?A[j]=0,g(j+N),g(j%N?j-1:0),g(j-N),g(++j%N?j:0):0;}f(a,r,c)int*a;{A=a;N=c;M=r;for(c=r=a=0;c<N*M;A[c++]&&++r)A[c]&&!a++&&g(c);return!r;}

Loops through the matrix until it finds the first non-zero element. Then stops looping for a while and recursively sets every non-zero element connected to the found element to zero. Then loops through the rest of the matrix checking if every element is now zero.

Try it online!

Unrolled:

*A, N, M;

g(j)
{
    j>=0 & j<N*M && A[j] ? A[j]=0, g(j+N), g(j%N ? j-1 : 0), g(j-N), g(++j%N ? j : 0) : 0;
}

f(a, r, c) int*a;
{
    A = a;
    N = c;
    M = r;

    for (c=r=a=0; c<N*M; A[c++] && ++r)
        A[c] && !a++ && g(c);

    return !r;
}

Answer 6

APL (Dyalog Unicode), 36 22 bytes^SBCS

~0∊∨.∧⍨⍣≡2>+/|↑∘.-⍨⍸×⎕

Try it online!

thanks @H.PWiz

⍸×⎕ coordinates of non-zero squares

2>+/|↑∘.-⍨ adjacency matrix of the neighbour graph

∨.∧⍨⍣≡ transitive closure

~0∊ is it all 1s?

Answer 7

Perl, 80 79 78 73 70 bytes

Includes +2 for 0a

Give the input matrix without spaces on STDIN (or in fact as rows separated by any kind of whitespace)

perl -0aE 's%.%$".join"",map chop,@F%seg;s%\b}|/%z%;y%w-z,-9%v-~/%?redo:say!/}/'
000000
003510
010201
110316
720030
082629
000005
^D

Easier to read if put in a file:

#!/usr/bin/perl -0a
use 5.10.0;
s%.%$".join"",map chop,@F%seg;s%\b}|/%z%;y%w-z,-9%v-~/%?redo:say!/}/

Answer 8

Java 8, 226 219 bytes

m->{int c=0,l=m[0].length,i=m.length*l;for(;i-->0;)if(m[i/l][i%l]>0){c++;f(m,i/l,i%l);}return c<2;}void f(int[][]m,int x,int y){try{if(m[x][y]>0){m[x][y]=0;f(m,x+1,y);f(m,x,y+1);f(m,x-1,y);f(m,x,y-1);}}finally{return;}}

Explanation:

Try it online.

m->{                   // Method with integer-matrix parameter and boolean return-type
  int c=0,             //  Amount of non-zero islands, starting at 0
      l=m[0].length,   //  Amount of columns in the matrix
      i=m.length*l;    //  Index integer
  for(;i-->0;)         //  Loop over the cells
    if(m[i/l][i%l]>0){ //   If the current cell is not 0:
        c++;           //    Increase the non-zero island counter by 1
        f(m,i/l,i%l);} //    Separate method call to flood-fill the matrix
  return c<2;}         //  Return true if 0 or 1 islands are found, false otherwise

void f(int[][]m,int x,int y){
                       // Separated method with matrix and cell input and no return-type
  try{if(m[x][y]>0){   //  If the current cell is not 0:
    m[x][y]=0;         //   Set it to 0
    f(m,x+1,y);        //   Recursive call south
    f(m,x,y+1);        //   Recursive call east
    f(m,x-1,y);        //   Recursive call north
    f(m,x,y-1);}       //   Recursive call west
  }finally{return;}    //  Catch and swallow any ArrayIndexOutOfBoundsExceptions
                       //  (shorter than manual if-checks)

Answer 9

Jelly, 23 bytes

FJṁa@µ«Ḋoµ€ZUµ4¡ÐLFQL<3

Try it online!

---

Explanation.

The program labels each morphological components with a different numbers, then check if there are less than 3 numbers. (including 0).

Consider a row in the matrix.

«Ḋo   Given [1,2,3,0,3,2,1], return [1,2,3,0,2,1,1].
«     Minimize this list (element-wise) and...
 Ḋ      its dequeue. (remove the first element)
      So min([1,2,3,0,3,2,1],
             [2,3,0,3,2,1]    (deque)
      ) =    [1,2,0,0,2,1,1].
  o   Logical or - if the current value is 0, get the value in the input.
         [1,2,0,0,2,1,1] (value)
      or [1,2,3,0,3,2,1] (input)
      =  [1,2,3,0,2,1,1]

Repeatedly apply this function for all row and columns in the matrix, in all orders, eventually all morphological components will have the same label.

µ«Ḋoµ€ZUµ4¡ÐL  Given a matrix with all distinct elements (except 0),
               label two nonzero numbers the same if and only if they are in
               the same morphological component.
µ«Ḋoµ          Apply the function above...
     €           for €ach row in the matrix.

      Z        Zip, transpose the matrix.
       U       Upend, reverse all rows in the matrix.
               Together, ZU rotates the matrix 90° clockwise.
         4¡    Repeat 4 times. (after rotating 90° 4 times the matrix is in the
               original orientation)
           ÐL  Repeat until fixed.

And finally...

FJṁa@ ... FQL<3   Main link.
F                 Flatten.
 J                Indices. Get `[1,2,3,4,...]`
  ṁ               ṁold (reshape) the array of indices to have the same
                  shape as the input.
   a@             Logical AND, with the order swapped. The zeroes in the input
                  mask out the array of indices.
      ...         Do whatever I described above.
          F       Flatten again.
           Q      uniQue the list.
            L     the list of unique elements have Length...
             <3   less than 3.

Answer 10

Haskell, 132 bytes

 \m->null.snd.until(null.fst)(\(f,e)->partition(\(b,p)->any(==1)[(b-d)^2+(p-q)^2|(d,q)<-f])e).splitAt 1.filter((/=0).(m!)).indices$m

extracted from Solve Hitori Puzzles

indices m lists the (line,cell) locations of the input grid.

filter((/=0).(m!)) filters out all locations with non-zero values.

splitAt 1 partitions off the first member into a singleton list next to a rest list.

any(==1)[(b-d)^2+(p-q)^2|(d,q)<-f] tells if (b,p) touches the frontier f.

\(f,e)->partition(\(b,p)->touches(b,p)f)e splits off touchers from not[yet]touchers.

until(null.fst)advanceFrontier repeats this until the frontier can advance no further.

null.snd looks at the result whether all locations to be reached were indeed reached.

Try it online!

Answer 11

Grime, 37 bytes

C=[,0]&<e/\0{/e\0*0$e|CoF^0oX
e`C|:\0

Prints 1 for match and 0 for no match. Try it online!

Explanation

The nonterminal C matches any nonzero character that is connected to the first nonzero character of the matrix in the English reading order.

C=[,0]&<e/\0{/e\0*0$e|CoF^0oX
C=                             A rectangle R matches C if
  [,0]                         it is a single character other than 0
      &                        and
       <                       it is contained in a rectangle S which matches this pattern:
        e/\0{/e\0*0$e           R is the first nonzero character in the matrix:
        e                        S has an edge of the matrix over its top row,
         /0{/                    below that a rectangle of 0s, below that
             e\0*0$e             a row containing an edge, then any number of 0s,
                                 then R (the unescaped 0), then anything, then an edge.
                    |CoF^0oX    or R is next to another match of C:
                     CoF         S is a match of C (with fixed orientation)
                        ^0       followed by R,
                          oX     possibly rotated by any multiple of 90 dergees.

Some explanation: e matches a rectangle of zero width or height that's part of the edge of the input matrix, and $ is a "wildcard" that matches anything. The expression e/\0{/e\0*0$e can be visualized as follows:

+-e-e-e-e-e-e-e-+
|               |
|      \0{      |
|               |
+-----+-+-------+
e \0* |0|   $   e
+-----+-+-------+

The expression CoX^0oX is actually parsed as ((CoF)0)oX; the oF and oX are postfix operators and concatenation of tokens means horizontal concatenation. The ^ gives juxtaposition a higher precedence then oX, so the rotation is applied to the entire sub-expression. The oF corrects the orientation of C after it is rotated by oX; otherwise it could match the first nonzero coordinate in a rotated English reading order.

e`C|:\0
e`       Match entire input against pattern:
    :    a grid whose cells match
  C      C
   |     or
     \0  literal 0.

This means that all nonzero characters must be connected to the first one. The grid specifier : is technically a postfix operator, but C|:\0 is syntactic sugar for (C|\0):.

Answer 12

Python 2, 211 163 150 bytes

m,w=input()
def f(i):a=m[i];m[i]=0;[f(x)for x in(i+1,i-1,i+w,i-w)if(x>=0==(i/w-x/w)*(i%w-x%w))*a*m[x:]]
f(m.index((filter(abs,m)or[0])[0]))<any(m)<1>q

Try it online!

Output is via exit code. Input is as an 1d list and the width of the matrix.

Answer 13

Perl 5, 131 129 + 2 (-ap) = 133 bytes

push@a,[@F,0]}{push@a,[(0)x@F];$\=1;map{//;for$j(0..$#F){$b+=$a[$'][$j+$_]+$a[$'+$_][$j]for-1,1;$\*=$b||!$a[$'][$j];$b=0}}0..@a-2

Try it online!

Answer 14

JavaScript (Node.js), 115 102 bytes

A=>w=>(A.find(F=(u,i)=>u&&[-w,-1,1,w].map(v=>v*v>1|i%w+v>=0&i%w+v<w&&F(A[v+=i],v),A[i]=0)),!+A.join``)

Try it online!

Receive input as (1d-array)(width). Rewrites all entries in one of the connected non-zero regions with 0 and checks whether the resultant array is a zero matrix. The matrix will become zero if there is zero or one connected non-zero region.

A=>                         // all rows are concatenated into an 1-d array
 w=>                        // width of the original matrix
  (
   A.find(                  // find the first non-zero entry
    F=(                     // helper function
     u,                     // value of the entry
     i                      // index of the entry
    )=>
     u                      // return 0 if value is 0 or out of range
     &&[-w,-1,1,w].map(     // return an array otherwise, and find the neighbors
      v=>                   // for each neighbor
       v*v>1                // if y-coord change: let go anyway
       |i%w+v>=0&i%w+v<w    // if x-coord change: let go only if on the same row
       &&F(A[v+=i],v),      // recurse on the neighbor
      A[i]=0                // before recursing change the current entry to 0
     )
   ),                       // if all entries were 0, no change is made
   !+A.join``               // return whether all entries are now 0
  )                         // if all entries are 0, then +A.join`` == 0

Tip: Use Array.prototype.find if you want to map through an array with a function that the return values can be ignored but to stop once the function is executed.

In this case, I want to map through the array to change only the first connected non-zero region found, but not the other regions (otherwise the array will become a zero matrix no matter what the original input is), so find is used here to save some bytes.