Number Pyramid

Description

You have a pyramid made of numbers like this:

   1
  2 3
 4 5 6
7 8 9 10

From top to bottom, there are routes on nodes like:

      [1]
   [2]   3
 4    [5]  6
7  [8]   9   10

The sum of this route is: 16

Exercise

What is the sum value of the largest route.

Example

Based on the example above, it's: 20

      [1]
    2    [3]
 4     5    [6]
7    8   9    [10]

Input format

1
2 3
4 5 6
7 8 9 10

Output format

20

A very simple input generator

#!/usr/bin/bash

levels=${1:-3}

for i in $(seq 1 $levels); do
  for _ in $(seq 1 $i); do
    echo -n $(($RANDOM % 100))" "
  done
  echo
done

Bonus

What is the exact route with the largest sum value.

Usage (provided python solutions)

lectures/number-pyramid master
[I] ❯ time (bash gen.sh 100 | python3 calc.py > /dev/null)
( bash gen.sh 100 | python3 calc.py > /dev/null; )  0.25s user 0.18s system 112% cpu 0.385 total

lectures/number-pyramid master
[I] ❯ time (bash gen.sh 100 | python3 calc-with-path.py > /dev/null)
( bash gen.sh 100 | python3 calc-with-path.py > /dev/null; )  0.26s user 0.19s system 111% cpu 0.402 total