Or for a big mess, compute the score and the path simultaneously :)
#!/usr/bin/perl
use strict; # https://perlmonks.org/?node_id=11128406
use warnings;
use List::Util qw( reduce min );
local $_ = <<END;
1
2 4
6 4 9
5 1 7 2
END
my @d = map [ split ], split /\n/;
$d[$#d][$_] = [ $d[$#d][$_], $d[$#d][$_] ] for 0 .. $#d;
for my $r ( reverse 0 .. $#d - 1 )
{
for my $c ( 0 .. $r )
{
$d[$r][$c] = [ $d[$r][$c] + min( $d[$r+1][$c][0], $d[$r+1][$c+1][0
+]),
"$d[$r][$c] + " . (reduce { $a->[0] <= $b->[0] ? $a : $b }
$d[$r+1][$c], $d[$r+1][$c+1])->[1] ];
}
}
print "value $d[0][0][0] path $d[0][0][1]\n";
Outputs:
value 8 path 1 + 2 + 4 + 1
|