40

Uno de los aspectos interesantes de la gravedad es que, hasta donde yo sé, no puedes tener cosas flotando en el aire.

Sin embargo, parece que no todos en la Asociación de Constructores de Castillo Aleatorio son conscientes de este hecho, lo que lleva a castillos como este:

                      #
                      #
    #  #      #  #   ###
    ####      ####   # #
    #### #  # ####   ###
    ##############   ###
    ######  ######   ###
    #####    #####   ###
                     ###
``````````````````````````````

y éste:

                                       # # #    # # #   
                                       ##############
                                       ###  ####  ###
    #  #      #  #      #  #      #  # ###  ####  ### #  #      #  #      #  #      #  #
    ####      ####      ####      #### ############## ####      ####      ####      ####
    #### #  # #### #  # #### #  # #### ## ######## ## #### #  # #### #  # #### #  # ####
    ####################################################################################
    ######  ########  ########  ########  ########  ########  ########  ########  ######
    ###################################    ######    ###################################
    ###################################    ######    ###################################
                                       ##
                                         ##
                                           ##
                                             ##
                                               ##
````````````````````````````````````````````````````````````````````````````````````````````

e incluso este:

       ##########
   ####   #      ###
#######################
            #
              #
                #
                  #
                    #  # # #
                  #   #  ###
                   #   # ###
                # # #  #  ##
                # # ##   ###
                 #  #  #####
                   #   #####
                  # #  #####
                       #####
                       ## ##
                       #####
                       #####
                       ## ##
                       ## ##
````````````````````````````````````````````

Reto

Para un castillo válido, todos los bloques estarán conectados al suelo, ya sea directa o indirectamente. Su programa o función recibirá un castillo como los anteriores como entrada, y su programa debe devolver un valor verdadero o falso que refleje si el castillo es válido o no.

Reglas

La entrada se da como una cadena.
Todos los castillos válidos descansan sobre una superficie, ````````. (Si la cadena de entrada no contiene una superficie, el castillo no es válido).
Puede suponer que todas las entradas satisfarán estos criterios:
- La superficie siempre será plana.
- La superficie siempre será al menos tan ancha como el castillo, por lo que no habrá bloques a la izquierda o derecha del suelo.
- La entrada nunca tendrá #debajo de la superficie.
- La entrada solo contendrá caracteres dados en este desafío. ( #, `espacio o nueva línea).
- Puede suponer que la entrada siempre contendrá al menos un carácter.
Los bloques están conectados si son adyacentes horizontal o verticalmente. Diagonal no cuenta!
- Conectado:
```
#	or	##
#
```
- No conectado:
```
#      or	# #	or	 #
                  		#
#
```
Los castillos deben existir para ser válidos. (En otras palabras, las entradas sin ninguna #deben dar un valor falso).
La entrada solo contendrá caracteres dados en este desafío. ( #, `espacio o nueva línea).
Puede suponer que la entrada siempre contendrá al menos un carácter.
Se aplican las reglas estándar de E / S y lagunas .

Casos de prueba

Falsa

Todos los ejemplos dados anteriormente.

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

(Sin suelo)

# 
### #### 
#### # # #### 
############## 
###### ###### 
##### # #### 
`` `` `` `` `` `` ``

(El bloque superior no está conectado ni horizontal ni verticalmente).

```
   
`` `
```
(Sin castillo)



                                     # # # # # #    
                                     ############## 
                                     ##### ## ##### 
  # # # # # # # # #### # # #### # # # # # # # # 
  #### #### #### #### ## #### ## #### #### #### #### 
  ## ## # # #### # # #### # # #### # # #### # # #### # # #### # # #### # # #### 
  ################################################## ################################## 
  ###### ######## ## ###### ######## ######## ######## ######## ######## #### ## 
  ################################### ###### ####### ############################
  ################################### ###### ######### ########################## 
`` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` ``

(La torre central no está conectada con el resto del castillo porque no hay bloques adyacentes horizontal o verticalmente que lo conecten).

```
   
```
(Sin castillo)
(Sin castillo, solo un personaje de nueva línea).
```
# # 
# 
`` `` `` `
```
(El bloque de la derecha no está conectado ni horizontal ni verticalmente).
```
   
`` `
```
(Sin castillo)

Verdad

```
# 
`
```

# # # # 
#### #### 
#### # # #### 
############## 
###### ###### 
## ### ##### 
`` `` `` `` `` `` ``

                      # 
                      # 
    # # # # ### 
    #### #### # # 
    #### # # #### ### 
    ############## ### 
    # ##### ###### ### 
    ##### ##### ### 
    ##### ##### ### 
`` `` `` `` `` `` `` `` `` `` `` `` `` `` ``

                                       # # # # # #    
                                       ############## 
                                       ### #### ### 
    # # # # # # # # ### #### ### # # # # # # # # 
    #### #### #### #### ############## #### #### #### ## ## 
    #### # # #### # # #### # # #### ## ######## ## #### # # #### # # ## ## # # #### 
    ########################################## ########################################## 
    ###### ## ###### ######## ######## ######## ######## ######## #### #### 
    ###### ################################### ##### # ###################################
    ################################### ###### ######### ########################## 
`` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` ``

                      #### ### 
                      # #### ### 
                      # ### 
                      # ## 
                      # 
                     ### 
                    ##### 
                   ####### 
                  ######### 
                 ### ## ##### 
                ##### ##### 
               ###### ###### 
              ################# 
              # ### ########## # 
                ############# 
                ############# 
                ############# 
                ###### ###### 
                ###### ###### 
                #############
                ############# 
                ############# 
                ############# 
                ###### ##### # 
                ###### ###### 
                ############# 
                ############# 
                ########### ## 
                ############# 
                ###### ###### 
                ###### ###### 
                ########### ## 
                ############# 
                ############# 
                ############# 
                ######### #### 
                ##### ##### 
                ##### ##### 
                ##### ##### 
            `` `` `` `` `` `` `` `` `` `` `

                                                
                                          ####   
                                         #####   
                                        ######   
                                         ####    
                                         ####    
                                        #####    
                                       ######## 
                                      ########## 
                                      #### ###### 
                                     ########### 
                                    ############ 
                                  ############## 
   ##### ## ############## 
  ########### #################  
  ###########################################    
   ####### #################################      
    ################# ####################        
     ############################## ####          
        ############################             
            ################## #                  
`` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` ` ``

¡Buena suerte!

code-golf ascii-art decision-problem usuario2428118
fuente

¿Podemos suponer que todas las líneas de la entrada tendrán la misma longitud (es decir, se rellenarán con espacios)?

sonríe

@smls No, no puede asumir que la entrada se rellenará.

user2428118

1

@smls Re # 1 y # 2: en realidad tenía la intención de especificar que las presentaciones no tienen que manejar eso, pero ahora veo que no es así como lo escribí. Como todavía no hay soluciones publicadas que manejen estas cosas, actualizaré la pregunta para que quede claro que no tiene que manejarlas. Re # 3: Realmente no puedo pensar en una situación en la que el código manejaría correctamente los casos de prueba Falsy 2, 4 y 6 y aún así no pueda detectar una situación en la que no haya bloques conectados al suelo. Re # 4: No estoy seguro de lo que quieres decir con eso. ¿No es eso ya manejado por el caso de prueba Truthy número 1?

user2428118

1

Relacionado.

Zgarb

2

¿Un castillo de plátano? MEJOR CASTILLO DE LA VIDA

Matthew Roh

11

Caracoles , 21 18 bytes

-3 bytes debido a restricciones de entrada adicionales editadas en desafío.

!{t=\#!(\#o`+\`}\#

Desafortunadamente, la complejidad del tiempo es factorial, por lo que la mayoría de las entradas no son ejecutables.

Salidas 0 para casos falsos, y el número de #casos verdaderos.

                 ,,
!{ t             ,, Assert that nowhere in the grid,
    =\#          ,, there is a '#'
    !(           ,, such that there does not exist
        (\# o)+  ,, an orthogonally connected path of '#'
        \`       ,, ending at a '`'
    )            ,,
}                ,,
\#               ,, Match '#' at starting position

Feersum
fuente

Esto no reconoce el ejemplo que publicaste en la respuesta de Zgarb como castillo. ¿No veo nada en las reglas que diga que estos no deberían ser detectados como castillos? Las reglas solo dicen que es un castillo si cada uno #está conectado al suelo.

Martin Ender

@Zgarb No, hay un error en la explicación: en +realidad es 1 o más veces, no 0. Se verá diferente de todos modos después de permitir castillos desconectados.

feersum

9

Octava, 53 51 bytes

@(s)([~,n]=bwlabel(s>32,4))|n==1&&nnz(diff(+s)==61)

¡Pruébelo en línea!

* Desde que op eliminó el requisito de verificar la respuesta de entrada vacía, volví a mi primera edición.

Explicación:

nnz(s)                       check for empty input
([~,n]=bwlabel(s~=' ',4))    label nonempty regions and count number of labels

n==1                         check if number of labels is 1.

nnz(diff(+s)==61)            check if blocks connected to the surface

rahnema1
fuente

6

Grime , 29 bytes

C=\`|\#&<0C>oX
e`\#&C!v#!&\##

Pruébalo en línea! La mayoría de los casos de prueba caducan en TIO. Reemplace <0C>con <0CoF>para hacerlo un poco más rápido.

Explicación

Estoy comprobando que desde cada #lugar existe un camino hacia a `, y que existe al menos uno #. Recientemente agregué comandos de rotación a Grime, que hacen que este desafío sea mucho más fácil.

C=\`|\#&<0C>oX  First line:
C=               Define nonterminal C as
  \`             the literal `
    |            or
     \#          the literal #
       &<  >     which is contained in a larger rectangle
         0C      containing said literal adjacent to a match of C
            oX   rotated by any multiple of 90 degrees.
e`\#&C!v#!&\##  Second line:
e`               Match entire input against this pattern:
         !       does not
       v#        contain
  \#             the literal #
    &C!          which is not a match of C,
          &      and
             #   contains
           \#    the literal #.

Zgarb
fuente

6

JavaScript (ES6), 197 196 bytes

f=(s,l=Math.max(...s.split`\n`.map(t=>t.length)),t=s.replace(/^.*/g,t=>t+' '.repeat(l-t.length)),u=t.replace(eval('/(#|`)([^]{'+l+'})?(?!\\1)[#`]/g'),'`$2`'))=>t==u?/#/.test(s)>/#/.test(t):f(s,l,u)

Donde \nrepresenta el carácter literal de nueva línea. Intenta eliminar todas las #s una a la vez encontrando una adyacente a a `y cambiándola a a `. Devuelve truesi hubo al menos uno #originalmente pero todos fueron eliminados. Versión que requiere entrada acolchada para ~~118~~ 117 bytes:

f=(s,t=s,u=t.replace(eval('/(#|`)([^]{'+s.search`\n`+'})?(?!\\1)[#`]/'),'`$2`'))=>t==u?/#/.test(s)>/#/.test(t):f(s,u)

Neil
fuente

5

Perl 6 , 180 bytes

{?/\#/&&?all map ->\c{my \b=[map {[$^a.comb]},.lines];sub f(\y,\x){with b[y;x] ->$_ {b[y;x]=0;/\#/??f(y+(1|-1),x)|f(y,x+(1|-1))!!/\`/??1!!|()}}(|c)},map {|($++X ^$^a.comb)},.lines}

Comprueba si la entrada contiene al menos uno #, y si todos #pueden encontrar una ruta a a `.

Más bien ineficiente, porque la búsqueda de ruta es forzada por la fuerza bruta utilizando una función recursiva que siempre visita todas las demás #regiones conectadas (es decir, no produce un cortocircuito).

Utiliza alguna interacción impía entre los operadores de unión y el deslizamiento , para garantizar que la prueba de ruta se omita para los caracteres de espacio sin requerir una verificación por separado fuera de la función de búsqueda de ruta.

smls
fuente

5

Python 3 , 214 206 bytes

def f(s):
 C=s.split('\n');n=max(map(len,C));o=[''];C=[*''.join(t.ljust(n)for t in C+o)]
 while C>o:o=C;C=['`'if z>' 'and'`'in{C[i+y]for y in(1,-1,n,-n)}else z for i,z in enumerate(C)]
 return'#'in{*s}-{*C}

Pruébalo en línea!

La primera línea aquí está dedicada a rellenar todas las líneas con la misma longitud: dividimos la cadena ( s.split('\n')es un carácter más corto que s.splitlines()), encontramos la longitud máxima de una línea y asignamos a C una lista aplanada de todos los caracteres después de rellenar cada línea. (Las nuevas líneas se han ido).

Luego, hacemos una lista en la que cada carácter no espacial adyacente a al menos un backtick se reemplaza por un backtick, y continuamos hasta que no ocurra ningún cambio (cuando la lista anterior oes igual a C. Podemos comparar en C>olugar de C!=oporque reemplazamos # (ASCII 35 ) con `(ASCII 96) solo puede aumentar el orden lexicográfico de la lista).

Si no queda ningún #, y al menos uno estaba presente inicialmente, el castillo es válido.

Se guardaron ocho bytes buscando # en la diferencia establecida, en lugar de '#'in s and'#'not in C

Nick Matteo
fuente

Detectar castillos defectuosos