| Bytes | Lang | Time | Link |
|---|---|---|---|
| 007 | Uiua | 240818T005943Z | nyxbird |
| 016 | Nekomata + e | 231023T034858Z | alephalp |
| 008 | Vyxal 3 | 240221T134828Z | pacman25 |
| 042 | 05AB1E | 231020T110820Z | Kevin Cr |
| 031 | Uiua | 231019T082831Z | Bubbler |
| 074 | Retina 0.8.2 | 180130T110104Z | Neil |
| 096 | JavaScript Node.js | 221223T170545Z | l4m2 |
| 201 | Java 8 | 180130T145748Z | Kevin Cr |
| 102 | JavaScript Node.js | 200205T121838Z | Shieru A |
| 022 | APL Dyalog Unicode | 180130T204417Z | ngn |
| 037 | Grime | 180205T144801Z | Zgarb |
| 132 | Haskell | 180204T083056Z | Roman Cz |
| 150 | Python 2 | 180130T163655Z | ovs |
| 070 | Perl | 180130T212433Z | Ton Hosp |
| 023 | Jelly | 180131T063305Z | DELETE_M |
| 007 | MATL | 180130T112144Z | Luis Men |
| 135 | JavaScript ES6 | 180130T115420Z | Arnauld |
| nan | Perl 5 | 180130T175401Z | Xcali |
| 163 | C | 180130T123839Z | Steadybo |
| 054 | Wolfram Language Mathematica | 180130T121550Z | alephalp |
Uiua, 7 bytes
≤1⧻⊜∞.±
≤1⧻⊜∞.±
± # convert nonzeroes to 1
⊜∞. # create an array with an ∞ for each contiguous area of 1s
≤1⧻ # is the length ≤1?
Nekomata + -e, 16 bytes
ᵗ{±1Ĩ$þÐaOđᵒ{≈∑Ƶ
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.
Vyxal 3, 8 bytes
Þoᵛᵛa?∧₌
Þoᵛᵛa?∧₌
Þo # grid neighbors
ᵛᵛa # any truthy?
?∧ # Logical and with input
₌ # equals input
💎
Created with the help of Luminespire.
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)
Uiua, 31 bytes
/×♭⍥'∺'/↥↧.⧻.⊠(≤1/+⌵-).▽♭∶/⊂⇡△.
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
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.
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'
P = 0 if 1 chunk, 00 if 2 chunk, to allow call inside
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.
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)
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``)
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.findif 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
findis used here to save some bytes.
APL (Dyalog Unicode), 36 22 bytesSBCS
~0∊∨.∧⍨⍣≡2>+/|↑∘.-⍨⍸×⎕
thanks @H.PWiz
⍸×⎕ coordinates of non-zero squares
2>+/|↑∘.-⍨ adjacency matrix of the neighbour graph
∨.∧⍨⍣≡ transitive closure
~0∊ is it all 1s?
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):.
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.
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
Output is via exit code. Input is as an 1d list and the width of the matrix.
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!/}/
Jelly, 23 bytes
FJṁa@µ«Ḋoµ€ZUµ4¡ÐLFQL<3
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.
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!
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
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()
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
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.
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;
}
Wolfram Language (Mathematica), 54 bytes
Saved 2 bytes thanks to user202729.
Max@MorphologicalComponents[#,CornerNeighbors->1<0]<2&