Re: Brute force vs algorithm (PWC # 100)

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

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.

use strict;
use warnings;

use 5.014;

use Term::ANSIColor qw{ :constants };

open my $inFH, q{<}, \ <<EOD or die $!;
01
02 04
06 04 09
05 01 07 02
EOD

=pod
06
-----
12
03 09
-----
01
02 04
06 04 09
05 01 07 02
-----
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
=cut

my @idxLR  = ( 0, 0, 1 );
my @pathLR = qw{ L L R };

my @lines;

while ( <$inFH> )
{
    chomp;
    push @lines, [
       map { { val => $_, sum => undef } } split
       ];
}

close $inFH or die $!;

if ( scalar @lines == 1 )
{
    say qq{Minimum path sum is - $lines[ 0 ]->[ 0 ]->{ val }};
    say  q{            No path};
}
elsif ( scalar @lines == 2 )
{
    my $compIdx =
       $lines[ 1 ]->[ 1 ]->{ val } <=> $lines[ 1 ]->[ 0 ]->{ val };
    say
       qq{Minimum path sum is - },
       $lines[ 0 ]->[ 0 ]->{ val } +
       $lines[ 1 ]->[ $idxLR[ $compIdx ] ]->{ val };
    say
       qq{            Path is - $pathLR[ $compIdx ]};
}
else
{
    do {
       $_->{ sum }  = $_->{ val };
       $_->{ path } = [];
       } for @{ $lines[ -1 ] };
    foreach my $lineIdx ( reverse 0 .. $#lines - 1 )
    {
        my $raLine = $lines[ $lineIdx ];
        foreach my $itemIdx ( 0 .. $#{ $raLine } )
        {
            my $compIdx =
               $lines[ $lineIdx + 1 ]->[ $itemIdx + 1 ]->{ sum }
               <=>
               $lines[ $lineIdx + 1 ]->[ $itemIdx ]->{ sum };
            $raLine->[ $itemIdx ]->{ sum }  =
               $raLine->[ $itemIdx ]->{ val } +
               $lines[ $lineIdx + 1 ]
                  ->[ $itemIdx + $idxLR[ $compIdx ] ]
                  ->{ sum };
            $raLine->[ $itemIdx ]->{ path } = [
               $pathLR[ $compIdx ],
               @{ $lines[ $lineIdx + 1 ]
                  ->[ $itemIdx + $idxLR[ $compIdx ] ]
                  ->{ path } }
                  ];
        }
    }
    my @pathElems = ( 0 );
    push @pathElems, m{L} ? $pathElems[ -1 ] : $pathElems[ -1 ] + 1
       for @{ $lines[ 0 ]->[ 0 ]->{ path } };;

    say qq{Minimum path sum is - $lines[ 0 ]->[ 0 ]->{ sum }};
    say  q{            Path is - T-},
       join q{-}, @{ $lines[ 0 ]->[ 0 ]->{ path } };
    say  q{       Elements are - },
       join q{-}, @pathElems;
    say q{};

    my $nElems = scalar( @lines ) * 2 - 1;
    my $fmt    = q{%2s} x $nElems;
    $fmt      .= qq{\n};

    for my $lineIdx ( 0 .. $#lines )
    {
        printf $fmt,
           ( q{  } ) x ( $#lines - $lineIdx ),
           sub {
               my @arr =
                  map {
                      $_ == $pathElems[ $lineIdx ]
                      ? RED . $_[ $_ ] . RESET
                      : $_[ $_ ]
                      } 0 .. $#_;
               splice @arr, $_, 0, q{  } for reverse 1 .. $#arr;
               return @arr;
               }->( map { $_->{ val } } @{ $lines[ $lineIdx ] } ),
           ( q{  } ) x ( $#lines - $lineIdx );
    }
}
[download]

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.

Cheers,

JohnGG

In Section Meditations