1nict:

Here ya go! (In readmore tags, just in case it would be a spoiler for someone...)

Running it gives:

$ perl PWC_100_min_path_sum.pl
Result: 8 (1, 4, 2, 1)
[download]

...roboticus

When your only tool is a hammer, all problems look like your thumb.

Classic caching problem. Each cell is computed only once.

#!/usr/bin/perl

use strict;
use warnings;
use List::Util qw( min );

local $_ = <<END;
            1
           2 4
          6 4 9
         5 1 7 2
END
my @d = map [ split ], split /\n/;

my %cache;

print path(0, 0), "\n";

sub path
  {
  my ($r, $c) = @_;
  $cache{"@_"} //= $r < $#d
    ? $d[$r][$c] + min(path($r+1, $c), path($r+1, $c+1))
    : $d[$r][$c]
  }
[download]

It wasn't clear from the problem whether just the sum was needed or the whole path. This just returns 8

> It wasn't clear from the problem whether just the sum was needed or the whole path. This just returns 8

any approach recording paths will fail in general, because there is no guaranty for a unique or even small number of optimal solutions.

Just imagine a triangle with n=100 rows but only weight 1 in every cell, the number of optimal paths is 2**99 then and the weight is always 100.

But it's nonetheless possible to calculate the weight of the optimal path, and even to reconstruct one of those optimal path.

And this in at most n**2/2 (here ~5000) steps (time and space complexity)

see Re^2: Brute force vs algorithm (PWC # 100)

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

If "a" minimal path is wanted (and not all) it sort of looks the same :)

#!/usr/bin/perl

use strict; # https://perlmonks.org/?node_id=11128406
use warnings;
use List::Util qw( reduce );

local $_ = <<END;
            1
           2 4
          6 4 9
         5 1 7 2
END
my @d = map [ split ], split /\n/;

my %cache;

print path(0, 0), "\n";

sub path
  {
  my ($r, $c) = @_;
  $cache{"@_"} //= $r < $#d
    ? $d[$r][$c] . ' + ' .  reduce { eval $a <= eval $b ? $a : $b }
      path($r+1, $c), path($r+1, $c+1)
    : $d[$r][$c]
  }
[download]

Outputs:

1 + 2 + 4 + 1
[download]

Basically, you try to continue a path only if it's "partial weight" is under the current minimum.

Once you reached the bottom line you can be sure you didn't miss any possible better solution, since all other partial path had higher weight.

Tho this "might" be easier when solved backwards by starting from the bottom line.

And the triangle structure might lead to more possible short-cuts.

DISCLAIMER: The given example is probably too small to show the benefits of BaB over brute-force, because the algorithm's overhead doesn't pay off with a tiny data set.

HTH!

So you have to visit each node once, but you never need to recurse or try every path.

edit: whoops, I described finding the maximum; thanks LanX. The idea is the same, just pick the smallest each time /edit

You are describing the dual problem of maximizing a path instead minimizing it.

... but yeah starting with penultimate row will take advantage of the triangle structure.

But you still need to visit all cells, branch-and-bound might help avoiding this.

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

That's what you meant? :)

("abusing" List::Util::reduce() to window two neighboring cells)

<Reveal this spoiler or all in this thread>

ok 1
ok 2
1..2
[download]

edit

That's O(m) = O(n**2) with m:= #cells , n:= #rows and m = n*(n+1)/2

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

update

added comments to code

Hmm, I didn't think it my method was as bad as the brute force, but it apparently is. So much for that idea. (it's how I would've solved it. Also, your implementation was better than mine would have been, even for my naive algorithm.)

Project Euler had almost the same task in problems #18 and #67 except they were looking for the "Maximum Sum Path" where, for #67 with a 100 row triangle, brute force was not an option. I've adapted my PE solution for "Minimum" and it does work for the 100 row triangle, although I've removed that from the script for brevity. I used a leading zero with single digit values just so that things lined up nicely. It calculates the sum and path and, for triangles with three or more rows, shows the triangle using Term::ANSIColor to highlight the path.

The output using the OP's data, sadly not showing the highlighted path here.

Minimum path sum is - 8
            Path is - T-L-R-L
       Elements are - 0-0-1-1

      01      
    02  04    
  06  04  09  
05  01  07  02
[download]

The algorithm works from the bottom of the triangle up but I wrote the script long enough ago that I'm struggling to work out exactly what I did. I'll keep looking at it and maybe produce a version that does both minimum and maximum paths, moving code into subroutines as appropriate.

Hi

I adapted my code in Re^4: Brute force vs algorithm (PWC # 100) to maximize the Euler#67 problem and it took 4 ms on my laptop to generate best weight and path for the provided triangle with 100 rows.

I don't wanna spoil it, but does $cost have 4 digits out of (2 3 7) ? :)

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

Update: Fixed an error (@sums - 1 instead of @sums - 2).

Update 2: Here's the visualisation part:

sub triangle_sum_show {
    my ($triangle) = @_;
    my @sums = @{ $triangle->[-1] };
    my @way;
    while (@sums > 1) {
        unshift @way, [];
        @sums = map {
            my $i = $sums[ $_ - 1 ] < $sums[$_] ? $_ - 1 : $_;
            push @{ $way[0] }, $i;
            $sums[$i] + $triangle->[@sums - 2][ $_ - 1 ];
        } 1 .. $#sums;
    }
    unshift @way, [];
    my $previous;
    for my $row (@$triangle) {
        my @selected = @{ $way[$#$row] };
        $previous = @selected ? $selected[$previous] : 0;
        print ' ' x (@$triangle - @$row);
        for my $i (0 .. $#$row) {
            print ' ', $i == $previous ? "[$row->[$i]]" : $row->[$i];
        }
        print "\n";
    }
}
my $triangle = [ map [map int rand 10, 1 .. $_], 1 .. 20 ];
triangle_sum_show($triangle);
[download]

                    [9]
                   [1] 4
                  3 [2] 9
                 9 [6] 8 2
                6 [2] 7 3 4
               0 [0] 0 5 9 5
              2 [2] 0 1 8 3 2
             7 [1] 1 8 4 6 8 6
            1 [0] 6 2 9 2 2 6 4
           3 [2] 0 1 6 9 5 6 2 2
          0 [1] 8 8 1 4 9 8 6 9 6
         8 9 [7] 1 9 7 1 5 8 8 1 4
        0 4 [4] 6 8 9 5 5 6 1 9 8 5
       9 4 [3] 0 4 8 6 3 7 1 8 0 7 8
      1 6 [1] 6 4 4 3 3 0 2 6 6 2 6 6
     0 6 1 [3] 9 6 9 9 1 5 9 7 1 5 9 9
    8 9 7 6 [1] 5 5 2 8 7 8 7 4 6 4 7 4
   3 4 8 8 9 [3] 4 0 5 7 6 8 2 8 4 1 1 2
  4 9 0 8 6 [0] 2 8 2 7 0 1 3 2 5 8 0 7 7
 3 3 2 0 5 9 [1] 3 5 2 5 9 3 0 4 6 3 6 4 3
[download]

it's a variation of this idea Re^2: Brute force vs algorithm (PWC # 100), right?

i.e. summing up the parents bottom-up with the min of two lower children?

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

Yes, it is. I wasn't able to come up with a top down algorithm.
map{substr$_->[0],$_->[1]||0,1}[\*||{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^*ARGV,3]

Check for Dijkstra's algorithm in classic Graph Theory.

Yes this problem can be represented as a shortest way lowest cost problem in a graph.

But Dijkstra also deals with generalized graphs, for instance here it s clear that any path will have the same length.

You'd have also more algorithmic overhead, it depends on always choosing the partial solution with the lowest cost so far. But Perl has no automatically sorted lists, so you'd run a sort each time over all open ends.°

And Dijkstra would handle a short path with lower cost (up in the triangle) before handling an almost finished path with slightly higher cost.

My guess is that Dijkstra would only pay off for triangles with several hundreds of rows. (update: An optimized branch-and-bound would do better but still need many rows.)

But OTOH there are ready to use Dijkstra / Graph packages...

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

°) or you reimplement Heaps to have balanced search trees.

I regard the discussion about a PWC challenge as inopportune when it is started before the submission deadline has expired.