Fondo
Tengo un montón de viejas y granuladas imágenes en blanco y negro. Algunos de ellos representan enredaderas trepando por una pared, otros no; su tarea es clasificarlos por mí.
Entrada y salida
Su entrada es una matriz rectangular 2D de bits A , dada en cualquier formato conveniente. No estará vacío, pero no se garantiza que contenga 0s y 1s. La matriz representa una vid si se cumplen las siguientes condiciones:
- La fila inferior de A contiene al menos uno 1. Estas son las raíces de la vid.
- Cada 1 en A está conectado a la fila inferior por una ruta de 1s que solo va a la izquierda, derecha y abajo (no arriba y no diagonalmente). Estos caminos son las ramas de la vid.
Su salida es un valor de verdad consistente si la entrada representa una viña, y un valor de falsedad consistente de lo contrario.
Ejemplos
Esta matriz representa una vid:
0 0 1 0 0 1
0 1 1 0 0 1
0 1 0 1 1 1
1 1 0 1 0 1
0 1 1 1 0 1
0 0 1 0 1 1
Esta entrada no representa una viña, ya que hay un 1 en el medio del borde derecho que no está conectado a las raíces por una rama:
0 0 0 1 1 0
0 1 0 1 1 1
0 1 0 1 0 1
0 1 1 1 1 0
0 0 1 1 0 1
La matriz all-0 nunca representa un vine, pero la matriz all-1 siempre lo hace.
Reglas y puntaje
Puede escribir un programa completo o una función. El conteo de bytes más bajo gana, y las lagunas estándar no se permiten.
Casos de prueba
Entradas de verdad:
1
0
1
1
01
11
0000
0111
1100
1001
1111
1111
1111
1111
001001
011001
010111
110101
011101
001011
1011011
1001001
1111111
0100000
0111111
1111001
1001111
1111101
0000000
0011100
0010100
0011100
0001000
1111111
0001000
0011100
0010100
0010100
Entradas de falsa:
0
1
0
10
01
000
000
000
011
110
000
111111
000000
101011
111001
010010
001000
000010
110001
001100
111111
110101
010011
111011
000110
010111
010101
011110
001101
11000000
10110001
10011111
11110001
01100011
00110110
01101100
01100001
01111111
fuente
Respuestas:
Caracoles ,
251917 bytesPruébalo en línea!
Explicación
Snails es un lenguaje de coincidencia de patrones 2D inspirado en regex, que fue desarrollado originalmente para nuestro desafío de diseño de lenguaje de coincidencia de patrones 2D .
Esto
&
hace que Snails pruebe el patrón desde todas las posiciones de inicio posibles e imprime0
o1
dependiendo de si el patrón falla en alguno de ellos o coincide en todos ellos.Ahora Snails puede trabajar con paréntesis implícitos, por lo que el patrón es la abreviatura de lo siguiente:
El
,
actúa como una*
en expresiones regulares (es decir, cero o más veces), mientras que el+
es el mismo que en expresiones regulares (que coincida con una o más veces). Entonces, comenzamos haciendo coincidir las\0z
veces que sea necesario, que coincide con un solo0
y luego permite que el caracol restablezca su dirección arbitrariamentez
. Esto permite ceros en la entrada, siempre que se pueda encontrar una celda de vid válida en cualquier otro lugar.Luego emparejamos al menos uno
\1dlr
, que coincide con uno solo1
y luego permite que el caracol restablezca su dirección hacia abajo, hacia la izquierda o hacia la derecha. Tenga en cuenta que si la celda en la que comenzamos contiene un,1
entonces solo estamos haciendo coincidir esta parte. Básicamente permite que el caracol atraviese una vid desde una rama hasta las raíces.Finalmente, debemos asegurarnos de llegar al suelo buscando una celda fuera de los límites (
~
) debajo (d
).fuente
JavaScript (ES6), 135 bytes
Nota: Debido a las limitaciones del tipo entero, solo funciona para vides de hasta 31 caracteres de ancho. Explicación: Cada fila se ANDA bit a bit con la fila adyacente para determinar los puntos de conexión, y luego la
g
función se usa para expandir recursivamente la fila horizontalmente hasta que ya no pueda expandirse. Por ejemplo, si dos filas adyacentes son1110111
y1011100
luego los puntos de conexión son1010100
y esto se expande1110110
y luego1110111
se encuentra que la fila está conectada. Si lag
función falla, devuelve cero, lo que hace que todas lasg
funciones posteriores también fallen, y el resultado es falso. Si lag
función tiene éxito, devuelve la nueva fila que luego se propaga a través dereduce
para probar la siguiente fila.fuente
Python 2, 254 bytes
No hay bibliotecas
Tenga en cuenta que las sangrías de segundo y tercer nivel se forman con pestañas en el recuento de bytes.
Pruébalo en línea
fuente
Wolfram - 254
Dedique un tiempo a hacer que esto funcione, así que lo dejaré aquí:
Básicamente, construyo un gráfico de cuadrícula con los bordes dirigidos hacia arriba, elimino los vértices que corresponden a 0, compruebo que los componentes del vértice inferior contengan todos los vértices. Ridículo, lo sé ...
fuente
Python + NumPy
204202195 BytesEspera
A
ser una matriz numpy 2D.Toma la matriz, rellena cero columnas a izquierda y derecha y aplana la matriz.
s
es una plantilla que apunta al elemento izquierdo, derecho e inferior. El bucle verifica cada elemento, excepto la última línea, si es así,1
y al menos una de sus plantillas es1
, devuelve loFalse
contrario. Luego, verifique si la última línea contiene alguna1
.Dos casos de prueba para ti:
Edit1:
1<0
es más corto queFalse
Edit2:
flat
es una buena alternativaflatten()
y uso de tabuladores para la segunda intención en el buclefuente