Nonsense

Euler 18 - maximizar suma

Clasificación

Es un problema fácil, pero con truco. Indicado para un nivel principiante-intermedio, diría yo.

Enunciado

El problema Euler 18 del Euler Project.

Básicamente tenemos un triángulo de números como los del enunciado. Por ejemplo…

            13
          54  30
        21  07  39
      14  44  23  45
    24  43  16  17  22

Partiendo desde arriba del todo, desde el 13, nos vamos dejando caer. Desde un número sólo podemos bajar a uno de los dos que tiene debajo, a izquierda o derecha. Del 13 podemos pasar al 54 o al 30, del 23 podemos pasar al 16 o al 17. Y así hasta que llegamos abajo del todo. Por ejemplo: 13 → 30 → 7 → 44 → 16. Ahora sumamos todos los números del camino: 13 + 30 + 7 + 44 + 16 = 110.

Pues bien, el problema trata de buscar cuál es el camino que produce la suma máxima en un triángulo dado. En el ejemplo, el camino de suma más alta es 13 → 54 → 21 → 44 → 43 que da un total de 175.

Sugerencias

Hay varias formas de resolver este problema. Creo que una parte interesante del problema es, precisamente, equivocarse en la forma de resolverlo. Hay alguna aproximación que a primera vista puede parecer que funciona pero luego resulta que no, y quizá es más interesante caer en el fallo para darse cuenta de por qué no vale, que no explorar esa solución en absoluto.

Pruebas

Dejo un par de ejemplos que se pueden usar para comprobar la solución frente a resultados conocidos:

assertEquals(euler18(
 [[3],
  [7, 4],
  [2, 4, 6],
  [8, 5, 9, 3]]),
  23, "3 + 7 + 4 + 9 = 23");
assertEquals(euler18(
 [[13],
  [54, 30],
  [21, 7, 39],
  [14, 44, 23, 45],
  [24, 43, 16, 17, 22]]),
  175, "El camino máximo posible es 175");
assertEquals(euler18(
 [[75],
  [95, 64],
  [17, 47, 82],
  [18, 35, 87, 10],
  [20,  4, 82, 47, 65],
  [19,  1, 23, 75,  3, 34],
  [88,  2, 77, 73,  7, 63, 67],
  [99, 65,  4, 28,  6, 16, 70, 92],
  [41, 41, 26, 56, 83, 40, 80, 70, 33],
  [41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
  [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
  [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
  [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
  [63, 66,  4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
  [ 4, 62, 98, 27, 23,  9, 70, 98, 73, 93, 38, 53, 60,  4, 23]]),
  1074, "El camino máximo posible es 1074");

Soluciones

Envíame tu solución si quieres que la revise o que te ayude con ella. Las pondremos aquí: Euler 18.