p1-matthias

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 ]);
}

Readability

Various things are vertically aligned. Stylish.

Consistency

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.

Clarity of intent

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.)

Algorithmic efficiency

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.

Idiomatic use of Perl 6

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.

Brevity

The code manages to get the job done in deligtfully few lines without feeling crowded.