Herausforderung

Bestimmen Sie anhand einer grafischen Eingabe einer Form, wie viele Löcher sich darin befinden.

Nicht duplizieren

Diese Frage wurde als mögliches Duplikat von Count Islands markiert . Ich glaube, diese Herausforderung unterscheidet sich von der Count Island-Herausforderung, weil Sie in dieser herausfinden müssen, wie Sie Blöcke entfernen, die die Grenze berühren.

Eingang

Die Eingabe erfolgt in Form einer 2D-Eingabe, entweder als mehrzeilige Zeichenfolge, als Array von Zeichenfolgen oder als Array von Zeichenfeldern. Dies repräsentiert die Form. Die Form ist garantiert nur einteilig und durch eine Kante verbunden. Bitte geben Sie an, wie die Eingabe erfolgen soll.

Ausgabe

Die Ausgabe ist eine einzelne Ganzzahl, die angibt, wie viele Löcher sich in der Form befinden. Ein abschließender Zeilenumbruch ist zulässig, jedoch kein anderes führendes oder abschließendes Leerzeichen. Mit anderen Worten, die Ausgabe muss mit dem regulären Ausdruck übereinstimmen ^\d+\n?$.

Was ist ein Loch?

Dies sind Einzellöcher:

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

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

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

Dies sind keine Löcher:

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

###
#  
###

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

Ziemlich genau, wenn sich die Lücke mit der Außenkante verbindet, ist es kein Loch.

Testfälle

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

Sie können anstelle des '#' und anstelle der Leerzeichen ein beliebiges Zeichen verwenden.

Objektive Bewertungskriterien

Die Punktzahl wird als Anzahl der Bytes in Ihrem Programm angegeben.

Gewinnen

Der Gewinner ist die Einsendung mit der niedrigsten Punktzahl bis zum 4. April.

MATLAB / Octave, 18 Bytes

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

Probieren Sie es online!

Dies ist eine anonyme Funktion, die eine logische Matrix als Eingabe verwendet. Das Objekt wird aus den trueEinträgen (mit der angegebenen Konnektivität) gebildet, der leere Raum sind die falseEinträge.

bweuler berechnet dann die Eulernummer des durch diese Matrix dargestellten binären Bildes, dh die Anzahl der Objekte abzüglich der Anzahl der Löcher.

Mathematica, 59 57 Bytes

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

Dafür gibt es eine eingebaute. Nimmt Eingaben als 2D-Matrix aus 1s (Wänden) und 0s (Löchern) auf. Der Einfachheit halber sind hier alle Testfälle in diesem Eingabeformat aufgeführt:

{{{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 Lösung, 59 Bytes

Dies war mein ursprünglicher Ansatz. Es basiert auch auf den komponentenbezogenen Einbauten, zählt jedoch die Löcher nicht direkt (stattdessen werden die Löcher selbst als Komponenten behandelt).

Max@*MorphologicalComponents@*DeleteBorderComponents@*Image

Verwendet dasselbe Eingabeformat wie oben, jedoch mit vertauschten Rollen von 0s und 1s.

Der Grund, warum ich dies in eine Imageerste konvertieren muss, besteht darin, dass Mathematica andernfalls alle 1-Zellen als Teil einer einzelnen Komponente betrachtet (da die Matrix als Komponentenbeschriftungsmatrix behandelt wird). Wenn also eine 1-Zelle an den Rand grenzt, werden alle gelöscht. Wenn DeleteBorderComponentsstattdessen ein Image verwendet wird, wird eine implizite Konnektivitätsprüfung durchgeführt, um die Komponenten zu finden.

Alternativ könnte ich MorphologicalComponents zuerst aufrufen , um die Eingabe in eine geeignete Beschriftungsmatrix umzuwandeln. Wenn ich dies jedoch zum DeleteBorderComponentszweiten Mal tue, kann nicht mehr garantiert werden, dass die maximale Komponentenbeschriftung der Anzahl der Komponenten entspricht (da ich möglicherweise eine kleinere Komponente lösche).

Perl 5 , 154 Bytes

152 Byte Code + 2 Byte für -p0Flag.

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

Probieren Sie es online!

Ich denke, der Code ist ziemlich selbsterklärend.

Wenn Sie einige Erklärungen benötigen, um diese zu verstehen, finden Sie hier einige Schritte der Transformationen, die das Programm an einer einfachen Eingabe (von hier aus ) durchführt, gefolgt von den folgenden Erklärungen:

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

######
# EIN
# ####
# # #
#### #
######

######
#AAAAA
#EIN####
#EIN# #
#### #
######

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

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

Erstens s/^ | $/A/gm;s/^.*\K | (?=.*$)/A/&&redowerden die Leerzeichen in der Umrandung (1. Regex für links / rechts, 2. für unten / oben) durch A(ich wähle dieses Zeichen ziemlich willkürlich) ersetzt.
Dann erhalten wir die Breite der Form mit /.*/;$@="@+"-1;.
Jetzt wollen wir jeden Raum ersetzen, die eine verbunden ist Amit einem A(denn wenn ein Raum a verbunden ist A, bedeutet dies nicht Teil eines Lochs sein kann. Das wird getan durch for$%(A,X){(s/$%(.?.?.{$@})? /$%$1$%/s||s/ (.?.?.{$@})?$%/$%$1$%/s)&&redo}. (Sie werden feststellen , dass dies geschehen ist einmal für das As und einmal für das Xs - Erklärungen für das Xsind unten) Hier gibt es zwei reguläre Ausdrücke: s/$%(.?.?.{$@})? /$%$1$%/sbefasst sich mit den Räumen, die rechts oder unten von a stehen, Aund s/ (.?.?.{$@})?$%/$%$1$%/smit den Räumen oben oder links von a A.
Zu diesem Zeitpunkt sind die einzigen Leerzeichen, die in der Zeichenfolge verbleiben, Teil von Löchern.
Während es noch Leerzeichen gibt, wiederholen wir:
- Um zu wissen, wie viele Löcher es gibt, ersetzen wir ein Leerzeichen durch ein X( s/ /X/) und erhöhen den Zähler der Löcher ( $\++) und wiederholen das gesamte Programm (eigentlich wollen wir nur die forSchleife wiederholen) , aber es sind weniger Bytes, um das gesamte Programm zu wiederholen).
- Dann ersetzt die forSchleife jeden Raum, der mit a verbunden ist, Xdurch a X, da sie Teil desselben Lochs sind.
Am Ende wird $\|=0sichergestellt, dass, wenn keine Löcher vorhanden sind, 0anstelle eines leeren Strings ein gedruckt wird. Und $\wird dank -pFlagge implizit gedruckt .

Python 2, 282 Bytes

+100 für diagonale Berührungen TT_TT (brauchen wir das wirklich?)
-119 dank @Rod Anleitung :)

Probieren Sie es online aus . Nimmt ein Array von Arrays aus Zeichen '#' und Leerzeichen als Eingabe.

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

Sucht nach dem ersten Leerzeichen und markiert es als nicht leer ('#'). Überprüfen Sie rekursiv die gesamte Umgebung, während Sie alle leeren Zellen füllen. Wenn sich eine leere Zelle des aktuellen "Lochs" auf dem Grenzzähler zu befinden scheint, ändert sich dies nicht. Andernfalls wird sie um 1 erhöht. Wiederholen Sie den Vorgang, bis keine Leerzeichen mehr vorhanden sind.

Python 2, 233 225 222 Bytes

math_junkie : -8 Bytes

Nimmt ein 2d-Array von Booleschen Werten / Ganzzahlen (0/1) als Eingabe

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

Probieren Sie es online!

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

C # 7, 364 Bytes

Unzufrieden damit ... vielleicht kann es jemand anderes klären ... Wenn ich später die Energie habe, werde ich die erste Schleife invertieren und sehen, ob dies dazu beitragen kann, die Grenzwertprüfung zu vereinfachen.

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);}}

Probieren Sie es online aus

Komplettes Programm, akzeptiert Eingaben zum Standardeingang, Ausgabe zum Standardausgang. Verwendet disjunkte Sets, um provisorische Löcher zu bestimmen, und wenn sie getötet werden, berühren Sie die Ränder (mit ein wenig Bedächtigkeit für die obere Kante).

Formatierter und kommentierter 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);
    }
}

Schnecken , 48 Bytes

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

Ungolfed:

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

JavaScript (ES6), 192 Byte

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>

Basierend auf meiner Antwort auf Fehlerhafte Schlösser erkennen . Zuerst wird die Zeichenfolge mit Leerzeichen aufgefüllt, um einen Bereich um die Form herum zu erstellen. Der RegExp sucht dann nach zwei benachbarten Feldern, von denen eines @ein Leerzeichen enthält, und ersetzt beide durch ein @. Wenn dies nicht möglich ist, wird ein Leerzeichen mit einem @gefüllt und dies als neues Loch gezählt. Schließlich wird einer abgezogen, um die Umgebung zu berücksichtigen.