Download the raw code.
use v6;
my @chain = $*IN.get.comb: /\d+/;
my @matrices = @chain Z=> @chain[1..*-1];
unless +@matrices {
say 'Input must consist of at least two integers.';
exit;
}
my $n = 1; # should be a state var of to-string($)
my multi sub to-string(@e) { [~] '(', (to-string($_) for @e), ')' } # .map does not like me :/
my multi sub to-string($ ) { 'A' ~ $n++ }
say to-string( mul(@matrices).[1] );
# mul(*@Matrices) returns:
# 1. Cost of the multiplication.
# 2. Multiplication expression as AoA. A single matrix is represented by a 1.
# 3. Rows of the result-matrix.
# 4. Cols of the result-matrix.
my %mul; # memoization, should be a state var of mul(*@M)
sub mul(*@M) {
my $key = @M.map( *.kv.join: 'x' ).join: '*';
return %mul{$key} if %mul.exists: $key;
return (%mul{$key} = [ 0, 1, @M[0].kv ]) if +@M == 1;
my ($cost, $expr, @size) = +Inf;
for 0 .. @M.end - 1 -> $i {
my ($c1, $e1, $p, ) = @( mul @M[ 0 .. $i ] ); # lhs
my ($c2, $e2, $q, $r) = @( mul @M[$i+1 .. @M.end] ); # rhs
my $cges = $c1 + $c2 + $p*$q*$r;
if $cges < $cost {
$cost = $cges;
$expr = [ $e1, $e2 ];
@size = $p, $r;
}
}
return (%mul{$key} = [ $cost, $expr, @size ]);
}
Various things are vertically aligned. Stylish.
The code, short as it is, doesn't settle on either pre-declaring or post-declaring all its local subs. The mainline code gets a bit sprinkled out as a result.
The comments speak volumes. Sometimes they complain that things "should" be otherwise, but it's not obvious why they aren't. (My guess is Rakudo limitations, but the point is that it doesn't say.)
I'm unable to prove whether recursion/memoization is actually as efficient as some corresponding iterative approach, but a few trials of the program suggest it is.
The code gives off a general sense of using multis and recursion in a very natural way. It's definitely coming from a FP angle, but it works well here, too.
The code manages to get the job done in deligtfully few lines without feeling crowded.