Considere la posibilidad de representar una curva bidimensional simple , abierta en una cuadrícula de texto de ancho W por alto H donde X
representa parte de la curva y .
representa el espacio vacío y no se utilizan otros caracteres.
Cada espacio de cuadrícula tiene 8 espacios de cuadrícula vecinos, su vecindario Moore . Los espacios de cuadrícula más allá de los bordes se consideran vacíos.
Una cuadrícula contiene una curva si tiene exactamente una X
O si tiene más de una X
donde:
- Exactamente dos
X
s tienen solo un vecinoX
. Estos son los puntos finales de la curva. - Todos,
X
además de los puntos finales vecinos, exactamente dosX
s. Estos forman la mayor parte de la curva.
Por ejemplo, esta cuadrícula donde W = 9 y H = 4 contiene una curva:
....X.... .X.X.X.X. X..X..X.X .XX.....X
Del mismo modo, estas cuadrículas (W = 4, H = 3) tienen curvas:
.... .X.. .... .... .X.X .... X..X ..X. XX.. X.X. ..X. .XX. .X.. .... ....
Sin embargo, estas cuadrículas no contienen una curva:
.... .XX. ...X XX.. .... X.X. .... X..X ..XX XX.. .X.X .X.. .... .XX. .X.. .... ...X X.X.
Podemos encontrar la longitud de una curva sumando las distancias entre todos los pares vecinos de X
s:
La distancia entre dos
X
s adyacentes ortogonalmente es 1 unidad.XX
X X
La distancia entre dos
X
s adyacentes en diagonal es √2 unidades.X. .X
.X X.
Por ejemplo, la longitud de la curva en la cuadrícula
XXX. ...X ..X.
se puede visualizar como
entonces podemos ver que es 1 + 1 + √2 + √2 = 4.828427 ...
La longitud de una curva con solo uno X
es cero.
Cuando una cuadrícula no forma una curva, su longitud no está bien definida.
Desafío
Dada una cuadrícula de texto de X
sys .
, muestre la longitud de la curva que contiene, o bien, muestre algo como -1
o Null
para indicar que la cuadrícula no tiene curva.
Para la entrada, puede usar otros caracteres que X
y .
si lo desea, y H y W pueden tomarse como entrada si es necesario. La entrada como una lista anidada o matriz llena de 1s y 0s en lugar de una cadena también está bien.
Puede generar un flotante para la longitud de la curva o, alternativamente, dos enteros A y B donde length = A + B*√2
.
El código más corto en bytes gana.
Casos de prueba
XXX.
...X
..X.
2 + 2*√2 = 4.828427...
....X....
.X.X.X.X.
X..X..X.X
.XX.....X
3 + 8*√2 = 14.313708...
....
....
..X.
0 + 0*√2 = 0
.X..
X..X
.XX.
1 + 3*√2 = 5.242640...
....
..X.
.X..
0 + 1*√2 = 1.414213...
....
XX..
....
1 + 0*√2 = 1
.X.X
X.X.
....
0 + 3*√2 = 4.242640...
....
....
....
....
-1
.XX.
X..X
.XX.
-1
...X
..XX
.X..
-1
....
.X.X
...X
-1
X.X.
.X..
X.X.
-1
fuente
[x.x,...,.x.]
No es una curva válida, ¿verdad?Respuestas:
MATL ,
5251 bytesLa entrada es una matriz de ceros y unos.
La salida es
B
, entoncesA
. Las no curvas dan un negativoA
.Pruébalo en línea! O verificar todos los casos de prueba .
Explicación
Para calcular la longitud de la curva se utilizan dos circunvoluciones 2D 1 : una con la máscara de Moore y otra con una máscara que contiene solo los vecinos diagonales. Los resultados son dos matrices con el mismo tamaño de la entrada, que se denotarán como M y D, respectivamente. M da el número total de vecinos para cada punto, mientras que D da el número de vecinos diagonales.
Los resultados en M y D se deben filtrar para descartar puntos que no pertenecen a la curva. Además, deben dividirse entre 2, porque "ser vecino de" es una relación simétrica, por lo que cada punto de la curva se cuenta dos veces.
Determinar si la curva es válida es más engorroso de lo que esperaba. Para hacer esto, el código prueba tres condiciones:
2
? (Es decir, ¿hay exactamente dos puntos con un solo vecino?)2
menos2
? (Junto con la condición 1, esto prueba si todos los valores distintos de cero en M excepto dos de ellos son iguales2
)La curva es válida si las condiciones 1 y 2 son verdaderas, o si la condición 3 lo es.
1 La convolución es la clave del éxito .
fuente
Python 3 ,
316315311 bytesCreo que esto cubre todos los casos; al menos los casos de prueba funcionan.
Además, seguramente todavía hay mucho para jugar golf, probablemente al principio donde se manejan los casos extremos.
Pruébalo en línea!
Cómo funciona:
d,R,C
son 1. una lista de listas con 1 como curva y 0 como fondo, 2. recuento de filas y columnasd
para que no tengamos que preocuparnos por el borde de la matriz 2dGracias a @Helka Homba por señalar un caso perdido. Gracias a @TuukkaX y @Trelzevir por los consejos de golf.
fuente
d=[[1,0,1],[0,1,0],[1,0,1]]
que fallará aquí (caso de prueba agregado).s=sum
ahorra 4 bytes.Mathematica,
153150 bytesToma una matriz 2D, con
0
s para.
sy1
s paraX
s. SalidasNull
para no curvas.Mathematica tiene una función de 45 bytes incorporada para esto, pero genera algunos números para no curvas y 1 / sqrt (2) para entrada
{{1}}
. Corregir estos costos de 105 bytes (¿podría jugar golf?).fuente