Perl Weekly Challenge 100: Triangle Sum

You are given triangle array.

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

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.

Examples

Example 1

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

Example 2

Input: Triangle = [ [3], [3,1], [5,2,3], [4,3,1,3] ]
Output: 7

Explanation: The given triangle

            3
           3 1
          5 2 3
         4 3 1 3

The minimum path sum from top to bottom: 3 + 1 + 2 + 1 = 7

             [3]
            3  [1]
           5 [2] 3
          4 3 [1] 3

Overview

We will read in the data, and put it in a (2-dimensional) array. We will then work from bottom to top, calculating for each point, the minimum path length to the bottom. We can do this by adding the minimum of the two elements "below" the current element to it.

For instance, assume the input is:

            3
           3 1
          5 2 3
         4 3 1 3

we can calculate the minimum path length to the bottom for the penultimate row by, for each element in that row, adding to it the minimum of the two elements below. This results in:

            3
           3 1
          8 3 4
         4 3 1 3

In the same way, we can calculate the minimum path length for each element in the second row:

            3
           6 4
          8 3 4
         4 3 1 3

One more step, and we get the wanted result in the top of the triangle:

            7
           6 4
          8 3 4
         4 3 1 3

This clearly is a linear time algorithm.

Solutions

Each of the solutions assumes a single triangle on standard input, one row per line, numbers separated by white space. We’re assuming the numbers are integers. The result, as single number, will be written on standard output.

Perl

We start with reading in the data, which can be done in a single statement:

my @nums = map {[/-?[0-9]+/g]} <>;

For each line of input, we’re extracting the numbers using a simple regular expression. This stores the triangle of numbers in the array @nums; each element of @nums is an array with numbers (a row in the triangle).

We can now calculate the lengths using a nested loop; the other loop loops over the rows (bottom to top, starting with the penultimate row), the inner loop loops over the elements of a row.

for (my $x = @nums - 2; $x >= 0; $x --) {
    foreach my $y (keys @{$nums [$x]}) {
        $nums [$x] [$y] += 
               $nums [$x + 1] [$y] < $nums [$x + 1] [$y + 1]
             ? $nums [$x + 1] [$y] : $nums [$x + 1] [$y + 1]
    }
}

For each element, we adding the minimum of the two elements below it.

All what needs to be done is to print the result:

say $nums [0] [0];

Find the complete program on GitHub.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s