Wyzwanie

Biorąc pod uwagę graficzny kształt kształtu, określ, ile otworów jest w nim.

Nie duplikat

To pytanie zostało oznaczone jako możliwy duplikat Hrabiów . Uważam, że to wyzwanie różni się od wyzwania Count Island, ponieważ w tym musisz wymyślić, jak wyeliminować bloki dotykające granicy.

Wejście

Dane wejściowe będą podawane jako forma wprowadzania 2D, albo ciąg wielowierszowy, tablica ciągów lub tablica znaków. To reprezentuje kształt. Gwarantowany jest kształt w jednym kawałku, połączony krawędzią. Podaj sposób, w jaki chcesz pobierać dane wejściowe.

Wynik

Dane wyjściowe to pojedyncza liczba całkowita określająca, ile otworów ma kształt. Końcowy znak nowej linii jest dozwolony, ale nie ma innych początkowych lub końcowych białych znaków. Innymi słowy, wynik musi być zgodny z wyrażeniem regularnym ^\d+\n?$.

Co to jest dziura?

Są to pojedyncze otwory:

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

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

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

To nie są dziury:

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

###
#  
###

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

Właściwie, jeśli szczelina łączy się z zewnętrzną krawędzią, nie jest to dziura.

Przypadki testowe

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

Możesz użyć dowolnej postaci zamiast „#” i zamiast spacji.

Kryteria punktacji obiektywnej

Wynik jest podawany jako liczba bajtów w twoim programie.

Zwycięski

Zwycięzcą zostanie zgłoszenie o najniższym wyniku do 4 kwietnia.

MATLAB / Octave, 18 bajtów

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

Wypróbuj online!

Jest to anonimowa funkcja przyjmująca logiczną macierz jako dane wejściowe. Obiekt jest tworzony przez truewpisy (o określonej łączności), puste miejsce to falsewpisy.

bweuler następnie oblicza liczbę eulerową obrazu binarnego reprezentowanego przez tę macierz, czyli liczbę obiektów minus liczbę otworów.

Mathematica, 59 57 bajtów

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

Jest do tego wbudowany. Pobiera dane wejściowe jako macierz 2D 1s (ściany) i 0s (dziury). Dla wygody oto wszystkie przypadki testowe w tym formacie wejściowym:

{{{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}}}

Alternatywne rozwiązanie, 59 bajtów

To było moje oryginalne podejście. Opiera się również na wbudowanych komponentach, ale nie liczy bezpośrednio otworów (zamiast tego traktuje same otwory jako komponenty).

Max@*MorphologicalComponents@*DeleteBorderComponents@*Image

Przyjmuje taki sam format wejściowy jak powyżej, ale z zamianą ról 0s i 1s.

Powodem, dla którego muszę przekonwertować to na Imagepierwsze, jest to, że w przeciwnym razie Mathematica rozważyłaby wszystko1 komórki jako część pojedynczego komponentu (ponieważ traktuje matrycę jako matrycę składową-etykietę). Dlatego jeśli jakakolwiek 1komórka przekroczy margines, usunie wszystkie z nich. GdyDeleteBorderComponents zamiast tego zostanie użyty na obrazie, przeprowadzi niejawną kontrolę łączności, aby znaleźć komponenty.

Alternatywnie, mógłbym zadzwonić jako MorphologicalComponents pierwszy , co zmieniłoby dane wejściowe w odpowiednią matrycę etykiet, ale jeśli to zrobię DeleteBorderComponents, nie jest już zagwarantowane, że maksymalna etykieta komponentu odpowiada liczbie komponentów (ponieważ mógłbym usunąć mniejszy komponent).

Perl 5 , 154 bajtów

152 bajty kodu + 2 bajty na -p0flagę.

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

Wypróbuj online!

Myślę, że kod jest dość zrozumiały.

Jeśli potrzebujesz kilku wyjaśnień, aby zrozumieć, oto kilka kroków transformacji wykonanych przez program na prostym wejściu (pochodzącym stąd ), a następnie kilka wyjaśnień poniżej:

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

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

######
#AAAAA
#ZA####
# A # #
#### #
######

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

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

Najpierw s/^ | $/A/gm;s/^.*\K | (?=.*$)/A/&&redozastąpi spacje na ramce (1. regex dla lewej / prawej, 2 dla dolnej / górnej) z A(wybieram tę postać dość dowolnie).
Następnie otrzymujemy szerokość kształtu /.*/;$@="@+"-1;.
Teraz chcemy zastąpić każde miejsce, które jest połączone Az a A(ponieważ spacja jest podłączona do a A, oznacza to, że nie może być częścią dziury. To zrobione przez for$%(A,X){(s/$%(.?.?.{$@})? /$%$1$%/s||s/ (.?.?.{$@})?$%/$%$1$%/s)&&redo}. (Zauważysz, że to zrobiono raz dla As i jeden dla Xs - wyjaśnienia Xponiżej podano poniżej. Istnieją dwa wyrażenia regularne: s/$%(.?.?.{$@})? /$%$1$%/szajmuje się spacjami po prawej lub na dole a A. I s/ (.?.?.{$@})?$%/$%$1$%/sspacjami na górze lub po lewej stronieA .
W tym momencie jedyne spacje, które pozostały w sznurek jest częścią otworów.
Podczas gdy są jeszcze spacje, powtarzamy:
- Aby wiedzieć, ile jest dziur, zastępujemy spację znakiem X( s/ /X/) i zwiększamy licznik otworów ( $\++) i ponawiamy cały program (w rzeczywistości chcemy tylko powtórzyć forpętlę , ale jest mniej bajtów, aby powtórzyć cały program).
- Następnie forpętla zastąpi każdą przestrzeń, która jest połączona z Xliterą a X, ponieważ są one częścią tego samego otworu.
Na końcu $\|=0zapewnia, że ​​jeśli nie ma otworów, 0zamiast pustego łańcucha drukowany jest znak a. I $\jest domyślnie drukowane dzięki -pflagom.

Python 2, 282 bajtów

+100 do obsługi dotyków ukośnych TT_TT (czy naprawdę tego potrzebujemy?)
-119 dzięki wytycznym @Rod :)

Wypróbuj online . Pobiera na wejściu tablicę tablic znaków „#” i białych znaków.

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

Wyszukuje pierwsze białe znaki i oznacza je jako niepuste („#”). Rekurencyjnie sprawdź całe otoczenie, wypełniając wszystkie puste komórki. Jeśli jakakolwiek pusta komórka obecnego „dołka” wydaje się znajdować na liczniku obramowania, nie zmieni się, w przeciwnym razie zostanie zwiększona o 1. Powtarzaj proces, aż nie będzie już białych znaków.

Python 2, 233 225 222 bajtów

math_junkie : -8 bajtów

Pobiera na wejściu tablicę 2d logicznych / liczb całkowitych (0/1)

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

Wypróbuj online!

Wersja sformatowana:

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 bajty

Nie jestem zadowolony z tego ... może ktoś inny może to rozwiązać ... Jeśli będę miał energię później, odwrócę pierwszą pętlę i zobaczę, czy to może pomóc w przycięciu sprawdzania granic.

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

Wypróbuj online

Kompletny program, akceptuje wejście do standardowego wejścia, wyjście do standardowego wyjścia. Używa rozłącznych zestawów do określania tymczasowych dziur, a gdy zabija dowolne, dotykaj granic (z pewną unikalnością dla górnej krawędzi).

Sformatowany i skomentowany kod:

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

Ślimaki , 48 bajtów

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

Nie golfowany:

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

JavaScript (ES6), 192 bajty

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>

Na podstawie mojej odpowiedzi na Wykrywanie nieudanych zamków . Najpierw sznurek jest wypełniony spacjami, aby utworzyć obszar wokół kształtu. RegExp następnie wyszukuje dwa sąsiednie kwadraty, jeden zawierający @, jeden zawierający spację i zamienia je oba na @. Jeśli nie może tego zrobić, wypełnia pole znakiem@ i liczy to jako nową dziurę. Na koniec odejmuje się jeden, aby uwzględnić otaczający obszar.