# ETOOBUSY ðŸš€ minimal blogging for the impatient

# PWC100 - Triangle Sum

**TL;DR**

On with TASK #2 from the Perl Weekly Challenge #100. Enjoy!

# The challenge

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.

# The questions

I can definitely hear Mohammad S Anwar muttering to himself about that objectively annoying polettix insisting on having a more specific example for the input of this challenge. Becauseâ€¦ itâ€™s nice to see this:

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

A-ha! I will assume that thereâ€™s no parsing involved then, and that the representation is already in easy-to-use Perl arrays of arrays. Thanks!

Reading through the Perl Weekly Review #097 by Colin Crain I got to understand how much stuff I give for granted when I read these challenges. For example, the fact that the the minimum number of changes in the binary substrings might land on none of the actual sub-sequences was an epiphany!

So I wonderâ€¦ *what might I be missing here?!?*.

I hope nothing.

# The solution

I know, I know.

I said: *no parsing, yay!*

Alas, I like to have programs around the functions that solve these challenges, which usually means messing up with the command line. So letâ€™s take this away first:

```
sub triangularize (@list) {
my @retval;
my $n = 1;
while (@list) {
die "invalid number of elements\n" unless @list >= $n;
push @retval, [splice @list, 0, $n];
++$n;
}
return \@retval;
}
```

This takes a flat list of items and groups them in the right way for the puzzle, producing an array of arrays as output.

OK, back on the main track, letâ€™s see my solution to this challenge:

```
sub triangle_sum ($tri) {
my @s = $tri->[0][0];
my $i = 1;
while ($i <= $tri->$#*) {
my $l = $tri->[$i];
my @ns = $s[0] + $l->[0];
push @ns, $l->[$_] + ($s[$_ - 1] < $s[$_] ? $s[$_ - 1] : $s[$_])
for 1 .. $l->$#* - 1;
push @ns, $s[-1] + $l->[-1];
@s = @ns;
++$i;
}
return min(@s);
}
```

We keep an array `@s`

of the *best sums so far* that landed us on a
specific spot. This starts with the very first line in our triangle,
which contains only one single item (`$tri->[0][0]`

).

For each following line, we calculate the *next sums* in `@ns`

. There
are three cases:

- the left-most item can
*only*come from the left-most item in the previous line; - the right-most item can
*only*come from the right-most item in the previous line; - all other items (if any) can come from two possible previous lineâ€™s items.

For this reason, calculating the two external elements in `@ns`

is
straightforward, while for the middle ones we have to understand what is
the best *previous* item, which in this case means which of these
previous items is the lower one.

When weâ€™re done calculating the *next sums* in `@ns`

, we can update `@s`

and move on.

When weâ€™re done with the last line, we just have to calculate the minimum of all the possible sums up to the last line and weâ€™re done!

Here is the whole program, for the masochists:

```
#!/usr/bin/env perl
use 5.024;
use warnings;
use experimental qw< postderef signatures >;
no warnings qw< experimental::postderef experimental::signatures >;
use List::Util 'min';
sub triangle_sum ($tri) {
my @s = $tri->[0][0];
my $i = 1;
while ($i <= $tri->$#*) {
my $l = $tri->[$i];
my @ns = $s[0] + $l->[0];
push @ns, $l->[$_] + ($s[$_ - 1] < $s[$_] ? $s[$_ - 1] : $s[$_])
for 1 .. $l->$#* - 1;
push @ns, $s[-1] + $l->[-1];
@s = @ns;
++$i;
}
return min(@s);
}
sub triangularize (@list) {
my @retval;
my $n = 1;
while (@list) {
die "invalid number of elements\n" unless @list >= $n;
push @retval, [splice @list, 0, $n];
++$n;
}
return \@retval;
}
my @list = @ARGV ? @ARGV : qw< 1 2 4 6 4 9 5 1 7 2 >;
say triangle_sum(triangularize(@list));
```

Stay safe folks!