#!/usr/bin/perl
use warnings;
use strict;

sub triangle_sum {
    my ($triangle) = @_;
    my @sums = @{ $triangle->[-1] };
    @sums = map {
        $sums[$sums[ $_ - 1 ] < $sums[$_] ? $_ - 1 : $_]
            + $triangle->[@sums - 2][ $_ - 1 ]
        } 1 .. $#sums
        while @sums > 1;
    return $sums[0]
}

use Test::More;

is triangle_sum ([ [1], [2,4], [6,4,9], [5,1,7,2] ]), 8, 'Example 1';
is triangle_sum ([ [3], [3,1], [5,2,3], [4,3,1,3] ]), 7, 'Example 2';

is triangle_sum([[2], [1, 5], [9, 10, 1]]), 8, 'Tricky';

done_testing();

##</code><code>##

sub triangle_sum_show {
    my ($triangle) = @_;
    my @sums = @{ $triangle->[-1] };
    my @way;
    while (@sums > 1) {
        unshift @way, [];
        @sums = map {
            my $i = $sums[ $_ - 1 ] < $sums[$_] ? $_ - 1 : $_;
            push @{ $way[0] }, $i;
            $sums[$i] + $triangle->[@sums - 2][ $_ - 1 ];
        } 1 .. $#sums;
    }
    unshift @way, [];
    my $previous;
    for my $row (@$triangle) {
        my @selected = @{ $way[$#$row] };
        $previous = @selected ? $selected[$previous] : 0;
        print ' ' x (@$triangle - @$row);
        for my $i (0 .. $#$row) {
            print ' ', $i == $previous ? "[$row->[$i]]" : $row->[$i];
        }
        print "\n";
    }
}
my $triangle = [ map [map int rand 10, 1 .. $_], 1 .. 20 ];
triangle_sum_show($triangle);

##</code><code>##

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