Mientras estamos en una patada de cuadrículas triangulares , me gustaría señalar que hay un equivalente a los poliominós en una cuadrícula triangular. Se llaman poliiamantes , y son formas formadas al pegar triángulos equiláteros a lo largo de sus bordes. En este desafío, usted decidirá qué subconjuntos de una cuadrícula triangular son poliiamantes y si tienen agujeros en ellos. Debido a que solo se necesitan 9 triángulos para hacer un polyiamond con un agujero, su código debe ser lo más corto posible.
La cuadrícula
Utilizaremos el diseño de cuadrícula triangular de Martin para la entrada:
Presta atención al hecho de que los centros de los triángulos forman una cuadrícula aproximadamente rectangular y que el triángulo superior izquierdo "apunta" hacia arriba. Podemos describir un subconjunto de esta cuadrícula, entonces, dando un "mapa estelar" rectangular que indique qué triángulos están incluidos y cuáles no. Por ejemplo, este mapa:
** **
*****
corresponde al poliamond más pequeño que contiene un agujero:
Agujeros
Un polyiamond que contiene un agujero como el ejemplo anterior (una región que no forma parte del polyiamond, que está rodeada por todos lados por regiones que lo son ) no está, topológicamente hablando, simplemente conectado .
El reto
Escriba una función o programa que tome como entrada un "mapa estelar" como se describió anteriormente y genere una verdad si y solo si el subconjunto indicado de la cuadrícula triangular es un poliamond simplemente conectado .
Más ejemplos
*** ***
*******
corresponde al polyiamond
que simplemente está conectado
* *
** **
***
corresponde al polyiamond
que simplemente está conectado
** **
*** **
****
corresponde a la no- polyiamond
que no estaría simplemente conectado incluso si fuera un poliamante.
Especificación de entrada
- La entrada consistirá solo en asteriscos, espacios y saltos de línea.
- El primer carácter de entrada siempre será un espacio o un asterisco (correspondiente al triángulo que apunta hacia arriba en la esquina superior izquierda de la cuadrícula).
- Siempre habrá al menos un asterisco en la primera y última línea.
- NO hay garantía de que las líneas después de la primera línea no estén vacías. Dos avances de línea seguidos pueden aparecer en una entrada legítima.
- Las longitudes de línea no necesitan ser todas iguales.
Condición ganadora
Este es el código de golf , por lo que la respuesta más corta en bytes gana.
Casos de prueba
Mapas de verdad:
1) *
2) *
*
3) **
4) *** ***
*******
5) * *
** **
***
6) *
**
*
7) **
***
****
8) ****
** *
*****
9) ***********
** ** **
**** ** **
**
************
Mapas de falsa:
1) *
*
*
2) * *
3) *
*
4) **
**
5) ***
***
6) ** **
*****
7) ** **
*** **
****
8) *
*
9) *****
** *
*****
fuente
AV VA\nVAVAV
lugar de hacerlo** **\n*****
, ya que facilita la visualización de un humano. Ya hice una edición en uno de los diagramas ASCII de Martin.Respuestas:
Caracoles , 95 bytes
Esto realmente sufrió duplicación, ya que no he implementado macros ni ningún tipo de referencia. Lo que hace es verificar que para cada estrella, exista un camino hacia la estrella más a la izquierda en la línea superior; y para cada espacio, hay un camino hacia un borde de la cuadrícula.
fuente
CJam,
10198 bytesPruébalo en línea.
Finalmente superé mi miedo a implementar un relleno de inundación en CJam. Es tan feo como esperaba, y definitivamente se puede jugar al golf.
La idea general es realizar dos rellenos de inundación (que en realidad se implementan como eliminaciones de la lista de celdas no visitadas). La primera pasada eliminará todos los espacios accesibles desde el borde. La segunda pasada luego elegirá la primera
*
en orden de lectura y eliminará todos los triángulos a los que se pueda llegar. Si y solo si la lista resultante está vacía, el polyiamond simplemente se conectó:fuente