Carrera de "¡Baja la escalera!"

propuesto por josejuan

Una variante que convierte al popular juguete en una carrera de la que debes calcular las mejores rutas de los corredores.

Enunciado
(Desafío inspirado en el problema 79 "Triangle Minimal Path" de 4clojure)

"¡Baja la escalera!" es (o era) un curioso juguete que consistía en una escalera de madera por la que descendía un señor a trompicones.

(Si la imagen se sigue viendo...)


Supón que en lugar de un señor hay N señores y en lugar de escaleras de madera, tenemos las gradas de un estadio, además, que según por donde bajemos, la caída será más rápida o menos rápida.

Entonces, podríamos representar dicha situación con la siguiente matriz:
--        #1 #2
    [     [3,2]
    ,    [9,8,3]
    ,   [1,4,7,7]
    ,  [4,9,8,8,0]
    , [4,8,6,3,0,4]
    ]

Donde tenemos al corredor #1 y al corredor #2. En su primer tropezón, el corredor #1 tendrá una penalización de 3 (3 lo que sea) y el corredor #2 una penalización de 2. Al segundo tropezón, el corredor #1 puede elegir entre ir por la parte izquierda (y penalizarse en 9) o por la derecha (y penalizarse en 8), mientras que el segundo puede elegir entre penalizarse 8 o 3.

Ganará el corredor que primero llegue al suelo.

SE PIDE

Calcular las rutas óptimas de cada corredor ("tropezoneador") junto con su coste total.

POR EJEMPLO

En el ejemplo anterior, el resultado sería:
   [ ( [3,9,1,4,4], 21 )
   , ( [2,3,7,0,0], 12 )
   ]


Por tanto gana el corredor #2.

¿COMO DE GRANDES SON LOS TRIANGULO QUE PUEDES CALCULAR?

Por ejemplo (si siguen ahí y bájalos en RAW sino no verás todas las líneas):

1. Un triángulo de 100 alturas
2. Un triángulo de 1000 alturas

Con soluciones respectivamente:

[([8,6,2,2,3,2,5,9,1,0,6,1,0,8,0,2,1,0,0,1,0,1,1,3,3,0,6,1,3,1,6,4,0,2,5,0,0,1,5,2,8,8,0,0,2,0,3,1,3,0,6,0,1,2,1,1,5,4,3,2,0,1,3,7,0,3,5,1,2,3,0,0,2,3,3,0,1,0,0,4,3,0,1,7,0,2,3,0,0,2,2,0,0,9,0,4,1,0,3,1],227)]


y

[([4,8,5,2,0,1,6,8,1,2,4,0,2,1,0,6,6,1,0,0,4,0,2,1,1,2,5,6,1,1,0,0,3,2,2,4,2,0,1,0,5,1,1,5,1,1,3,1,2,5,1,3,4,0,0,1,6,9,1,1,4,1,2,1,1,4,1,0,0,0,0,0,2,2,1,3,8,0,1,3,1,0,2,3,4,0,0,1,4,6,6,7,7,2,0,2,2,0,2,3,3,3,0,0,0,4,3,0,1,0,0,4,0,2,5,0,0,1,0,7,0,2,1,2,1,2,6,0,2,6,0,4,6,3,0,0,1,2,0,3,4,2,2,0,6,1,0,1,4,4,3,3,3,1,0,2,2,6,1,3,2,3,6,2,3,1,0,4,2,1,2,2,2,3,1,1,4,3,1,4,2,1,1,3,0,2,3,0,2,2,0,4,1,8,0,1,1,3,0,0,2,7,0,1,0,1,2,6,2,1,2,1,0,7,1,1,3,0,0,1,2,3,4,0,0,4,2,2,2,3,2,0,2,3,2,1,2,1,0,2,2,1,2,0,8,0,2,2,6,1,3,5,1,1,6,5,1,5,3,0,3,1,4,0,2,0,3,3,3,4,0,4,2,2,4,1,2,2,1,1,2,1,1,3,7,0,1,3,0,1,2,0,1,0,4,5,2,0,1,3,0,4,1,4,0,0,0,6,2,0,4,3,0,0,0,1,6,1,4,0,8,0,2,2,0,7,3,1,0,1,1,4,1,1,0,6,3,2,3,2,7,0,0,4,0,6,1,1,0,1,0,1,0,9,0,2,1,5,3,5,1,0,2,3,1,1,2,5,1,1,3,0,4,0,4,2,3,2,1,0,2,0,3,0,4,1,1,1,3,1,0,5,0,4,2,2,2,0,2,1,7,2,4,0,2,0,0,0,3,0,2,3,5,0,5,1,1,1,4,2,4,1,1,7,3,1,2,2,0,2,2,2,0,0,0,1,5,1,6,0,2,0,1,0,3,4,1,0,0,3,9,2,4,1,1,1,1,3,2,1,1,9,2,2,4,1,0,0,5,2,1,2,2,4,0,2,1,5,0,2,7,1,0,2,4,1,0,1,1,0,3,3,2,3,0,5,0,4,6,1,5,4,0,1,0,3,0,0,2,2,5,0,0,0,4,1,2,3,7,1,6,0,2,4,2,1,3,4,0,5,2,2,0,5,4,4,1,5,5,1,4,0,1,2,3,2,1,5,4,0,0,0,6,2,2,0,2,1,6,3,0,7,0,0,0,0,4,1,0,3,1,3,1,5,2,7,0,1,3,0,4,0,0,3,2,3,3,4,1,1,3,3,1,2,2,0,1,1,0,0,9,0,1,0,5,6,1,3,0,4,0,1,2,0,1,1,0,2,1,2,2,1,2,1,2,4,1,2,4,4,1,3,0,0,2,5,0,0,0,3,1,5,1,3,0,9,3,1,2,0,0,3,0,1,2,2,8,0,6,0,0,2,2,4,1,3,1,1,2,4,0,6,1,2,0,0,0,1,1,3,2,2,1,1,0,3,6,4,1,0,1,1,3,0,1,0,7,0,5,0,5,1,3,1,2,1,7,4,3,2,1,0,0,5,0,2,0,4,2,0,1,2,0,4,0,0,0,2,0,2,1,3,8,0,3,2,4,2,0,4,0,0,1,1,2,0,1,0,1,8,1,1,0,2,3,2,2,1,4,5,1,1,1,3,5,2,2,1,1,6,2,0,5,4,2,1,2,0,8,1,5,3,4,2,2,3,0,1,5,2,3,3,0,6,2,0,0,6,0,4,2,0,1,0,0,2,1,6,2,3,4,7,1,1,1,1,8,0,2,2,0,0,4,0,7,1,0,0,2,4,1,3,1,3,0,3,0,3,1,0,7,0,0,0,1,4,2,0,6,1,3,2,1,6,1,0,2,2,1,2,3,3,2,1,4,2,5,4,3,1,0,4,1,0,2,1,5,1,0,0,0,1,0,1,0,2,4,3,3,1,1,4,1,1,0,4,0,3,0,0,2,1,1,2,2,4,3,5,0,1,9,0,0,6,3,0,0,0,2,0,2,5,0,4,0,1,0,2,0,0,3,6,0,2,0,5,3,4,4,1,1,2,0,3,2,5,5,1,1,1,2,3,2,2,1,0,6,2,1,1,5,1,2,1,1,3,2,0,1,0,3,4,0,1,2,1,0,1,0,0,6,1,4,0,2,1,0,0,0,2,1,0,4,1,2,4,2,0,0,1],2045)]

Ver todo el enunciado

Preguntas sobre el desafío

¿Tienes dudas sobre el desafío? plantéala aquí

Plantea tu pregunta

9 Soluciones

Dar mi solución

1voto
Carrera de "¡Baja la escalera!" en F#
por

josejuan

hace 5 años

Una traslación directa de la versión de Haskell arroja en F# unos rendimientos muy inferiores. Usando la misma máquina (8 cores) tarda 6 veces más de tiempo. Seguramente la paralelización con "Array.Parallel" no es la más eficiente para este tipo de paralelización (muchas pequeñas operaciones).

0votos
Carrera de "¡Baja la escalera!" en Haskell
por

josejuan

hace 5 años

Se resuelven problemas de 22000 filas (242M nodos) en 2,68 segundos usando 8 cores. Lo que me ha gustado de este problema es que te obliga a darle muchas vueltas para obtener soluciones eficientes. Existen muchas alternativas, pero sólo unas pocas consiguen buen rendimiento. Soluciones genéricas (como usar Floyd o Dijikstra) darían rendimientos mucho menores porque este problema admite soluciones específicas.

0votos
Carrera de "¡Baja la escalera!" en JavaScript
por

josejuan

hace 5 años

La estrategia básica consiste en obtener el camino óptimo de un nodo, conociendo el camino óptimo de sus dos descendientes. Ésto se puede hacer eficientemente de dos formas, memoizando una búsqueda recursiva en el árbol o haciendo "tail recursion" que, imperativamente, puede reducirse a mantener un único registro de caminos óptimos. Ésto supone usar 4mS para el árbol de 100 filas y 340mS para el árbol de 1.000 filas en un ordenador modesto.

0votos
Carrera de "¡Baja la escalera!" en JavaScript
por

Pedro-vk

hace 5 años

El algoritmo es el más obvio, generar todas las posibles rutas y después escoger la más rápida. Es totalmente lento e ineficiente, con 22 filas tarda 3 segundo (2097152 rutas). El algoritmo va añadiendo por un lado la lista de los números usados y por otro la cantidad de resistencia, solo pasa una vez por cada punto. Intentaré hacerlo con paralelización.

Dar mi solución