p1-util

Download the raw code.

# Adapted from javascript at http://alexle.net/wp-content/uploads/2006/04/matrix.html
# Calculate the best parenthization for matrix multiplication using
# Dynamic Programming approach.
sub find_optimal_chain_for_matrix_multiply ( @rows_cols_interleaved ) {
    my @rows = @rows_cols_interleaved[ 0  ..^ @rows_cols_interleaved.end ];
    my @cols = @rows_cols_interleaved[ 0 ^..  @rows_cols_interleaved.end ];

    my $n = @rows.elems;

    my @matrix   = (^$n).map({ [ 0 xx $n ] });
    my @sequence = (^$n).map({ [ 0 xx $n ] });

    # Run the algorithm
    my $max_int = 2**31 - 1;
    for 1..$n -> $d { # diagonal --> the length of the chain
        for ^($n-$d) -> $i { # sub problems from
            my $j = $i + $d;
            @matrix[$i][$j] = $max_int;
            for $i..^$j -> $k {
                my $m = @matrix[$i  ][$k]
                      + @matrix[$k+1][$j]
                      + @rows[$i] * @cols[$k] * @cols[$j];

                if $m < @matrix[$i][$j] {
                    @matrix[    $i][$j] = $m;
                    @sequence[  $i][$j] = $k;
                }
            }
        }
    }

    # Return a string representing the best parenthesis groupings.
    # Uses @sequence as a global.
    sub parenthesize ( $i, $j ) {
        return "A{$i+1}" if $i >= $j;
        my $sij = @sequence[$i][$j];
        return '('
             ~ parenthesize( $i,     $sij )
             ~ parenthesize( $sij+1, $j   )
             ~ ')';
    }

    say parenthesize( 0, $n-1 );
}

for $*IN.lines {
    my @nums = .split( /\s+/ )».Int;

    if +@nums < 2 {
        say "Input must consist of at least two integers.";
        next;
    }

    find_optimal_chain_for_matrix_multiply( @nums );
}

Readability

The code is nicely laid out, has sensible variable names, and has some breathing-room here and there.

Consistency

Looks fine.

Clarity of intent

The variable names are short and gruffy, as is the custom in this type of algorithm.

Algorithmic efficiency

Since this was the algorithm I had in mind, this was the algorithmic efficiency I had in mind.

Idiomatic use of Perl 6

Why settle for a measly my $max_int = 2**31 - 1; (line 14) when we have Inf?

The vertical alignment on lines 24..26 is well taken, but could be even prettier with unspace.

Sub-in-a-sub (line 34). We like.

Lines 5 and 6 choose an .end-based approach to indexing rather than a *-based one. Not sure why, or if it helps understanding. Maybe the translation from JavaScript showing through?

.split( /\s+/ ) on line 47 could have been spelled .words. The » is cute, though.

Brevity

Delightfully short.