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;

}