# PWC 100
use v5.12;
use warnings;
use JSON::PP;
use Test::More;
use List::Util qw/reduce min first/;
use Data::Dump qw/pp dd/;

# --------- Testing

while ( my $line = <DATA> ) {
    chomp $line;

    my ($json, $exp_cost, $exp_path) = split /\s+/, $line;
    my $triangle   = decode_json($json);
    $exp_path = decode_json($exp_path);

    my ($cost,$path) = compute($triangle);

    is( $cost, $exp_cost,
        "cost: $cost" );

    is_deeply( $path, $exp_path ,
               "path: ".pp $path);

}

# --- 100 rows element "1"
my $depth = 100;
my $pathological = [ map [ (1) x $_], 1..$depth ];

my ($cost,$path) = compute($pathological);

is( $cost, $depth,
    "pathologigal cost: $cost" );

# --- 100 rows random elements
my $random = [ map [ map {1+int rand 10} 1..$_ ], 1..$depth ];
($cost,$path) = compute($random);

say "random cost: $cost";
say "random path: ",pp $path;

done_testing;


# --------- Implementation

sub compute {
    my @triangle = @{(shift)};
    my @weight = map { [@$_] } @triangle; # deep copy


    for ( my $i = $#weight; $i > 0; $i--) {
        my $children = $weight[$i];
        my $parents  = $weight[$i-1];

        my $j;

        reduce {                        # --- by overlapping pairs
            $parents->[$j++] +=         # add to parent ...
              min $a,$b;                # ... minimal child
            $b                          # = next $a
        } @$children;
    }

    my $result = $weight[0][0];

    my $path = calc_path(\@triangle,\@weight,$result);

    return ($result,$path);
}


sub calc_path {
    my ($triangle, $weight, $diff) = @_;

    my @path;

    for my $row (@$triangle) {
        my ($i,$sum) = each @$weight;

        my $j = -1;
        first { $j++; $diff == $_ } @$sum;

        my $step = $row->[$j];
        push @path, $step;
        $diff -= $step;
    }

    return \@path;
}



__DATA__
[[1],[2,4],[6,4,9],[5,1,7,2]] 8   [1,2,4,1]
[[9],[1,6],[7,8,2],[5,8,2,3]] 19  [9,6,2,2]

##</code><code>##

C:/Perl_524/bin\perl.exe -w d:/tmp/pm/pwc100.pl 
ok 1 - cost: 8
ok 2 - path: [1, 2, 4, 1]
ok 3 - cost: 19
ok 4 - path: [9, 6, 2, 2]
ok 5 - pathologigal cost: 100
random cost: 305
random path: [
  10,
  3,
  2,
  6,
  3,
  5,
  2,
  2,
  2,
  1,
  6,
  1,
  8,
  3,
  1,
  6,
  1,
  3,
  1,
  1,
  1,
  2,
  2,
  3,
  3,
  4,
  1,
  4,
  3,
  1,
  7,
  1,
  1,
  1,
  2,
  2,
  5,
  1,
  6,
  1,
  6,
  2,
  1,
  8,
  5,
  3,
  1,
  3,
  2,
  1,
  2,
  5,
  3,
  5,
  1,
  4,
  8,
  9,
  6,
  5,
  1,
  3,
  4,
  2,
  3,
  5,
  7,
  2,
  3,
  1,
  3,
  2,
  1,
  5,
  5,
  4,
  4,
  1,
  2,
  4,
  2,
  3,
  1,
  4,
  2,
  6,
  1,
  2,
  3,
  2,
  3,
  1,
  1,
  2,
  2,
  4,
  2,
  1,
  2,
  1,
]
1..5