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

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 2

Retina 0.8.2, 80 77 74 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 3

Wolfram Language (Mathematica), 54 bytes

Saved 2 bytes thanks to user202729.

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

Try it online!

Answer 4

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

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 8

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 9

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 10

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 11

Java 8, 226 219 207 205 201 bytes

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

-2 bytes thanks to @ceilingcat.

Try it online.

Explanation:

int[][]M;              // Integer-matrix on class-level, uninitialized
m->{                   // Method with integer-matrix parameter & boolean return
  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(M=m;             //  Set the class-level matrix to the input
      i-->0;)          //  Loop over the cells
    c+=                //   Increase the count by:
       m[i/l][i%l]>0?  //    If the current cell is not 0:
        f(i/l,i%l)     //     Flood-fill the matrix with a separated method
                       //     And increase the count by 1
       :               //    Else:
        0;             //     Leave the count the same
  return c<2;}         //  Return whether 0 or 1 islands are found

// Separated recursive method with cell input & integer return
int f(int x,int y){
  try{m[x][y]*=M[x][y]>0?
                       //  If the current cell is not 0:
           f(m,x,y-1)  //   Recursive call west
          f(m,x-...,y) //   Recursive call north
         f(m,x,y+...)  //   Recursive call east
        f(m,x+...,y)   //   Recursive call south
        -1:1;}         //   Empty the current cell
  }finally{            //  Catch and swallow any ArrayIndexOutOfBoundsExceptions
                       //  (shorter than manual if-checks)
           return 1;}  //  Always result in 1, so we use it to our advantage
                       //  to save bytes here by nesting, instead of having four
                       //  loose calls to each direction)

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

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.

Answer 14

JavaScript (Node.js), 96 bytes

f=(A,P,Q)=>!A.map((B,i)=>B.map((C,j)=>(P-i)**2+(Q-j)**2-1|!C||f(A,i,j,A[i][j]=0,P=0+[P])))|P>'0'

Try it online!

P = 0 if 1 chunk, 00 if 2 chunk, to allow call inside

Answer 15

Uiua, 31 bytes

/×♭⍥'∺'/↥↧.⧻.⊠(≤1/+⌵-).▽♭∶/⊂⇡△.

Try it online!

The same approach as ngn's APL answer.

∧↧1♭⍥'∺'/↥↧.⧻.⊠(≤1/+⌵-).▽♭∶/⊂⇡△.    input: a matrix(n,m)
▽♭∶/⊂⇡△.  collect coordinates of positive numbers:
       ⇡△     coordinates of each position in the matrix (n,m,2)
     /⊂       reduce by join; flatten the first two dimensions
  ♭∶      .    original matrix flattened
▽             keep: for each number n in the matrix, get n copies of its coords
⊠(≤1/+⌵-).  create adjacency matrix:
⊠(      ).    self cross product over the coordinates:
   ≤1/+⌵-      sum of absolute difference is 1 or less?
⍥'∺'/↥↧.⧻.  get transitive closure:
⍥       ⧻.    run <length of the array> times:
  '∺'/↥↧.      self matrix product, using min as product and max as sum
/×♭         test if it is all ones

Answer 16

05AB1E, 42 bytes

Ā©˜ƶ®gäΔ2Fø0δ.ø}2Fø€ü3}®*εεÅsyøÅs«à]˜0KÙg!

Input as a matrix of integers; output as a 05AB1E truthy/falsey value (only \$1\$ is truthy in 05AB1E, so if the result is \$\geq2\$ it's falsey).

Try it online or verify all test cases.

Explanation:

Uses the same flood-fill algorithm I've used in multiple other challenges.

Ā             # Convert each positive integer in the (implicit) input-list to 1s
 ©            # Store this matrix in variable `®` (without popping)
  ˜           # Flatten it to a single list
   ƶ          # Multiply each by its 1-based index to make all values unique
    ®gä       # Convert it back to a matrix with the dimensions of `®`
Δ             # Loop until it no longer changes to flood-fill:
 2Fø0δ.ø}     #  Add a border of 0s around the matrix:
 2F     }     #   Loop 2 times:
   ø          #    Zip/transpose; swapping rows/columns
     δ        #    Map over each row:
    0 .ø      #     Add a leading/trailing 0
 2Fø€ü3}      #  Convert it into overlapping 3x3 blocks: 
 2F    }      #   Loop 2 times again:
   ø          #    Zip/transpose; swapping rows/columns
    €         #    Map over each inner list:
     ü3       #     Convert it to a list of overlapping triplets
 ®*           #  Multiply each 3x3 block by the value in matrix `®`
              #  (so the 0s remain 0s)
 εεÅsyøÅs«à   #  Get the largest value from the horizontal/vertical cross of each 3x3
              #   block:
 εε           #   Nested map over each 3x3 block:
   Ås         #     Pop and push its middle row
     y        #     Push the 3x3 block again
      ø       #     Zip/transpose; swapping rows/columns
       Ås     #     Pop and push its middle rows as well (the middle column)
         «    #     Merge the middle row and column together to a single list
          à   #     Pop and push its maximum
]             # Close the nested maps, flood-fill loop, and outer loop
 ˜            # Flatten the resulting flood-filled matrix
  0K          # Remove all 0s
    Ù         # Uniquify the values of each island
     g        # Pop and push its length (which is 1 if it was a single island)
      !       # Factorial to convert 0 to 1 (and 1 remains 1), since 0 is also truthy
              # (after which the result is output implicitly)

Answer 17

Vyxal 3, 8 bytes

Þoᵛᵛa?∧₌

Try it Online!

Þoᵛᵛa?∧₌­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁣‏⁠‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁣​‎⁠‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏⁠‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌­
Þo        # ‎⁡grid neighbors
  ᵛᵛa     # ‎⁢any truthy?
     ?∧   # ‎⁣Logical and with input
       ₌  # ‎⁤equals input
💎

Created with the help of Luminespire.

Answer 18

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 19

Nekomata + -e, 16 bytes

ᵗ{±1Ĩ$þÐaOđᵒ{≈∑Ƶ

Attempt This Online!

Take input as an 1d array and a number of columns.

Slow for large inputs.

ᵗ{±1Ĩ$þÐaOđᵒ{≈∑Ƶ
ᵗ{                  Check that the following will fail:
  ±                   Sign
   1Ĩ$þÐa             Find the coordinates of 1s
         Ođ           Split into a disjoint union of two subsets
           ᵒ{         For each pair of coordinates from the two subsets:
             ≈∑Ƶ        Check that the distance between them is greater than 1

If I can swap truthy and falsy, ᵗ{ can be removed and the program will be 14 bytes.

Answer 20

Uiua, 7 bytes

≤1⧻⊜∞.±

Try it!

≤1⧻⊜∞.±
       ± # convert nonzeroes to 1
   ⊜∞.  # create an array with an ∞ for each contiguous area of 1s
≤1⧻     # is the length ≤1?