Su tarea es determinar la longitud del descenso más largo por una "montaña" representada como una cuadrícula de alturas enteras. Un "descenso" es cualquier camino desde una celda inicial a celdas adyacentes ortogonalmente con alturas estrictamente decrecientes (es decir, no diagonal y no a la misma altura). Por ejemplo, puede pasar de 5-4-3-1 pero no 5-5-4-3-3-2-1. La longitud de esta ruta es cuántos movimientos de celda hay desde la celda inicial hasta la celda final, por lo tanto, 5-4-3-1 es la longitud 3.
Recibirá una cuadrícula rectangular como entrada y debería generar un número entero que indique el descenso más largo.
Ejemplos
1 2 3 2 2
3 4 5 5 5
3 4 6 7 4
3 3 5 6 2
1 1 2 3 1
La longitud del descenso más largo por esta montaña es 5. El camino más largo comienza en el 7, se mueve hacia la izquierda, arriba, izquierda, arriba y luego a la izquierda (7-6-5-4-2-1). Como hay 5 movimientos en esta ruta, la longitud de la ruta es 5.
Pueden ser todos el mismo número.
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
Como este mapa de altura es plano, el descenso más largo es 0. (no 19, ya que la secuencia de la ruta debe ser estrictamente descendente)
Los mapas de altura pueden estar formados por números más grandes que los números de un solo dígito.
10 12 13 14 15 15
17 14 15 15 15 16
18 20 21 15 15 15
21 14 10 11 11 15
15 15 15 15 15 15
El camino más largo aquí es de longitud 6. (21, 20, 18, 17, 14, 12, 10)
... e incluso números más grandes también están bien.
949858 789874 57848 43758 387348
5848 454115 4548 448545 216464
188452 484126 484216 786654 145451
189465 474566 156665 132645 456651
985464 94849 151654 151648 484364
El descenso más largo aquí es de longitud 7. (786654, 484216, 484126, 474566, 156665, 151654, 151648, 132645)
Reglas y notas
- Las cuadrículas se pueden tomar en cualquier formato conveniente. Especifique su formato en su respuesta.
- Puede suponer que el mapa de altura es perfectamente rectangular, no está vacío y contiene solo enteros positivos en el rango de enteros de 32 bits con signo.
- El camino de descenso más largo puede comenzar y terminar en cualquier lugar de la cuadrícula.
- No necesita describir el camino de descenso más largo de ninguna manera. Solo se requiere su longitud.
- El código más corto gana
Respuestas:
JavaScript (ES7),
106 103 10298 bytesPruébalo en línea!
Comentado
¿Cómo?
Durante la primera iteración, , y están todos indefinidos y ambas pruebas ( A y B en los comentarios) evalúan a NaN , lo que desencadena la llamada recursiva. Por lo tanto, todas las celdas se consideran como un posible punto de partida de la ruta.x y p
fuente
Gelatina ,
23 2120 bytes-2 gracias a Erik the Outgolfer
Pruébalo en línea! (Demasiado ineficiente para los ejemplos: la ruta aquí es
95 94 93 83 77 40 10
así que se6
produce)¿Cómo?
fuente
Python 2,
150147140136134132125123120 bytesPruébalo en línea!
Toma entrada en forma de diccionario
(x, y): value
.-7 bytes gracias a wizzwizz4, -2 bytes gracias a Jonathan Allen, -2 bytes gracias a BMO
Alternativa,
123121 bytesPruébalo en línea!
Esencialmente, la misma solución, solo con el lambda final reemplazado por un programa real. Personalmente, me gusta más el primero, pero este se acerca al recuento de bytes al permitir
g
que se use como una variable global.fuente
Limpio ,
211207 bytesPruébalo en línea!
Una solución de fuerza bruta que toma una lista de listas de enteros (
[[Int]]
).El controlador TIO toma el mismo formato que los ejemplos a través de STDIN.
Es demasiado lento ejecutar cualquiera de los ejemplos en TIO y probablemente también localmente, pero funciona en teoría.
Éste hace lo mismo más rápido, puede hacer 3x3 o 2x4 en TIO y 4x4 y 3x5 localmente.
Sangrado:
fuente
Python 3 , 219 bytes
Pruébalo en línea!
La cuadrícula se representa como una lista de listas:
Código original sin golf:
fuente
Haskell ,
188186 bytesPruébalo en línea!
notElem
(not.).(#)
Pruébalo en línea!
Explicación y Ungolfed
Estrategia: intente recurrentemente todos los caminos posibles, realice un seguimiento de las entradas visitadas y maximice su longitud.
elem
notElem
(#)
elem
maximize
Ahora estamos listos para definir nuestra función recursiva
fun :: [[Integer]] -> Integer
:fuente
[[Integer]]
es una lista de listas. Aunque en el TIO vinculado tienes un contenedorparse :: String -> [[Integer]]
, st. puede usar cadenas divididas en espacios y nuevas líneas.Python 3,
263227 bytesPruébalo en línea!
-2 bytes gracias a BMO
Toma cuadrículas en el formato
{(0, 0): 1, (1, 0): 2, ...}
. Este formato se puede generar a partir del formato de ejemplo utilizando la siguiente función de utilidad:fuente