Escriba una función (utilizando la menor cantidad de bytes posible) que tome una matriz bidimensional de cualquier número de columnas y filas en las que:
0
representa bloque vacío,1
representa el bloque de serpiente.
La función debe devolver el número de caminos posibles que recorrió la serpiente.
Ejemplo 1:
Entrada:
[
[1,1,1,1,1],
[0,0,0,0,1],
[0,0,0,0,1],
]
Salida: 2
En el ejemplo anterior, la función regresará 2
porque la respuesta es una de:
Ejemplo 2
Entrada:
[
[1,1,1,1],
[0,0,1,1],
[0,0,1,1],
]
Salida: 6
En este ejemplo, la función regresará 6
porque la respuesta es una de:
Nota:
Al evaluar la entrada, puede suponer que:
- Las matrices que representan columnas siempre tendrán los mismos tamaños (por lo que las matrices son rectangulares);
- Existe al menos 1 ruta válida;
- La serpiente no puede caminar a través de los bordes (como puede suceder en algunas versiones de serpiente);
- La serpiente siempre tendrá al menos 2 bloques;
- La serpiente no puede moverse en diagonal;
- Los caminos están dirigidos. (por lo tanto, dos rutas que terminan en diferentes posiciones pero que se ven exactamente iguales no son la misma ruta, se sumarán al total)
code-golf
grid
binary-matrix
Adelin
fuente
fuente
[[0,0,1,1],[0,0,1,1],[0,0,1,1]]
. La mayoría de las respuestas dan 16, pero una da 15.Respuestas:
Wolfram Language (Mathematica) , 16 + 83 = 99 bytes
Declaración de importación de biblioteca (16 bytes):
Cuerpo de función real (83 bytes):
Pruébalo en línea!
Tenga en cuenta que la pregunta solo pide el número de ruta hamiltoniana en el gráfico.
Sin embargo, (por alguna razón) la
HamiltonianPath
función realmente no funciona con el gráfico dirigido ( ejemplo ). Entonces, utilicé la solución descrita en esta pregunta de Mathematica.SE :True
) que esté conectado a todos los demás vértices.El gráfico se construye usando
MakeGraph
(molestamente, no hay una función incorporada directamente equivalente), usando la función booleana##||Norm[#-#2]==1&
, que devuelveTrue
si y solo si uno de los argumentos esTrue
o la distancia entre los dos vértices es1
.Tr[1^x]
no se puede usar en lugar deLength@x
, y<2
no se puede usar en lugar de==1
.HamiltonianPath
se puede usar si el gráfico no está dirigido, con el cuerpo de la función toma 84 bytes (exactamente 1 byte más que el envío actual):Pruébalo en línea!
fuente
JavaScript (ES6),
154134bytesPruébalo en línea!
¿Cómo?
Método
Comenzando desde cada celda posible, inundamos la matriz, limpiando todas las celdas en nuestro camino. Siempre que la matriz no contenga más 1 's, incrementamos el número n de posibles caminos.
Cada ruta válida se cuenta 4 veces debido a la dirección elegida en la última celda, que en realidad no importa. Por lo tanto, el resultado final es n / 4 .
Función recursiva
En lugar de llamar a la función recursiva g () desde la devolución de llamada del segundo mapa () de esta manera ...
... definimos la función recursiva g () directamente como la devolución de llamada de map () :
A pesar de la fórmula bastante larga
y=1/y?y:Y
que se necesita para establecer el valor inicial de y , esto ahorra 2 bytes en general.Código comentado
fuente
Jalea ,
1211 bytesPruébalo en línea!
Explicación.
fuente
§ỊML
lugar de§ỊP€S
guardar un byte? Creo que debería funcionar.§ÐṂL
que es un poco más rápido.Pitón 2 ,
257246241234233227214210 bytesPruébalo en línea!
Salvado
fuente
w
yh
Python 2, 158 bytes
Pruébalo en línea!
fuente
Haskell ,
187155 bytesPruébalo en línea!
fuente