Here, my take on this,(a variation from that solution)
- it calculates best cost and path for both test cases.
- for one "pathological" triangle with 100 rows with all cells 1
- for one "random" triangle with 100 rows and random entries
Our approaches are not that different, your dynamic "cache" is just my explicit "weight" triangle.
And you are needing more resources for recursion and hash.
But you could improve it by adding bound criteria (i.e. no need to calculate a subtree if it has no chance to be better than the current minimum).
edit
Though I'm not sure this will pay of, my algorithm is already O(m) with m #cells.
# 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]
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
| [reply]
[d/l]
[select] |
#!/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
| [reply]
[d/l]
[select] |