17
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Related \$\endgroup\$ – VisualMelon Mar 24 '17 at 13:24
  • 2
    \$\begingroup\$ Could you add ###|# #|## as a test case? That should be 0, right? \$\endgroup\$ – Martin Ender Mar 24 '17 at 13:41
  • 1
    \$\begingroup\$ Related \$\endgroup\$ – Matthew Roh Mar 24 '17 at 16:20
  • 1
    \$\begingroup\$ Possible duplicate of Code-Golf: Count Islands \$\endgroup\$ – Matthew Roh Mar 25 '17 at 4:00
  • \$\begingroup\$ @SIGSEGV Thank you for pointing that out; however, I believe that this challenge has a critical component that makes it different enough from the other challenge to warrant its own post (I edited in the difference). Please let me know what you think, and we may want to start a discussion in chat if necessary. \$\endgroup\$ – HyperNeutrino Mar 25 '17 at 4:22
12
\$\begingroup\$

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.

\$\endgroup\$
8
\$\begingroup\$

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

\$\endgroup\$
  • 5
    \$\begingroup\$ Really, Mathematica has got built-ins for just everything... \$\endgroup\$ – Mr. Xcoder Mar 24 '17 at 21:14
  • 3
    \$\begingroup\$ @Mr.Xcoder I have a good challenge idea: Find a challenge for which Mathematica has no builtin. \$\endgroup\$ – HyperNeutrino Mar 25 '17 at 2:12
  • \$\begingroup\$ @HyperNeutrino good idea, but I think that the users of Mathematica will heavily downvote it, unfortunately, and I don't know if the community will react well... =] \$\endgroup\$ – Mr. Xcoder Mar 25 '17 at 9:30
  • 1
    \$\begingroup\$ @HyperNeutrino, there's probably a builtin for that too :-) \$\endgroup\$ – Brian Minton Mar 25 '17 at 22:08
  • \$\begingroup\$ @BrianMinton Haha. There's probably a built-in in Mathematica called GenerateBuiltin. It generates a built-in for any challenge that doesn't have a built-in. Also, I feel bad for Martin Ender's inbox, so if you want, let's continue this discussion here \$\endgroup\$ – HyperNeutrino Mar 25 '17 at 23:04
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ You can use sum(A,[]) to flatten \$\endgroup\$ – Rod Mar 24 '17 at 15:52
  • 1
    \$\begingroup\$ Also you can check this answer, it has the same recursive logic, and also have some other tricks (like the function "renaming" in the first line) \$\endgroup\$ – Rod Mar 24 '17 at 15:57
  • \$\begingroup\$ @Rod Trick with sum is very good, thank you. I'm now working on getting all 8 directions without all this uglyness, your answer might help. I'll update after that \$\endgroup\$ – Dead Possum Mar 24 '17 at 16:02
  • \$\begingroup\$ Note that on my answer I called the recursive function inside a list comprehension just to use less bytes, but on your case you can check the list length to see if the current cell belong to borders (the content of the list will be a lot of Nones, but that is irrelevant) \$\endgroup\$ – Rod Mar 24 '17 at 16:07
  • 1
    \$\begingroup\$ You can use list unpacking on x=T[0];y=T[1] -> x,y=T, you (probably) don't need to declare g=1 on 3rd line, and you can use < or > to compare strings (it will take the ord() value of each char) allowing you to replace A[y][x]!='#' with A[y][x]<'#', since ' '<'#'. \$\endgroup\$ – Rod Mar 24 '17 at 16:47
3
\$\begingroup\$

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))
\$\endgroup\$
  • 1
    \$\begingroup\$ You can save a few bytes with print sum(m(x,y)... instead of a= and print a \$\endgroup\$ – math junkie Mar 24 '17 at 23:50
  • 1
    \$\begingroup\$ Also, some minor whitespace golfs: TIO \$\endgroup\$ – math junkie Mar 24 '17 at 23:55
1
\$\begingroup\$

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);
    }
}
\$\endgroup\$
  • \$\begingroup\$ Convert it to a Func<List<string>, int> to remove the fluff and console stuff. However, I've seen you have local functions so you may not be able to have them in a func. Could just compile to a method int h(string[] s) { }. \$\endgroup\$ – TheLethalCoder Mar 24 '17 at 16:31
  • \$\begingroup\$ I'm sure there's a lot more that can be simplified here... \$\endgroup\$ – TheLethalCoder Mar 24 '17 at 16:32
  • \$\begingroup\$ @TheLethalCoder I shan't be converting this to a different form, I don't like answers as functions (wouldn't need to be a lambda, as you said). Yeah... the whole thing feels bloated... but I spent a good while mutating it and didn't make any substantial progress, so I did a few passes of 'bitty' golfing and pushed it. Feel free to submit a shorter version, I'm less than attached to this one. \$\endgroup\$ – VisualMelon Mar 24 '17 at 16:36
  • \$\begingroup\$ I mean just converting it to a method and removing all the console stuff, as that would no longer be needed, is going to knock 50-100 bytes off (just a guess but it will knock a lot off). \$\endgroup\$ – TheLethalCoder Mar 24 '17 at 16:38
  • \$\begingroup\$ @TheLethalCoder indeed; I just don't like submitting functions as answers. Standard Input is pretty Standard, and a 'complete program' is easy to compile and run anywhere. Don't get me started on untyped lambdas... Obviously, if there was a competing Java answer, then I'd have to slacking my standards a bit... \$\endgroup\$ – VisualMelon Mar 24 '17 at 16:43
1
\$\begingroup\$

Snails, 48 bytes

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

Ungolfed:

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

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.

\$\endgroup\$
  • \$\begingroup\$ Can you provide a TIO link of some sort? Thanks! \$\endgroup\$ – HyperNeutrino Mar 25 '17 at 2:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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