21
\$\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\$
6
  • \$\begingroup\$ Perhaps the input should contain only ones and zeros (or truthys and falsys), as this is essentially about connected components. \$\endgroup\$
    – NikoNyrh
    Commented Jan 30, 2018 at 14:15
  • \$\begingroup\$ Can we take input as an 1d array and a number of columns? \$\endgroup\$
    – ovs
    Commented Jan 30, 2018 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\$ Commented Jan 30, 2018 at 17:06
  • 3
    \$\begingroup\$ Related: how many zeroes do you need to change to make all nonzero elements connected \$\endgroup\$
    – dylnan
    Commented Jan 30, 2018 at 17:34
  • \$\begingroup\$ Related: count the number of components (but with diagonal entries adjacent). \$\endgroup\$ Commented Feb 5, 2018 at 14:53

18 Answers 18

10
\$\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
\$\endgroup\$
3
  • 1
    \$\begingroup\$ OP's note: in case there's any doubt: the outputs are perfectly fine and adheres to the linked meta post. \$\endgroup\$ Commented Jan 30, 2018 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
    Commented Jan 31, 2018 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
    Commented Jan 31, 2018 at 10:13
9
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ @FryAmTheEggman Thanks, and you gave me an idea as to how to save another two bytes too! \$\endgroup\$
    – Neil
    Commented Jan 31, 2018 at 9:33
8
\$\begingroup\$

Wolfram Language (Mathematica), 54 bytes

Saved 2 bytes thanks to user202729.

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

Try it online!

\$\endgroup\$
0
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()
\$\endgroup\$
5
\$\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;
}
\$\endgroup\$
0
5
\$\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?

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

\$\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!/}/
\$\endgroup\$
2
\$\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):.

\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
0
1
\$\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.

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

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

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

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

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

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

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.

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

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