in reply to Brute force vs algorithm (PWC # 100)

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

Replies are listed 'Best First'.
Re^2: Brute force vs algorithm (PWC # 100)
by LanX (Saint) on Feb 15, 2021 at 21:33 UTC
    > 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

[reply]
[d/l]

      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]
[reply]
[d/l]
[select]
        Here, my take on this,(a variation from that solution)

        • it calculates best cost and path for both test cases.
        • for one "pathological" triangle with 100 rows with all cells 1
        • for one "random" triangle with 100 rows and random entries

        Our approaches are not that different, your dynamic "cache" is just my explicit "weight" triangle.

        And you are needing more resources for recursion and hash.

        But you could improve it by adding bound criteria (i.e. no need to calculate a subtree if it has no chance to be better than the current minimum).

        edit

        Though I'm not sure this will pay of, my algorithm is already O(m) with m #cells.

        <Reveal this spoiler or all in this thread>

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

[reply]
[d/l]
[select]

In Section Meditations