Antecedentes
Un poliomino se llama L-convexo , si es posible viajar desde cualquier mosaico a cualquier otro mosaico por un camino en forma de L, es decir, un camino que va en las direcciones cardinales y cambia de dirección como máximo una vez. Por ejemplo, el poliomino de 1
s en la figura
0 0 1 1 1 0
1 1 1 1 0 0
1 1 0 0 0 0
no es L-convexo, ya que ambas rutas en forma de L desde la parte inferior izquierda 1
a la superior derecha 1
contienen un 0
:
0>0>1>1>1 0
^ ^
1 1 1 1 0 0
^ ^
1>1>0>0>0 0
Sin embargo, el poliomino de 1
s en esta figura es L-convexo:
0 1 1 1 0 0
1 1 1 1 1 1
0 1 1 0 0 0
Entrada
Su entrada es una matriz 2D de bits en el formato nativo de su idioma, o como una cadena delimitada por una nueva línea si nuestro idioma carece de matrices. Se garantiza que contiene al menos uno 1
.
Salida
Su salida será un valor verdadero si el conjunto de 1
s es un poliomino L-convexo, y un valor falso si no. Estas salidas deben ser consistentes: debe generar el mismo valor verdadero para todas las entradas L-convexas, y el mismo valor falso para otras. Tenga en cuenta que un conjunto desconectado de 1
s (que no es un poliomino) da como resultado una salida falsa.
Reglas y puntuación
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
Estos casos de prueba también deberían funcionar si gira o refleja las matrices, o agrega filas de 0
s a cualquier borde.
False instances
01
10
111
101
111
1101
1111
1110
1100
1000
0011
01100
11110
01110
00110
011000
011110
001111
True instances
1
01
11
010
111
010
001
011
111
11100
11110
01100
01000
011000
011000
111100
111111
001000
Respuestas:
Caracoles ,
4524Justo después de publicar mi solución inicial, me di cuenta de que había una manera mucho mejor. El programa original viajó alrededor del cuadrado formado por los caminos entre dos
1
s, probando la presencia de un 0 en cada par de lados. También tenía que tener un caso especial para rutas de línea recta. La nueva versión comienza teletransportándose de uno1
a otro y probando la ausencia de una ruta recta o en forma de L de1
s de regreso al inicio.fuente
Matlab, 182 bytes
Idea: Repita para cada
1
en la matriz de poliomino:1
pero el resto cero.1
en esta nueva matriz (repita hasta que ya nada cambie)1
como vecinos en la dirección x si hay1
como vecinos en el polinomio1
en esta nueva matriz (repita hasta que ya nada cambie)1
como vecinos en la dirección x si hay1
como vecinos en el polinomioAhora,
1
en la nueva matriz debe cubrir todo1
en la matriz de polinomio a la que se puede llegar desde el punto de partida dado yendo primero en la dirección xy luego en la dirección y. Ahora podemos repetir el mismo proceso pero primero yendo en la dirección y y luego en la dirección x. Ahora se1
debe alcanzar cada una de las matrices de poliomino a la vez o ambas veces. Si no es así, entonces hemos encontrado una posición en la matriz de polinomio que no puede ser alcanzada desde cualquier otra posición mediante unaL
ruta.Golfizado:
Con comentarios:
Script de casos de prueba:
fuente
Javascript ES6, 290 bytes
Ok, tal vez no gane ningún premio por brevedad, pero sí utiliza un enfoque novedoso. Vea la versión sin golf de cómo funciona.
La prueba de este método se puede encontrar en: Autómatas celulares y sistemas complejos discretos .
Sin golf:
fuente
Mathematica,
129127 bytesExplicación:
Primero, si hay
0
entre dos1
s en la misma fila o columna, la matriz no es L-convexa, porque no podemos conectar los dos1
s.Después de excluir este caso, cada dos
1
s en la misma fila o columna se pueden conectar por una ruta recta. Podemos generar un gráfico, cuyos vértices son las posiciones de1
s en la matriz, y los bordes son pares de1
s en la misma fila o columna. Entonces la matriz es L-convexa si y solo si el diámetro del gráfico es menor que 3.fuente
JavaScript (ES6) 174
Mirando la cuadrícula de celdas vacías o llenas, para cualquier par de celdas llenas verifico las rutas horizontales a la otra columna de celdas (puede haber 1 si las celdas están en la misma fila, de lo contrario o 2) y las rutas verticales a la otra fila de celdas (puede haber 1 o 2 también). Si encuentro una celda vacía en ambas rutas verticales o en ambas rutas horizontales, entonces no puede haber una ruta en forma de L entre las celdas.
(Me costó mucho tratar de poner esta explicación, espero haber sido claro)
Pruebe a ejecutar el fragmento a continuación en cualquier navegador compatible con EcmaScript 6
fuente