p1-moritz

use v6;

# after http://en.wikipedia.org/wiki/Matrix_chain_multiplication#A_Dynamic_Programming_Algorithm
sub matrix-mult-chaining(@dimensions) {

# @cp has a dual function: the upper triangle of the diagonal matrix
# stores the cost (c) for mulplying matrices \$i and \$j in @cp[\$j][\$i],
# \$j > \$i
# the lower triangle stores the path (p) that was used for the lowest cost
# multiplication to get from \$i to \$j.
#
#    wikipedia         this program
#    m[i][j]           @cp[\$j][\$i]
#    s[i][j]           @cp[\$i][\$j]
#
# it makes the code harder to read, but hey, it saves memory!

my @cp;

# a matrix never needs to be multiplied with itself,
# so it has cost 0
@cp[\$_][\$_] = 0 for @dimensions.keys;
my @path;

my \$n = @dimensions.end;
for 1 .. \$n -> \$chain-length {
for 0 .. \$n - \$chain-length - 1 -> \$start {
my \$end = \$start + \$chain-length;
@cp[\$end][\$start] = Inf;  # until we find a better connection
for \$start .. \$end - 1 -> \$step {
my \$new-cost = @cp[\$step][\$start]
+ @cp[\$end][\$step + 1]
+ [*] @dimensions[\$start, \$step+1, \$end+1];
if \$new-cost < @cp[\$end][\$start] {
# cost
@cp[\$end][\$start] = \$new-cost;
# path
@cp[\$start][\$end] = \$step;
}
}
}
}

sub find-path(Int \$start, Int \$end) {
if \$start == \$end {
take 'A' ~ (\$start + 1);
} else {
take '(';
find-path(\$start, @cp[\$start][\$end]);
find-path(@cp[\$start][\$end] + 1, \$end);
take ')';
}
}
return  gather { find-path(0, \$n - 1) }.join;
}

multi MAIN {
my \$line = get;
my @dimensions = \$line.comb: /\d+/;
if @dimensions < 2 {
say "Input must consist of at least two integers.";
} else {
say matrix-mult-chaining(@dimensions);
}
}

multi MAIN ('test') {
use Test;
plan *;
is matrix-mult-chaining(<10 30 5 60>), '((A1A2)A3)', 'wp example';

# http://www.cs.auckland.ac.nz/~jmor159/PLDS210/mat_chain.html
is matrix-mult-chaining(<10 100 5 50>), '((A1A2)A3)', 'auckland';

# an example verified by http://modoogle.com/matrixchainorder/
is matrix-mult-chaining(<6 2 5 1 6 3 9 1 25 18>),
'((A1((A2A3)((A4A5)(A6A7))))(A8A9))', 'modoogle';

done_testing;

}

The largest comment is a confession about dual-using an array of arrays for two semantically disparate ends. Were it not for the comment, this would be a mortal readability sin. As it stands, it's refreshing. The comment even ends with a joke.

Clarity of intent

The fact that the algorithm compares itself with the one on Wikipedia should be considered a definite plus.

Algorithmic efficiency

Since this is the algorithm I had in mind, this is the level of efficiency I had in mind.

Idiomatic use of Perl 6

It is a sign of Perl 6 mastery when \$*IN.get becomes just get (line 59). So is putting a sub in a sub (line 45). Yo dawg.

Let's not forget the "gather around a recursive sub" pattern on line 55. That's a very convenient way to do tree traversal.

[*] @dimensions[\$start, \$step+1, \$end+1] on line 34 is worth ogling a bit. That's a nice use of Perl's slicing and Perl 6's reduction.

I find @dimensions.keys at line 22 to be an interesting choice over the more common ^@dimensions. The former does have a slightly more self-documenting ring to it.

Brevity

Could be shorter, but why complain when the extra space is used to lay things out and to insert comments?