Hello beloved brethren,

I don't usually participate in the Perl Weekly Challenge but for the occasion of the 100th challenge I thought I'd give it a try.

The challenge

Input: Triangle = [ [1], [2,4], [6,4,9], [5,1,7,2] ]
Output: 8

Explanation: The given triangle

            1
           2 4
          6 4 9
         5 1 7 2

The minimum path sum from top to bottom:  1 + 2 + 4 + 1 = 8

             [1]
           [2]  4
           6 [4] 9
          5 [1] 7 2
[download]

Solutions?

More complex than it first seems, this task requires the programmer to look ahead further than the "next move" to see which "move" is correct. I think the solution involves some sort of recursive algorithm but I cannot see how one could avoid computing all possible paths. It's not possible to assume that the lower of the two choices for "next move" is the correct move, as it may lead to a subsequent choice of two very high numbers.

I eagerly await minds brighter than mine to provide "correct" ways of doing this. In the meantime here's my brute-force approach which works well, given that the spec is for a four-row triangle:

# PWC 100
use strict;
use warnings;
use feature 'say';
use JSON::PP;
use Test::More;

while ( my $line = <DATA> ) {
    my ($json, $expected) = split /\s/, $line;
    my $aoa = decode_json($json);
    is( compute($aoa), $expected );
}

sub compute {
    my @aoa = @{shift()};

    my $total;

    for my $r1_ix (0,1) { # second row
        for my $r2_ix ($r1_ix, $r1_ix+1) { # third row
            for my $r3_ix ($r2_ix, $r2_ix+1) { # fourth row
                my $sum = $aoa[0][0] +
                          $aoa[1][$r1_ix] +
                          $aoa[2][$r2_ix] +
                          $aoa[3][$r3_ix];

                say sprintf('Sum of %d (%d, %d, %d, %d)',
                            $sum, $aoa[0][0], $aoa[1][$r1_ix], $aoa[2]
+[$r2_ix], $aoa[3][$r3_ix]);

                $total = $sum if ! $total || $total > $sum;
            }
        }
    }

    return $total;
}

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
[download]

Here's to a lively discussion!