Challenge 152 Task #1 - Summing up minimums

[Task #1] - Triangle Sum Path

Description

You are given a triangle array.

Write a script to find the minimum sum path from top to bottom.

Example 1:

Input: $triangle = [ [1], [5,3], [2,3,4], [7,1,0,2], [6,4,5,2,8] ]

                1
               5 3
              2 3 4
             7 1 0 2
            6 4 5 2 8

Output: 8

    Minimum Sum Path = 1 + 3 + 2 + 0 + 2 => 8

Example 2:

Input: $triangle = [ [5], [2,3], [4,1,5], [0,1,2,3], [7,2,4,1,9] ]

                5
               2 3
              4 1 5
             0 1 2 3
            7 2 4 1 9

Output: 9

    Minimum Sum Path = 5 + 2 + 1 + 0 + 1 => 9

Solution

Full Source

On first reading of the current challenge, I thought we had this task before. After some digging it turns out - not quite. In task #2 of challenge 100 we had the same task with an additional restriction:

When you are on index i on the current row then you may move to either index i or index i + 1 on the next row.

I solved this here.

Without this restriction it becomes even easier. We have to calculate the sum of the minimum values from each row of the triangle. To do this I’ll use sum0 and min from the venerable List::Util and Perl’s built-in map.

sub minimum_triangle_sum_path($triangle) {
    return sum0( map { min(@$_) } @$triangle );
}

In words:

We map the min function over the rows of the triangle and calculate the sum of that.

Done.

There is no comment section on this site. For questions, suggestions or errors in my post or solution, please create an issue over here or drop me a mail:

    
my $mail = join('@', 'pwc', join('.', 'pankoff', 'net'));