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 );
}
The code is nicely laid out, has sensible variable names, and has some breathing-room here and there.
Looks fine.
The variable names are short and gruffy, as is the custom in this type of algorithm.
Since this was the algorithm I had in mind, this was the algorithmic efficiency I had in mind.
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.
Delightfully short.