Connected bits
+1
−0
Indicate whether the 1s and 0s in an 8 by 8 grid are connected.
The grid
- Connectedness is by orthogonal adjacency (up, down, left, right).
- Diagonal adjacency does not count.
- If all of the
1s can be reached by orthogonal steps from any other1, stepping on only1s, then the set of1s is connected. - If all of the
0s can be reached by orthogonal steps from any other0, stepping on only0s, then the set of0s is connected. - The grid does not wrap toroidally. The left hand edge is not adjacent to the right hand edge, and the top edge is not adjacent to the bottom edge.
Input
- An 8 by 8 grid of
1s and0s. This can be in any format that does not contribute to solving the challenge. For example:- 8 strings of 8 characters.
- A string of 64 characters.
- A string of newline separated strings of 8 characters.
- A sequence of 8 8 bit values.
- A 64 bit value (such as an unsigned integer).
Output
- An indication of whether all of the like values are connected. That is, all of the
1s are connected and all of the0s are connected. - This could be one of 2 distinct values to indicate true or false, or any truthy or falsy value if your language has this concept.
Examples
Connected
00000000
00000000
01111000
01111000
01111000
00000000
00000000
00000000
00000000
1s not connected
11111111
00000000
00000000
00000000
00000000
00000000
00000000
11111111
0s not connected
Diagonal connection does not count.
11111111
11001111
11001111
11110011
11110011
11111111
11111111
11111111
Neither connected
00000001
00000010
00000100
00001000
00010000
00100000
01000000
10000000
Trivially connected
The empty set is considered to be connected, so if there are no 1s, the set of 1s is connected. Similarly for 0s.
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
Test cases
Each test case is in the format input : output.
Unsigned integer input
0 : true
18446744073709551615 : true
1 : true
257 : true
258 : false
33909453996687360 : true
18374686479671623935 : false
18433180446528372735 : false
72624976668147840 : false
18375105691386724735 : true
67178694441613952 : true
18375101293340213631 : false
Binary input
0000000000000000000000000000000000000000000000000000000000000000 : true
1111111111111111111111111111111111111111111111111111111111111111 : true
0000000000000000000000000000000000000000000000000000000000000001 : true
0000000000000000000000000000000000000000000000000000000100000001 : true
0000000000000000000000000000000000000000000000000000000100000010 : false
0000000001111000011110000111100000000000000000000000000000000000 : true
1111111100000000000000000000000000000000000000000000000011111111 : false
1111111111001111110011111111001111110011111111111111111111111111 : false
0000000100000010000001000000100000010000001000000100000010000000 : false
1111111100000001011111010100010101010101010111010100000101111111 : true
0000000011101110101010101010101010101010101010101011101010000000 : true
1111111100000001011110010100010101010101010111010100000101111111 : false
Scoring
This is a code golf challenge. Your score is the number of bytes in your code. Lowest score for each language wins.
Explanations are optional, but I'm more likely to upvote answers that have one.
2 answers
+1
−0
Perl, 148 bytes
Pass 64 character string of 1s and 0s on stdin.
Zero exit means success; non-zero means failure.
perl -ne'@g=/./g;sub c{my($i)=@_;$i<0||$i>63||$g[$i]-$v||($g[$i]=2)+c($i+8)+c($i+1)+c($i-8)+c($i-1)}c index$_,0;$v=1;c index$_,1;exit 64-grep/2/,@g'
Comments:
perl -ne'
# load input string into array of individual characters
@g=/./g;
# recursive connectivity search
# mark each connected element found
sub c{
my($i)=@_;
$i<0||$i>63 # out of bounds?
|| $g[$i]-$v # incorrect value?
|| ($g[$i]=2) # mark value
+ c($i+8) # recurse
+ c($i+1)
+ c($i-8)
+ c($i-1)
}
c index$_,0; # search for connected 0s
$v=1; c index$_,1; # search for connected 1s
exit 64-grep/2/,@g # zero iff 64 values were marked
'
0 comment threads
+1
−0
AWK, 127 bytes
Pass 64 character string of 1s and 0s on stdin.
Zero exit means success; non-zero means failure.
awk 'function n(i){i<1||i>64||c-$i||($i=2)+n(i+8)+n(i+1)+n(i-8)+n(i-1)}{n(index($0,0));c=1;n(index($0,1));exit/[01]/}' FS= OFS=
Comments:
awk '
function n(i){
i<1||i>64 || # out of bounds?
c-$i || # incorrect value?
($i=2)+\
n(i+8)+n(i+1)+n(i-8)+n(i-1) # mark(replace) then recurse
}
{
n(index($0,0)); # find connected 0s
c=1; n(index($0,1)); # find connected 1s
exit /[01]/ # zero iff no 0s or 1s left
}
' FS= OFS=
- Same basic logic as my Perl answer
-
FS=(non-standard but widely implemented) splits line into fields containing individual characters -
OFS=- assigning to a field cause line to be rewritten with fields separated byOFS; clearing it means result is unchanged (affectsindex)
0 comment threads
0 comment threads