Enquanto estamos em um chute de grade triangular , eu gostaria de salientar que existe um equivalente a poliomanos em uma grade triangular. Eles são chamados de diamantes e são formas formadas pela colagem de triângulos equilaterais ao longo de suas bordas. Neste desafio, você decidirá quais subconjuntos de uma grade triangular são diamantes e se eles têm orifícios. Como são necessários apenas 9 triângulos para criar um poliamino com um orifício, seu código precisa ser o mais curto possível.

A grade

Usaremos o layout da grade triangular de Martin para a entrada:

Preste atenção ao fato de que os centros dos triângulos formam uma grade aproximadamente retangular e que o triângulo superior esquerdo "aponta" para cima. Podemos descrever um subconjunto dessa grade, fornecendo um "mapa em estrela" retangular indicando quais triângulos estão incluídos e quais não estão incluídos. Por exemplo, este mapa:

** **
*****

corresponde ao menor poliamino que contém um orifício:

Furos

Um poliamantado que contém um orifício como o exemplo acima (uma região que não faz parte do poliamantino, que é cercada por todos os lados por regiões que são ) não é, topologicamente falando, simplesmente conectado .

O desafio

Escreva uma função ou programa que tenha como entrada um "mapa estelar" como descrito acima e produza uma verdade se e somente se o subconjunto indicado da grade triangular for um poliamantado simplesmente conectado .

Mais exemplos

*** ***
*******

corresponde ao poliamino

que está simplesmente conectado.

*   *
** **
 ***

corresponde ao poliamino

que está simplesmente conectado.

**  **
*** **
 ****

corresponde ao não- diamante

que não seria simplesmente conectado, mesmo que fosse um poliamantino.

Especificações de entrada

• A entrada consistirá apenas em asteriscos, espaços e feeds de linha.
• O primeiro caractere da entrada sempre será um espaço ou asterisco (correspondente ao triângulo apontando para cima no canto superior esquerdo da grade).
• Sempre haverá pelo menos um asterisco na primeira e na última linha.
• Não há garantia de que as linhas após a primeira linha não estejam vazias. Dois feeds de linha em uma linha podem aparecer em uma entrada legítima.
• Os comprimentos das linhas não precisam ser todos iguais.

Condição vencedora

Isso é código-golfe , então a resposta mais curta em bytes vence.

Casos de teste

Mapas de verdade:

1) *

2) *
   *

3) **

4) *** ***
   *******

5) *   *
   ** **
    ***

6) *
   **
    *

7)    **
     ***
   ****

8) ****
   **   *
    *****

9) ***********
   **    **  **
    ****  **  **
              **
   ************

Mapas de falsidade:

1) *
   *
   *

2) * *

3) *
    *

4)  **
   **

5) ***

   ***

6) ** **
   *****

7) **  **
   *** **
    ****

8)  *
    *

9) *****
   **   *
    *****

Caracóis , 95 bytes

F&
lr|=((ul.)2 ,l~a~)d|!((ul.)2 ,l~a~)u}\*}+l\ ,~a~|{\ (lr|=((ul.)2 ,l~a~)d|!((ul.)2 ,l~a~)u}+~

Isso realmente sofreu com a duplicação, pois eu não implementei macros ou qualquer tipo de referência posterior. O que faz é verificar se, para cada estrela, existe um caminho para a estrela mais à esquerda na linha superior; e para cada espaço, há um caminho para uma borda da grade.

F&                         ,, option F: pad lines with spaces to the length of the longest
                           ,, option &: print 1 iff match succeeds from every cell
lr                         ,, direction left or right, or
      | =((ul.)2 ,l~a~) d  ,, direction down, if we are an even number of orthogonal moves from the top left
      | !((ul.)2 ,l~a~) u  ,, or, direction up if we are odd number of moves from the top left
    }  \*                  ,, literal '*'
}+                         ,, 1 or more times
l\ ,~a~                    ,, check that we are on the leftmost * in the top line

|                          ,, the part before this is for starting on '*'; part after for starting on ' '

{ \                        ,, literal ' '
    (   lr                 ,, direction left or right, or
      | =((ul.)2 ,l~a~) d  ,, same drill as before...
      | !((ul.)2 ,l~a~) u 
}+                         ,, 1 or more times
~                          ,, end on an out of bounds cell

CJam, 101 98 bytes

qN/_z,f{' e]}{S2*f+W%z}4*:eeee::f+:~{_(aL{+_{_2,.+1$2,.-@_:+1&!2*(a.+}%2${a1$&},\;@1$-@@}h;\;-}2*!

Experimente online.

Finalmente, superei meu medo de implementar um preenchimento de inundação no CJam. É tão feio quanto eu esperava, e definitivamente pode ser jogado no golfe.

A idéia geral é realizar dois preenchimentos (que são realmente implementados como remoções da lista de células não visitadas). A primeira passagem removerá todos os espaços acessíveis da borda. A segunda passagem selecionará a primeira *em ordem de leitura e removerá todos os triângulos alcançáveis. Se, e somente se, a lista resultante estiver vazia, o poliamantado estava simplesmente conectado:

• Se o poliamantino tiver um orifício, o primeiro preenchimento de inundação não poderá alcançar e remover esse orifício.
• Se a entrada consistir em vários poliamantes desconectados, o segundo preenchimento de inundação não poderá alcançar e remover todos eles.