Contiguous Block Count

5

1

Count the number of contiguous blocks within a given 3D input.

Input

The input will consist of one or more rectangles of characters separated by blank lines. Each rectangle represents a cross section of the 3D space. The characters used will be 0, representing empty space, and 1 representing a solid block.

Example

00000
01110
01110
01110

00000
01110
01110
01110

00000
01110
01110
01110

In the above example we have a 3x3 cube - the bottom layer first, then the middle and then the top.

Output

The output should be a single integer giving the number of contiguous blocks within the input.

What's considered contiguous?

If any two 1s are adjacent to each other to the front, back, left, right, top or bottom, they are considered to be part of the same contiguous block. If they are not adjacent or they are only adjacent diagonally, they are not considered to be part of the same block.

Examples

00
11

Contiguous.

10
10

Contiguous.

10
01

Not contiguous.

01
00

01
00

Contiguous.

01
00

00
01

Not contiguous.

01
00

00
10

Not contiguous.

01
00

10
00

Not contiguous.

Test inputs

11101110111
10000011100

00111000000
00000000000

Result: 1

111
111
111

000
010
000

111
111
111

Result: 1

111
111
111

100
000
000

101
011
111

Result: 2

11011011011
00100100100

11011011011
00100100100

00100100100
11011011011

00100100100
11011011011

Result: 14

11011011011
01100100110

11011011011
00100100100

00100100100
11011011011

00100100100
11011011011

Result: 12

11011011011
00100100100

11011011011
01100100110

00100100100
11011011011

00100100100
11011011011

Result: 10

11111
10001
10001
10001
11111

Result: 1

11111
10001
10101
10001
11111

Result: 2

11111
11111
11111
11111
11111

11111
10001
10001
10001
11111

11111
10001
10001
10001
11111

11111
10001
10001
10001
11111

11111
11111
11111
11111
11111

Result: 1

11111
11111
11111
11111
11111

11111
10001
10001
10001
11111

11111
10001
10101
10001
11111

11111
10001
10001
10001
11111

11111
11111
11111
11111
11111

Result: 2

11111
11111
11111
11111
11111

11111
10001
10001
10001
11111

11111
10001
10101
10001
11111

11111
10001
10101
10001
11111

11111
11111
11111
11111
11111

Result: 1

Input format

I'm happy to be slightly flexible on the input format, so if you want to take a list of strings as input instead of one continuous string that's okay, and if you want to take a list of lists of characters (or integers if that helps) that's okay too.

Your answer can be a full program reading input or a function taking the input as a parameter. If your anonymous function needs a name in order for me to call it, then the characters for assigning the function to a name need to be counted too.

This is code golf so shortest code in bytes will win the big green tick, but any answer that meets the spec, passes the tests and has obviously been golfed will get my upvote.

Gareth

Posted 2017-01-17T22:10:37.833

Reputation: 11 678

1Can we take the input as 3dimensional array? – flawr – 2017-01-17T22:18:53.200

1@flawr Yes you can. – Gareth – 2017-01-17T22:22:19.373

Thanks for providing so many test cases! I suggest you put most of them in a snippet/gist/pastebin in order to declutter the challenge a little bit. – flawr – 2017-01-18T10:49:15.960

@flawr I've put them all into one code block to force the scroll bar to appear. – Gareth – 2017-01-18T11:14:10.863

Answers

3

Octave, 30 bytes

bwlabeln(...,6) determines the 6-connected components of an n-dimensional array and outputs the number of components found as a second argument.

@(m){[~,N]=bwlabeln(m,6),N}{2}

Try it online!

flawr

Posted 2017-01-17T22:10:37.833

Reputation: 40 560

Apologies. I've just noticed ( over 2 years late :-\ ) that I never accepted your answer even though you won. – Gareth – 2019-02-19T22:33:59.033

@Gareth Thanks! Actually many people don't accept any code-golf answers in the first place as the challenges usually do not have any deadline. So it might always be the case that someone can find an even shorter answer. See for example the discussion here.

– flawr – 2019-02-20T08:44:36.713

Yes, I've read that. I prefer to accept after a few answers have come in - I can always change the accepted answer if someone comes along with a shorter answer. :-) – Gareth – 2019-02-20T11:20:57.027

3

APL, 83 bytes

{0=⍴o←(,G)/Z←,⍳⍴G←⍵:0⋄1+∇G⊣{G[⊂⍵]←0⋄0=⍴A←G[A]/A←(A∊Z)/A←⍵∘+¨(+,-)↓∘.=⍨⍳3:⍬⋄∇¨A}⊃o}

Unlike some other languages, APL does not have a built-in for this (that I know of).

This function takes a 3-dimensional array of bits. It uses a 3-dimensional flood fill to remove blocks one by one, and counts how many blocks it can remove before the input is empty.

Non-golfed version with comments here.

marinus

Posted 2017-01-17T22:10:37.833

Reputation: 30 224

Why the read function when input may be rank 3? – Adám – 2017-01-18T00:05:19.340

@Adám: so I could enter the test data easier. That read function reads the input as written in the question using and returns a rank-3 array. That way I didn't have to convert it into X Y Z ⍴ ... by hand. Since I wrote it anyway, I thought I might as well include it in the non-golfed version. – marinus – 2017-01-18T00:09:29.100

3

Mathematica, 53 bytes

Max@MorphologicalComponents[#,CornerNeighbors->False]&

Unnamed function taking a 3D-array of integers. MorphologicalComponents is the builtin being exploited here: treating 0 as empty space, it separates the other integers into contiguous blocks, and assigns each block a number (starting from 1, 2, ...) and replaces all of its component entries by that number. So the number of blocks is just the maximum of all entries thus produced. Unfortunately, by default MorphologicalComponents counts diagonal neighbors as connected, so we need to add the option CornerNeighbors->False to fit the spec. (Side note: MorphologicalComponents is really built to operate on 2D and 3D images; but it handles arrays of integers as a side benefit.)

Greg Martin

Posted 2017-01-17T22:10:37.833

Reputation: 13 940