Here is my solution. It only finds the sum, I might add the highlighting later.
#!/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();
Update: Fixed an error (@sums - 1 instead of @sums - 2).
Update 2: Here's the visualisation part:
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);
Possible output:
[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
map{substr$_->[0],$_->[1]||0,1}[\*||{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^*ARGV,3]