5
\$\begingroup\$

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.

Improve this question
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Can we take the input as 3dimensional array? \$\endgroup\$
    – flawr
    Jan 17, 2017 at 22:18
  • 1
    \$\begingroup\$ @flawr Yes you can. \$\endgroup\$
    – Gareth
    Jan 17, 2017 at 22:22
  • \$\begingroup\$ 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. \$\endgroup\$
    – flawr
    Jan 18, 2017 at 10:49
  • \$\begingroup\$ @flawr I've put them all into one code block to force the scroll bar to appear. \$\endgroup\$
    – Gareth
    Jan 18, 2017 at 11:14

3 Answers 3

Reset to default
4
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Why the read function when input may be rank 3? \$\endgroup\$
    – Adám
    Jan 18, 2017 at 0:05
  • \$\begingroup\$ @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. \$\endgroup\$
    – marinus
    Jan 18, 2017 at 0:09
3
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Apologies. I've just noticed ( over 2 years late :-\ ) that I never accepted your answer even though you won. \$\endgroup\$
    – Gareth
    Feb 19, 2019 at 22:33
  • \$\begingroup\$ @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. \$\endgroup\$
    – flawr
    Feb 20, 2019 at 8:44
  • \$\begingroup\$ 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. :-) \$\endgroup\$
    – Gareth
    Feb 20, 2019 at 11:20
3
\$\begingroup\$

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

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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