Desafío

Dada una entrada gráfica de una forma, determine cuántos agujeros hay en ella.

No duplicado

Esta pregunta fue marcada como un posible duplicado de Count Islands . Creo que este desafío es diferente del desafío Count Island porque en este, tienes que descubrir cómo eliminar los bloques que tocan el borde.

Entrada

La entrada se dará como una forma de entrada en 2D, ya sea una cadena multilínea, una matriz de cadenas o una matriz de matrices de caracteres. Esto representa la forma. Se garantiza que la forma sea de una sola pieza, conectada por el borde. Especifique cómo desea que se tome la entrada.

Salida

La salida es un entero entero que indica cuántos agujeros hay en la forma. Se permite una nueva línea final, pero no otros espacios en blanco iniciales o finales. En otras palabras, la salida debe coincidir con la expresión regular ^\d+\n?$.

¿Qué es un hoyo?

Estos son agujeros individuales:

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

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

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

Estos no son agujeros:

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

###
#  
###

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

Más o menos, si la brecha se une al borde exterior, no es un agujero.

Casos de prueba

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

Puede usar cualquier carácter en lugar del '#' y en lugar de los espacios.

Criterios de puntuación objetiva

La puntuación se da como el número de bytes en su programa.

Victorioso

El ganador será la presentación con el puntaje más bajo, antes del 4 de abril.

MATLAB / Octave, 18 bytes

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

Pruébalo en línea!

Esta es una función anónima que toma una matriz lógica como entrada. El objeto está formado por las trueentradas (con la conectividad especificada), el espacio vacío son las falseentradas.

bweuler luego calcula el número de Euler de la imagen binaria representada por esa matriz, es decir, el número de objetos menos el número de agujeros.

Mathematica, 59 57 bytes

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

Hay un incorporado para eso. Toma entrada como una matriz 2D de 1s (paredes) 0ys (agujeros). Por conveniencia, aquí están todos los casos de prueba en este formato de entrada:

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

Solución alternativa, 59 bytes.

Este fue mi enfoque original. También se basa en los elementos integrados relacionados con los componentes, pero no cuenta los agujeros directamente (en su lugar, trata los agujeros en sí mismos como componentes).

Max@*MorphologicalComponents@*DeleteBorderComponents@*Image

Toma el mismo formato de entrada que el anterior, pero con los papeles de 0s y 1s intercambiado.

La razón por la que necesito convertir esto en un Imageprimero es que, de lo contrario, Mathematica consideraría todas las 1células como parte de un solo componente (porque trata la matriz como una matriz de etiqueta de componente). Por lo tanto, si alguna 1celda bordea el margen, los eliminaría a todos. En DeleteBorderComponentscambio, cuando se usa en una imagen, realizará una comprobación de conectividad implícita para encontrar los componentes.

Alternativamente, podría llamar MorphologicalComponents primero , lo que convertiría la entrada en una matriz de etiquetas adecuada, pero si lo hago en DeleteBorderComponentssegundo lugar, ya no está garantizado que la etiqueta máxima del componente corresponda al número de componentes (porque podría eliminar un componente más pequeño).

Perl 5 , 154 bytes

152 bytes de código + 2 bytes para el -p0indicador.

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

Pruébalo en línea!

Creo que el código se explica por sí mismo.

Si necesita algunas explicaciones para comprender, aquí hay algunos pasos de las transformaciones realizadas por el programa en una entrada simple (proveniente de aquí ), seguidas de algunas explicaciones a continuación:

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

######
# UN
# ####
# # #
#### #
######

######
#AAAAA
#UN####
#UN# #
#### #
######

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

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

Primero, s/^ | $/A/gm;s/^.*\K | (?=.*$)/A/&&redoreemplazará los espacios en el borde (primera expresión regular para izquierda / derecha, segunda para abajo / arriba) con A(elijo ese carácter bastante arbitrario).
Luego, obtenemos el ancho de la forma /.*/;$@="@+"-1;.
Ahora, queremos reemplazar cada espacio que está conectado a a Acon un A(porque si un espacio está conectado a a A, significa que no puede ser parte de un agujero. Eso se hace por for$%(A,X){(s/$%(.?.?.{$@})? /$%$1$%/s||s/ (.?.?.{$@})?$%/$%$1$%/s)&&redo}. (Notará que esto se hace) una vez para la As y otra para la Xs - las explicaciones para la siguiente Xson.) Hay dos expresiones regulares aquí: s/$%(.?.?.{$@})? /$%$1$%/strata con los espacios que están a la derecha o al final de A. AY s/ (.?.?.{$@})?$%/$%$1$%/scon los espacios en la parte superior o izquierda de a A.
En este punto, los únicos espacios que quedan en la cadena son parte de los agujeros.
Si bien todavía hay espacios, repetimos:
- Para saber cuántos agujeros hay, reemplazamos un espacio con a X( s/ /X/) e incrementamos el contador de agujeros ( $\++), y rehace todo el programa (en realidad, solo queremos rehacer el forciclo , pero son menos bytes rehacer todo el programa).
- Luego, el forbucle reemplazará cada espacio que esté conectado a a Xcon a X, ya que son parte del mismo agujero.
Al final, $\|=0asegura que si no hay agujeros, 0se imprime a en lugar de una cadena vacía. Y $\se imprime implícitamente gracias a la -pbandera.

Python 2, 282 bytes

+100 para manejar toques diagonales TT_TT (¿realmente necesitamos eso?)
-119 gracias a la guía de @Rod :)

Pruébalo en línea . Toma una matriz de matrices de caracteres '#' y espacios en blanco como entrada.

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

Busca el primer espacio en blanco y lo marca como no vacío ('#'). Verifique recursivamente todo su entorno, mientras llena todas las celdas vacías. Si alguna celda vacía del "agujero" actual parece estar en el contador de bordes no cambiará, de lo contrario se incrementaría en 1. Repita el proceso, hasta que no haya más espacios en blanco.

Python 2, 233 225 222 bytes

matemática_junkie : -8 bytes

Toma una matriz 2D de booleanos / enteros (0/1) como entrada

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

Pruébalo en línea!

Versión formateada:

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

Menos que contento con esto ... tal vez alguien más pueda resolverlo ... Si tengo la energía más tarde, invertiré el primer bucle y veré si eso puede ayudar a recortar los límites.

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

Pruébalo en línea

Programa completo, acepta entrada a entrada estándar, salida a salida estándar. Utiliza conjuntos disjuntos para determinar los agujeros provisionales, y cuando mata, toca los bordes (con cierta dificultad para el borde superior).

Código formateado y comentado:

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

Caracoles , 48 bytes

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

Sin golf:

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

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>

Basado en mi respuesta a Detect Failing Castles . Primero, la cuerda se rellena con espacios para hacer un área alrededor de la forma. Luego, RegExp busca dos cuadrados adyacentes, uno que contenga un @, otro que contenga un espacio, y los reemplaza a ambos con un @. Si no puede hacer esto, llena un espacio con un @y cuenta esto como un nuevo agujero. Finalmente se resta uno para tener en cuenta el área circundante.