Download the raw code.
#
# optimal way to multiply a chain of matrices
# the algorithm seeks to always collapse the higher factor
# by canceling it in between the multiplications.
#
my @items = $*IN.get.comb(/\d+/);
exit say "Input must consist of at least two integers." unless @items > 1;
my @matrix = 'A' X~ 1 .. @items-1;
while @matrix > 1
{
my $i = max { @items[$^a] > @items[$^b] }, 1 .. @items-2;
@items.splice($i,1);
@matrix.splice($i-1,2,'('~@matrix[$i-1]~@matrix[$i]~')');
}
say @matrix[0];
The code goes for a slightly rugged, crammed-together look, not giving its binary operators any (white) space. But some people like it that way. It's also consistent with the code seemingly striving for terseness.
I wonder why the @items
array deserved a plural but the @matrix
only a
singular...
I'd say the code is very clear. It goes to work, and it does it cleanly.
Hm, I wouldn't have called the list of dimensions @items
, though.
I guess the fact that this algorithm is linear in time gets shadowed a bit by the fact that the algorithm is flawed.
$ perl6 solutions/p1-fox/code
5 10 2 1
((A1A2)A3)
$ dc
5 10 2** 5 2 1** +p
110
10 2 1** 5 10 1** +p
70
The algorithm goes the greedy route, always eliminating the largest dimension. In doing so, it sometimes misses better solutions.
Nice touch with the X~
for concatenating the same string to a list of
integers.
I must say I find the exit say
idiom charming.
Oh yes.