How Many Holes?

Question

Challenge

Given a graphical input of a shape, determine how many holes there are in it.

Not Duplicate

This question was marked as a possible duplicate of Count Islands. I believe this challenge is different from the Count Island challenge because in this one, you have to figure out how to eliminate blocks that touch the border.

Input

Input will be given as some 2D form of input, either a multiline string, an array of strings, or an array of character arrays. This represents the shape. The shape is guaranteed to be in only one piece, connected by edge. Please specify how you want input to be taken.

Output

Output is a single integer stating how many holes there are in the shape. A trailing newline is permitted, but no other leading or trailing whitespace. In other words, the output must match the regular expression ^\d+\n?$.

What is a hole?

These are single holes:

####
#  #
#  #
####

####
#  #
# ##
###

#####
# # #
#   #
#####

These are not holes:

########
########
#   ####
#   ####
# ######
#       
########

###
#  
###

##########
#         
# ########
# #      #
# # #### #
# #   ## #
# ###### #
#        #
##########

Pretty much, if it the gap joins the outside edge, it is not a hole.

Test cases

#####
# # # -> 2
#####

#####
#    
# ### -> 1
# # #
#####

####
## # -> 1 (things are connected by edges)
# ##
####

###
### -> 0 (You must handle shapes with no holes, but input will always contain at least one filled space)
###

You can use any character in place of the '#', and in place of the spaces.

Objective Scoring Criteria

The score is given as the number of bytes in your program.

Winning

The winner will be the submission with the lowest score, by April 4th.

Answer 1

MATLAB / Octave, 18 bytes

@(g)1-bweuler(g,4)

Try it online!

This is an anonymous function taking a logical matrix as input. The object is formed by the true entries (with the specified connectivity), the empty space are the false entries.

bweuler then calculates the euler number of the binary image represented by that matrix, that is the number of objects minus the number of holes.

Answer 2

Mathematica, 59 57 bytes

1/.ComponentMeasurements[#,"Holes",CornerNeighbors->0>1]&

There's a built-in for that. Takes input as a 2D matrix of 1s (walls) and 0s (holes). For convenience, here are all the test cases in this input format:

{{{1,1,1,1},{1,0,0,1},{1,0,0,1},{1,1,1,1}},
 {{1,1,1,1},{1,0,0,1},{1,0,1,1},{1,1,1,0}},
 {{1,1,1,1,1},{1,0,1,0,1},{1,0,0,0,1},{1,1,1,1,1}},
 {{1,1,1,1,1,1,1,1},{1,1,1,1,1,1,1,1},{1,0,0,0,1,1,1,1},{1,0,0,0,1,1,1,1},{1,0,1,1,1,1,1,1},{1,0,0,0,0,0,0,0},{1,1,1,1,1,1,1,1}},
 {{1,1,1},{1,0,0},{1,1,1}},
 {{1,1,1,1,1,1,1,1,1,1},{1,0,0,0,0,0,0,0,0,0},{1,0,1,1,1,1,1,1,1,1},{1,0,1,0,0,0,0,0,0,1},{1,0,1,0,1,1,1,1,0,1},{1,0,1,0,0,0,1,1,0,1},{1,0,1,1,1,1,1,1,0,1},{1,0,0,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,1}},
 {{1,1,1,1,1},{1,0,1,0,1},{1,1,1,1,1}},
 {{1,1,1,1,1},{1,0,0,0,0},{1,0,1,1,1},{1,0,1,0,1},{1,1,1,1,1}},
 {{1,1,1,1},{1,1,0,1},{1,0,1,1},{1,1,1,1}}}

Alternative solution, 59 bytes

This was my original approach. It's also based on the component-related built-ins, but doesn't count the holes directly (instead it treats the holes themselves as components).

Max@*MorphologicalComponents@*DeleteBorderComponents@*Image

Takes the same input format as above, but with the roles of 0s and 1s swapped.

The reason I need to convert this to an Image first is that, otherwise, Mathematica would consider all the 1-cells as part of a single component (because it treats the matrix as a component-label matrix). Hence, if any 1-cell borders the margin, it would delete all of them. When DeleteBorderComponents is used on an image instead, then it will do an implicit connectivity check to find the components.

Alternatively, I could call MorphologicalComponents first, which would turn the input into a suitable label matrix, but if I do DeleteBorderComponents second it's no longer guaranteed that the maximum component label corresponds to the number of components (because I might delete a smaller component).

Answer 3

Perl 5, 154 bytes

152 bytes of code + 2 bytes for -p0 flag.

s/^ | $/A/gm;s/^.*\K | (?=.*$)/A/&&redo;/.*/;$@="@+"-1;for$%(A,X){$~="(.?.?.{$@})?";(s/$%$~ /$%$1$%/s||s/ $~$%/$%$1$%/s)&&redo}s/ /X/&&++$\&&redo}{$\|=0

Try it online!

I think the code is quite self-explanatory.

---

If you need some explanations to understand, here are a few steps of the transformations done by the program on a simple input (coming from here), followed by some explanations bellow:

######
#     
# ####
# #  #
#### #
######

######
#    A
# ####
# #  #
#### #
######

######
#AAAAA
#A####
#A#  #
#### #
######

######
#AAAAA
#A####
#A#X #
#### #
######

######
#AAAAA
#A####
#A#XX#
####X#
######

First, s/^ | $/A/gm;s/^.*\K | (?=.*$)/A/&&redo will replace the spaces in the border (1st regex for left/right, 2nd for bottom/top) with A (I choose that character quite arbitrary).
Then, we get the width the shape with /.*/;$@="@+"-1;.
Now, we want to replace every space that is connected to a A with a A (because if a space is connected to a A, it means it can't be part of a hole. That's done by for$%(A,X){(s/$%(.?.?.{$@})? /$%$1$%/s||s/ (.?.?.{$@})?$%/$%$1$%/s)&&redo}. (you'll notice that this is done once for the As and one for the Xs - explanations for the X are bellow). There are two regex here: s/$%(.?.?.{$@})? /$%$1$%/s deals with the spaces that are on the right or bottom of a A. And s/ (.?.?.{$@})?$%/$%$1$%/s with the spaces on top or left of a A.
At this point, the only spaces that are left in the string are part of holes.
While there are still spaces, we repeat:
- To know how much holes there are, we replace a space with a X (s/ /X/) and increment the counter of holes ($\++), and redo the entire program (actually, we only want to redo the for loop, but it's less bytes to redo the whole program).
- Then, the for loop will replace every space that is connected to a X with a X, as they are part of the same hole.
At the end, $\|=0 ensures that if there are no holes, a 0 is printed instead of an empty string. And $\ is implicitly printed thanks to -p flag.

Answer 4

Python 2, 282 bytes

+100 to handle diagonal touches TT_TT (do we really need that?)
-119 thanks to @Rod guidance :)

Try it online. Takes array of arrays of chars '#' and whitespace as input.

A=input()
c=0
X=len(A[0])-1
Y=len(A)-1
def C(T):
 x,y=T
 global g
 if A[y][x]<'#':
    if y<1or y==Y or x<1or x==X:g=0
    A[y][x]='#';map(C,zip([x]*3+[min(x+1,X)]*3+[max(x-1,0)]*3,[y,min(y+1,Y),max(y-1,0)]*3))
while' 'in sum(A,[]):i=sum(A,[]).index(' ');g=1;C((i%-~X,i/-~X));c+=g
print c

Searches for first whitespace and mark it as non-empty ('#'). Recursively check all of it's surrounding, while filling all empty cells. If any empty cell of current "hole" appears to be on border counter won't change, otherwise it would be increased by 1. Repeat process, until there is no more whitespaces.

Answer 5

Python 2, 233 225 222 bytes

math_junkie: -8 bytes

Takes 2d array of booleans/integers (0/1) as input

s=input()
o=[-1,0,1]
m=lambda x,y:0if x in[-1,len(s[0])]or y in[-1,len(s)]else 1if s[y][x]else(s[y].__setitem__(x,1),all([m(x+a,y+b)for a in o for b in o]))[1]
e=enumerate
print sum(m(x,y)-c for y,l in e(s)for x,c in e(l))

Try it online!

Formatted version:

s = input()
o = [-1, 0, 1]
m = lambda x,y:
    0 if x in [-1, len(s[0])] or y in [-1, len(s)]
      else
        1 if s[y][x]
          else
            (s[y].__setitem__(x, 1),
             all([m(x + a, y + b) for a in o for b in o]))[1]
e = enumerate
print sum(m(x, y) - c for y, l in e(s) for x, c in e(l))

Answer 6

C# 7, 364 bytes

Less than happy with this... maybe someone else can sort it out... If I have the energy later I will invert the first loop, and see if that can help to trim the bounds checking.

using C=System.Console;class P{static void Main(){string D="",L;int W=0,H=0,z;for(;(L=C.ReadLine())!=null;H+=W=L.Length)D+=L;int[]S=new int[H*9];int Q(int p)=>S[p]<p?Q(S[p]):p;void R(int r)=>S[Q(r+=z)]=S[r]>0?z:0;for(z=H;z-->0;)if(D[z]<33){S[z]=z;R(1);R(W);R(W+1);R(W-1);}for(;++z<H;)S[Q(z)]*=z>H-W-2|z%W<1|z%W>W-2?0:1;for(;W<H;)z+=Q(W)<W++?0:1;C.WriteLine(z-H);}}

Try it online

Complete program, accepts input to standard in, output to standard out. Uses disjoint sets to determine provisional holes, and when kills any touch the borders (with some dodgyness for the top-edge).

Formatted and commented code:

using C=System.Console;

class P
{
    static void Main()
    {
        string D="", // the whole map
            L; // initally each line of the map, later each line of output

        // TODO: some of thse might be charable
        int W=0, // width, later position
            H=0, // length (width * height)
            z; // position, later counter

        // read map and width
        for(;(L=C.ReadLine())!=null; // read a line, while we can
                H+=W=L.Length) // record the width, and increment height
            D+=L; // add the line to the map

        // disjoint sets
        int[]S=new int[H*9]; // generousness (relieve some bounds checking)
        // note that S[x] <= x, because we call R with decending values of z

        // returns whatever p points to
        int Q(int p)=>S[p]<p?Q(S[p]):p;
        // points whatever r points to at z if r is empty
        void R(int r)=>S[Q(r+=z)]=S[r]>0?z:0; // note that is never called when z=0

        // fill out disjoint sets
        for(z=H;z-->0;)
            if(D[z]<33) // if cell is empty
            {
                S[z]=z; // point it at itself

                // point the things next  to z at z
                R(1);
                R(W);
                R(W+1);
                R(W-1);
            }

        // zero sets which are against the left, bottom, or right edges
        for(;++z<H;)
            S[Q(z)]*=z>H-W-2|z%W<1|z%W>W-2?0:1; // TODO?: this suggests inverting the first loop (NOTE: would break S[x]<=x)

        // starting from the second row, count all the sets that point to this cell (ignores any non-zeros pointing to first row)
        for(;W<H;)
            z+=Q(W)<W++?0:1;

        C.WriteLine(z-H);
    }
}

Answer 7

Snails, 48 bytes

!{\ z`+~}\ {t\ z!.!~=((lu|u.+r)!(.,~},!{t\ z!.!~

Ungolfed:

!{
    (\   z)+
    ~
}
\ 
{
    t \ 
    z !.!~
    ={
        (lu|u.+r)
        !(.,~)
    }
},
!{
    t \ 
    z !.!~
}

Answer 8

JavaScript (ES6), 192 bytes

v=a=>Math.min(...a=a.map(s=>s.length))==Math.max(...a);
f=(s,t=(u=` `.repeat(w=s.search`
`+1))+`
`+s.replace(/^|$/gm,` `)+`
`+u,v=t.replace(RegExp(`( |@)([^]{${w},${w+2}})?(?!\\1)[ @]`),`@$2@`))=>t!=v?f(s,v):/ /.test(t)?f(s,t.replace(` `,`@`))+1:-1

<textarea id=i rows=10 cols=10></textarea><input type=button value=Count onclick=o.textContent=/^[\s#]+$/.test(i.value)*v(i.value.split`\n`)?f(i.value):`Invalid_Entry`><span id=o>

Based on my answer to Detect Failing Castles. First the string is padded with spaces to make an area around the shape. The RegExp then looks for two adjacent squares, one containing an @, one containing a space, and replaces them both with an @. If it can't do this, it fills in a space with an @ and counts this as a new hole. Finally one is subtracted to account for the surrounding area.