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

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]

Comment on Re^3: Brute force vs algorithm (PWC # 100) Select or Download Code

Replies are listed 'Best First'.
Re^4: Brute force vs algorithm (PWC # 100) by LanX (Saint) on Feb 16, 2021 at 03:42 UTC
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]
Re^5: Brute force vs algorithm (PWC # 100) by tybalt89 (Monsignor) on Feb 16, 2021 at 04:39 UTC
For people who don't like recursion and hashes :) `#!/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/; for my $r ( reverse 0 .. $#d - 1 ) { for my $c ( 0 .. $r ) { $d[$r][$c] .= ' + ' . reduce { eval $a <= eval $b ? $a : $b } $d[$r+1][$c], $d[$r+1][$c+1]; } } print "$d[0][0]\n";` [download]	[reply] [d/l]
Re^6: Brute force vs algorithm (PWC # 100) by tybalt89 (Monsignor) on Feb 16, 2021 at 05:04 UTC
Or for a big mess, compute the score and the path simultaneously :) #!/usr/bin/perl use strict; # https://perlmonks.org/?node_id=11128406 use warnings; use List::Util qw( reduce min ); local $_ = <<END; 1 2 4 6 4 9 5 1 7 2 END my @d = map [ split ], split /\n/; $d[$#d][$_] = [ $d[$#d][$_], $d[$#d][$_] ] for 0 .. $#d; for my $r ( reverse 0 .. $#d - 1 ) { for my $c ( 0 .. $r ) { $d[$r][$c] = [ $d[$r][$c] + min( $d[$r+1][$c][0], $d[$r+1][$c+1][0 +]), "$d[$r][$c] + " . (reduce { $a->[0] <= $b->[0] ? $a : $b } $d[$r+1][$c], $d[$r+1][$c+1])->[1] ]; } } print "value $d[0][0][0] path $d[0][0][1]\n"; [download] Outputs: `value 8 path 1 + 2 + 4 + 1` [download]	[reply] [d/l] [select]

edit