#!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";
[download]