in reply to Re^4: Brute force vs algorithm (PWC # 100)
in thread Brute force vs algorithm (PWC # 100)

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]

Replies are listed 'Best First'.
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]

In Section Meditations