Desafio

Dada a entrada gráfica de uma forma, determine quantos furos existem nela.

Não duplicado

Esta questão foi marcada como uma possível duplicata das Ilhas Conde . Acredito que esse desafio seja diferente do desafio de Count Island porque, neste, você precisa descobrir como eliminar os blocos que tocam a fronteira.

Entrada

A entrada será fornecida como uma forma de entrada 2D, como uma cadeia de linhas múltiplas, uma matriz de cadeias ou uma matriz de matrizes de caracteres. Isso representa a forma. A forma é garantida em apenas uma peça, conectada pela borda. Especifique como deseja que a entrada seja recebida.

Resultado

A saída é um único inteiro informando quantos furos existem na forma. Uma nova linha à direita é permitida, mas nenhum outro espaço em branco à esquerda ou à direita. Em outras palavras, a saída deve corresponder à expressão regular ^\d+\n?$.

O que é um buraco?

Estes são orifícios únicos:

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

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

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

Estes não são buracos:

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

###
#  
###

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

Praticamente, se a lacuna se unir à borda externa, não é um buraco.

Casos de teste

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

Você pode usar qualquer caractere no lugar do '#' e no lugar dos espaços.

Critérios de Pontuação Objetiva

A pontuação é dada como o número de bytes no seu programa.

Ganhando

O vencedor será a finalização com a menor pontuação, até o dia 4 de abril.

MATLAB / oitava, 18 bytes

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

Experimente online!

Esta é uma função anônima que recebe uma matriz lógica como entrada. O objeto é formado pelas trueentradas (com a conectividade especificada), o espaço vazio são as falseentradas.

bweuler depois calcula o número de euler da imagem binária representada por essa matriz, ou seja, o número de objetos menos o número de furos.

Mathematica, 59 57 bytes

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

Há um built-in para isso. Recebe a entrada como uma matriz 2D de 1s (paredes) 0es (furos). Por conveniência, aqui estão todos os casos de teste neste 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}}}

Solução alternativa, 59 bytes

Esta foi a minha abordagem original. Também é baseado nos componentes relacionados ao componente, mas não conta os furos diretamente (em vez disso, trata os furos como componentes).

Max@*MorphologicalComponents@*DeleteBorderComponents@*Image

Tem o mesmo formato de entrada como acima, mas com os papéis de 0s e 1s trocados.

A razão pela qual eu preciso converter isso em um Imageprimeiro é que, caso contrário, o Mathematica consideraria todas as 1células como parte de um único componente (porque trata a matriz como uma matriz de rótulo de componente). Portanto, se alguma 1célula-delimitar a margem, ela excluirá todas elas. Quando DeleteBorderComponentsé usado em uma imagem, ele faz uma verificação implícita de conectividade para encontrar os componentes.

Como alternativa, eu poderia ligar MorphologicalComponents primeiro , o que transformaria a entrada em uma matriz de etiqueta adequada, mas, se o fizer DeleteBorderComponents, não será mais garantido que o rótulo máximo do componente corresponda ao número de componentes (porque eu poderia excluir um componente menor).

Perl 5 , 154 bytes

152 bytes de código + 2 bytes para -p0sinalizador.

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

Experimente online!

Eu acho que o código é bastante auto-explicativo.

Se você precisar de algumas explicações para entender, aqui estão algumas etapas das transformações feitas pelo programa em uma entrada simples (vinda daqui ), seguidas de algumas explicações abaixo:

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

######
# UMA
# ####
# # #
#### #
######

######
#AAAAA
#UMA####
#UMA# #
#### #
######

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

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

Primeiro, s/^ | $/A/gm;s/^.*\K | (?=.*$)/A/&&redosubstituirá os espaços na borda (1º regex para esquerda / direita, 2º para inferior / superior) por A(eu escolho esse caractere bastante arbitrário).
Então, obtemos a largura da forma /.*/;$@="@+"-1;.
Agora, queremos substituir todo espaço conectado a a Apor a A(porque se um espaço estiver conectado a a A, significa que não pode fazer parte de um buraco. Isso é feito por for$%(A,X){(s/$%(.?.?.{$@})? /$%$1$%/s||s/ (.?.?.{$@})?$%/$%$1$%/s)&&redo}. (Você notará que isso é feito uma vez para se Ae um para Xs - explicações para o Xabaixo) Existem dois regex aqui: s/$%(.?.?.{$@})? /$%$1$%/slida com os espaços que estão à direita ou na parte inferior de a A. E s/ (.?.?.{$@})?$%/$%$1$%/scom os espaços na parte superior ou esquerda de a A.
Nesse ponto, os únicos espaços restantes na cadeia de caracteres fazem parte dos furos.
Enquanto ainda existem espaços, repetimos:
- Para saber quantos buracos existem, substituímos um espaço por um X( s/ /X/) e incrementamos o contador de buracos ( $\++) e refazemos o programa inteiro (na verdade, só queremos refazer o forloop , mas são menos bytes para refazer todo o programa).
- Então, o forloop substituirá todo espaço conectado a a Xpor a X, pois eles fazem parte do mesmo furo.
No final, $\|=0garante que, se não houver furos, a 0seja impresso em vez de uma sequência vazia. E $\é implicitamente impresso graças à -pbandeira.

Python 2, 282 bytes

+100 para lidar com toques diagonais TT_TT (realmente precisamos disso?)
-119 graças às orientações @Rod :)

Experimente online . Toma matriz de matrizes de caracteres '#' e espaços em branco 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

Procura o primeiro espaço em branco e o marca como não vazio ('#'). Verifique recursivamente tudo ao redor, enquanto preenche todas as células vazias. Se alguma célula vazia do "buraco" atual parecer estar no contador de borda não será alterada, caso contrário, ela será aumentada em 1. Repita o processo, até que não haja mais espaços em branco.

Python 2, 233 225 222 bytes

math_junkie : -8 bytes

Pega 2d matriz de booleanos / inteiros (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))

Experimente online!

Versão formatada:

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 do que feliz com isso ... talvez alguém possa resolver isso ... Se eu tiver energia mais tarde, inverterei o primeiro loop e ver se isso pode ajudar a reduzir a verificação dos limites.

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

Experimente online

Programa completo, aceita entrada para entrada padrão, saída para saída padrão. Usa conjuntos disjuntos para determinar os furos provisórios e, quando mata qualquer um, toque nas bordas (com alguma desonestidade na borda superior).

Código formatado e 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);
    }
}

Caracóis , 48 bytes

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

Ungolfed:

!{
    (\   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>

Com base na minha resposta para Detectar falha de castelos . Primeiro, a corda é preenchida com espaços para criar uma área ao redor da forma. O RegExp procura então dois quadrados adjacentes, um contendo um @, um contendo um espaço e os substitui por um @. Se não puder fazer isso, preenche um espaço com um @e conta isso como um novo buraco. Finalmente, um é subtraído para dar conta da área circundante.