20
\$\begingroup\$

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 , so the shortest submission in each language wins. Explanations are encouraged!


Inspired by this challenge.

\$\endgroup\$
  • \$\begingroup\$ Perhaps the input should contain only ones and zeros (or truthys and falsys), as this is essentially about connected components. \$\endgroup\$ – NikoNyrh Jan 30 '18 at 14:15
  • \$\begingroup\$ Can we take input as an 1d array and a number of columns? \$\endgroup\$ – ovs Jan 30 '18 at 15:05
  • \$\begingroup\$ @ovs sure. I can't see that it should give you any advantages over other people that have already answered. \$\endgroup\$ – Stewie Griffin Jan 30 '18 at 17:06
  • 3
    \$\begingroup\$ Related: how many zeroes do you need to change to make all nonzero elements connected \$\endgroup\$ – dylnan Jan 30 '18 at 17:34
  • \$\begingroup\$ Related: count the number of components (but with diagonal entries adjacent). \$\endgroup\$ – Misha Lavrov Feb 5 '18 at 14:53

14 Answers 14

9
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ @FryAmTheEggman Thanks, and you gave me an idea as to how to save another two bytes too! \$\endgroup\$ – Neil Jan 31 '18 at 9:33
8
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ OP's note: in case there's any doubt: the outputs are perfectly fine and adheres to the linked meta post. \$\endgroup\$ – Stewie Griffin Jan 30 '18 at 21:59
  • \$\begingroup\$ It's blowing my mind that MATL/matlab considers an array of numbers to be truthy IFF it contains no zeros. mathworks.com/help/matlab/ref/if.html (earlier comment deleted) \$\endgroup\$ – Sparr Jan 31 '18 at 1:56
  • \$\begingroup\$ @Sparr (Actually, it is iff it contains no zeros and is not empty.) I was also confused when I learned that any nonempty array is truthy in other languages \$\endgroup\$ – Luis Mendo Jan 31 '18 at 10:13
7
\$\begingroup\$

Wolfram Language (Mathematica), 54 bytes

Saved 2 bytes thanks to user202729.

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

Try it online!

| improve this answer | |
\$\endgroup\$
7
\$\begingroup\$

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()
| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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;
}
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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!/}/
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

APL (Dyalog Unicode), 36 22 bytesSBCS

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

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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.
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Imaginary bounty if you can do it in linear time. I think it's not possible in Jelly, even ¦ takes O(n). \$\endgroup\$ – user202729 Jan 31 '18 at 7:20
  • \$\begingroup\$ (without Python eval, of course) \$\endgroup\$ – user202729 Jan 31 '18 at 7:32
1
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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