1nict:
Here ya go! (In readmore tags, just in case it would be a spoiler for someone...)
#!env perl
#
# PWC_100_min_path_sum.pl
#
# Return the path with the smallest sum from the top of the triangle t
+o the bottom.
#
# 20210215
use strict;
use warnings;
my @triangle = (
[1],
[2, 4],
[6, 4, 9],
[5, 1, 7, 2],
);
sub p {
my $L = shift;
return "$L->[0] (", join(", ", @{$L->[1]}), ")";
}
# Given a coordinate, return an array ref where the first item is the
+sum of the
# shortest path, and the second item is the path (from bottom to top)
sub f {
my ($r, $c) = @_;
my $val = $triangle[$r][$c];
# If there are no more rows to check, then return the column
return [ $val, [ $val ] ] unless defined $triangle[$r+1];
die "Invalid data structure! ($r,$c)" unless defined $triangle[$r+
+1][$c];
my $L = f($r+1, $c);
if (defined $triangle[$r+1][$c+1]) {
my $R = f($r+1, $c+1);
$L = $R if $R->[0] < $L->[0];
}
$L->[0] += $val;
push @{$L->[1]}, $val;
return $L;
}
my $result = f(0,0);
print "Result: ", p($result), "\n";
Running it gives:
$ perl PWC_100_min_path_sum.pl
Result: 8 (1, 4, 2, 1)
...roboticus
When your only tool is a hammer, all problems look like your thumb.