Download the raw code.
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.
Nothing to complain about here.
The fact that the algorithm compares itself with the one on Wikipedia should be considered a definite plus.
Since this is the algorithm I had in mind, this is the level of efficiency I had in mind.
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.
Could be shorter, but why complain when the extra space is used to lay things out and to insert comments?