#!/usr/bin/perl -w
# Matrix chain multiplication
# Author: Chao-Kuei Hung http://www.cyut.edu.tw/~ckhung
# License: GPL
#
# This program is part of algotutor. Yet it can also run as a
# stand-alone text mode program that requires no other modules.
# When used as a stand-alone program, it requires as a list
# of arguments alternating numbers and matrix names, like this:
# matrixchain -e ansi 32 A 35 B 24 C 30 D 36 E 25 F 40 G 34 H 35

my (@name, $best);

sub print_expr {
    my ($i, $j) = @_;
    if ($i >= $j) {
	print($name[$i]);
    } else {
	print("(");
	print_expr($i,$best->[$i][$j]{cut});
	print(" * ");
	print_expr($best->[$i][$j]{cut}+1,$j);
	print(")");
    }
}

sub matrixchain {
    my ($chain, $can) = @_;
    my (@dim, $show, $left, $size, $i, $expr);
    my ($cell) = sub { return $show->cell(
	($_[0]+1) % ($#name+2), ($_[1]+$#name+2) % ($#name+2)
    ); };

    while ($#$chain > 0) {
	my ($d, $n) = splice @$chain, 0, 2;
	print " $n:${d}x$chain->[0]";
	push @dim, $d;
	push @name, $n;
    }
    print "\n";
    push @dim, @$chain;

    if (ref $can) {
	$show = Board->new(-canvas=>$can, -width=>$#name+2, -height=>$#name+2,
	    -node_opts=>{ -size=>Vector->new(50,40), -shape=>"rectangle" } );
	map { $cell->(-1,$_)->configure(-text=>$name[$_], -status=>"done"); } 0..$#name;
	map { $cell->($_,-1)->configure(-text=>$name[$_], -status=>"done"); } 0..$#name;
	$expr = $can->createText(@{ $show->rc2xy($#name+2, int(($#name+1)/2) ) },
	    -justify=>"center", -text=>"expr");
    }
    for ($left=0; $left<=$#name; ++$left) {
	$best->[$left][$left] = { val => 0 };
	if (ref $can) {
	    $cell->($left,$left)->configure(-text=>0, -status=>"done");
	    for ($i=$left+1; $i<=$#name; ++$i) {
		$cell->($i,$left)->configure(-status=>"hidden");
	    }
	}
    }
    $can->set_mark(2) if ref $can;
    for ($size=1; $size<=$#name; ++$size) {
	for ($left=0; $left<=$#name-$size; ++$left) {
	    $cell->($left,$left+$size)->configure(-text=>"?", -status=>"focus")
		if ref $can;
	    my ($s, $t);
	    $best->[$left][$left+$size] = { val => 1e99 };
	    for ($i=0; $i<$size; ++$i) {
		$s = $best->[$left][$left+$i]{val} . " + " .
		    $best->[$left+$i+1][$left+$size]{val} . " + " .
		    $dim[$left] . " * " .
		    $dim[$left+$i+1] . " * " .
		    $dim[$left+$size+1];
		$t = eval $s;
		if (ref $can) {
		    $can->itemconfigure($expr, -text=>"$t = $s");
		    $cell->($left, $left+$i)->configure(-status=>"focus");
		    $cell->($left+$i+1, $left+$size)->configure(-status=>"focus");
		    if ($i >= 1) {
			$cell->($left, $left+$i-1)->configure(-status=>"done");
			$cell->($left+$i, $left+$size)->configure(-status=>"done");
		    }
		    $can->set_mark(1);
		}
		if ($t < $best->[$left][$left+$size]{val}) {
		    $best->[$left][$left+$size] = { val=>$t, cut=>$left+$i };
		}
	    }
	    if (ref $can) {
		$t = $best->[$left][$left+$size];
		$t = $t->{val} . "\n" . $name[$t->{cut}] . "|" .  $name[$t->{cut}+1];
		$cell->($left,$left+$size)->configure(-text=>$t, -status=>"done");
		$can->itemconfigure($expr, -text=>"");
		$cell->($left, $left+$size-1)->configure(-status=>"done");
		$cell->($left+$size, $left+$size)->configure(-status=>"done");
		$can->set_mark(2);
	    }
	}
    }

    for ($i=1; $i<=$#name; ++$i) {
	printf "     %2s    ", $name[$i];
    }
    print "\n";
    for ($left=0; $left<$#name; ++$left) {
	print "           " x $left;
	for ($i=$left+1; $i<=$#name; ++$i) {
	    my ($t) = sprintf "%d:%s|%s",
		$best->[$left][$i]{val},
		$name[$best->[$left][$i]{cut}],
		$name[$best->[$left][$i]{cut}+1];
	    printf "%11s", $t;
	}
	print "  $name[$left]\n";
    }
    print_expr(0, $#name);
    print "\n";
}

if ($0 =~ /matrixchain$/) {

my ($chain) = $#ARGV >= 0 ? \@ARGV :
    [qw(32 A 35 B 24 C 30 D 36 E 25 F 40 G 34 H 35)];
matrixchain($chain);

}

1;