The Path in the Pyramid

Wherein we travel along these pathways into darkness, trying to finish our mission and avoid being killed by monsters…

THE WEEKLY CHALLENGE – PERL & RAKU #152 task 1

---

“The fact is that building a pyramid is fairly easy, aside from the lifting. You just pile up stones in receding layers, placing one layer carefully upon another, and pretty soon you have a pyramid. You can’t help it. In other words, it is not in the nature of a pyramid to fall down… It probably could not fall down if it tried.”

— Will Cuppy, The Decline and Fall of Practically Everybody (1950)

---

Triangle Sum Path

Submitted by: Mohammad S Anwar

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

A Note on SImplicity

You know, when I do these challenges, and especially when I review the work of others, I make a concerted effort not to ever use the word “easy”. Why? Because it communicates very little informatiion, and none of it useful. When I say something is easy, I can only really mean that it is easy for me. Other people, less familiar with the material, or the required steps to a solution, might find the task considerably more difficult. I don’t know what they know, and generally knowing the solution myself makes me blind to the state of not knowing it.

To them, knowing that I found the task easy does not help at all. It’s a distraction, or perhaps nothing at best, and at worst sets up a judgemental ruling that their own efforts, struggling to put the pieces together, are substandard. I have no idea why I would ever want to do this. Belittling another person in no way makes me objectively better. I remain exactly as able after the judgement as I was before.

This isn’t to be taken as a rejection of things actually being easy mind you. I love that feeling of being overtaken by exhuberance on a job well-done. Confidence is good, as is pride in one’s work, but only up to and not exceeding the point of being noticed by the gods. That other related word, hubris, is an important idea to keep around, and I’m quite pleased an impassioned classicist hammered the nuances of the Greek word into my head many years ago. It has served me well in life.

So in the end I’ve decided that declaring things “easy” amounts to nothing but a brag. An empty boast at that, as the claim does not normally achieve anything of value. The only possible effect it can have, it seems, is to cut someone else down, if they happen to be finding the task difficult.

Perhaps I’m being a little hard on the term. It’s still a good word, after all, for what it represents. Easy is something we should all strive for.

But I really can’t stand braggarts.

METHOD

This took me bit, understanding what exactly was meant by the idea of a “minimum sum path”. Looking at a triangle in this context, to me, generally implies a directed graph of some sort, which would involve navigating the edges in some optimal fashion.

But no.

A quick study of the examples shows this not to be the case. In fact, for lack of some flash of insight I can’t seem to come up with much of a reason at all for using one of those particular terms to describe what we are being asked to do. I mean, it’s not wrong, per se, just not very illuminating, at least for me.

The first two ideas, “minimum” and “sum” speak for themselves, and the smallest total value from a sequence of addition is indeed what we want. It’s the word “path” that strikes me as the part that will cause confusion. The term “path” generally speaks to a series of connected steps describing a way to proceed. One might think that the “steps” involved here were somehow the selected minimal digits, but as it turn out the steps are the descending levels of the triangle, with each level a complete unit. As such the goal is only to select the minimal value from each level, one per level, and sum the collection. Kind of a let-down, if you ask me.

As the triangles themselves are delivered transformed into a flat list-of-lists data structure, the levels come already grouped into collections of elements for us. Although the triangle is constructed as an array-of-arrays, as that is the data structure available to us, in practice the set of levels is unordered: the “sum” operation is commutative, and does not care about the order of the additions. Likewise the “minimum” function on each level operates on another set, finding the smallest value where’ve it may lie, again without regard to order.

So hence my use of the word “lists” before, as the positional indexing that de facto exists is inconsequential to either the processing or the outcome. What we have is a list of anonymous array units to be processed one-by-one until we are done, gathering from each the smallest element to an accumulator of some sort that is ultimately reported.

That’s a lot of words to very specifically describe a much simpler operation than I first expected.

Although just printing the actual sum would be simpler still, we’ll follow the example and gather the elements selected along the way to produce a readout on our “path”.

---

PERL 5 SOLUTION

By importing two functions, sum() and min() from the core List::Util module, the actual processing is done in one or two lines, depending on how you count. I’ve decided to punt on the whole idea of parsing user input to specify arbitrary triangles, as defining and reading in a flat format for stringified multidimensional arrays is a project larger than the requested process itself. Not to mention we’re given an example as pre-built array reference. We could just read in that, as a string, and apply eval on the input to turn it into a data structure, but that’s such a bad practice in general I wrote it up and then refused to leave it there, glaring at me with unrestrained malice:

$ARGV[0] //= q([ [1], [5,3], [2,3,4], [7,1,0,2], [6,4,5,2,8] ]);
my $triangle = eval shift;    ##  NO! NO! NO!

This is, to put it mildly, a security risk. What would happen should some mean person call your script with rm -rf / instead of a triangle? That would be bad.

The process is straightforward: for every level array encountered we select the smallest element and append it to an output array. In the reporting phase we join the array to produce a nice string of addends, and then call sum() to provide the final value.

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';

use List::Util qw( sum min );

## default triangle
my $triangle = [ [1], [5,3], [2,3,4], [7,1,0,2], [6,4,5,2,8] ] ;

my @out      = map { min( $_->@* ) } $triangle->@*;

say "minimum sum path: ", (join ' + ', @out), " => ", sum @out;

The result:

minimum sum path: 1 + 3 + 2 + 0 + 2 => 8

Raku Solution

In Raku our outboard functions are built-in, making things easier. Another welcome addition to the language is the ability to include a block directly into a sting to be interpolated, which will be evaluated and the result inserted in-place, avoiding the concatenation of the Perl version.

unit sub MAIN () ;

my @triangle = [1], [5,3], [2,3,4], [7,1,0,2], [6,4,5,2,8];

my @out = @triangle.map( { $_.min });

say "minimum sum path: {@out.join(' + ')} => {@out.sum}";