You are describing the dual problem of maximizing a path instead minimizing it.
... but yeah starting with penultimate row will take advantage of the triangle structure.
But you still need to visit all cells, branch-and-bound might help avoiding this.
| [reply] |
That's what you meant? :)
("abusing" List::Util::reduce() to window two neighboring cells)
# PWC 100
use strict;
use warnings;
use JSON::PP;
use Test::More;
use List::Util qw/reduce/;
while ( my $line = <DATA> ) {
my ($json, $expected) = split /\s/, $line;
my $aoa = decode_json($json);
is( compute($aoa), $expected );
compute($aoa);
}
sub compute {
my @aoa = @{(shift)};
my $bottom;
while (@aoa) {
$bottom = pop @aoa;
my $i=0;
reduce { # by overlapping pairs
$aoa[-1][$i++] += # add to parent ...
($a < $b ? $a : $b); # ... minimum neighbors
$b # right to left nb
} @$bottom;
}
return $bottom->[0];
}
done_testing;
__DATA__
[[1],[2,4],[6,4,9],[5,1,7,2]] 8
[[9],[1,6],[7,8,2],[5,8,2,3]] 19
ok 1
ok 2
1..2
edit
That's O(m) = O(n**2) with m:= #cells , n:= #rows and m = n*(n+1)/2
update
added comments to code | [reply]
[d/l]
[select] |
Hmm, I didn't think it my method was as bad as the brute force, but it apparently is. So much for that idea. (it's how I would've solved it. Also, your implementation was better than mine would have been, even for my naive algorithm.)
| [reply] |
> I didn't think it my method was as bad as the brute force
It's not, brute (well the brutest) force will explore all possible path.
The number of possible path grows much faster than m (I'd say exponentially)°.
(... but with such a small triangle that's only of theoretical interest )
°) sure it's p = 2**(n-1)
| [reply]
[d/l] |