Problem Description

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in red and is equal to 2427.

Find the minimal path sum, in matrix.txt (right click and ‘Save Link/Target As…’), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by only moving right and down.

Analysis

As with problems 18 & 67 we have a designated starting and ending place. We can use the same technique that solved those problems by starting at the bottom and replacing with minimal sums. See those problems for further information.

Out of bounds (undefined) spaces are ignored from determining a minimum.

Solution

Runs < 1 second in Perl.

my @rows = map { [split /,/] } <DATA>;
my $nrows = $#rows;
 
for (my $i = $nrows; $i >= 0; $i--) {
    for (my $j = $nrows; $j >= 0; $j--) {
        $rows[$i][$j] += min_n($rows[$i+1][$j], $rows[$i][$j+1]);
    }
}
print "Answer to PE81 = $rows[0][0]";
 __DATA__
131, 673, 234, 103, 18 
201, 96, 342, 965, 150 
630, 803, 746, 422, 111 
537, 699, 497, 121, 956 
805, 732, 524, 37, 331

Comments

• We’ve included the sample matrix as an example.
• The first line of the program reads the data file, which is appended to the end of the program after the __DATA__ separator, into a two dimensional array named @rows. $nrows is the last index of the array so in this case 4.
• Check here for more information on the min_n function.