# Adapted from javascript at http://alexle.net/wp-content/uploads/2006/04/matrix.html # Calculate the best parenthization for matrix multiplication using # Dynamic Programming approach. sub find_optimal_chain_for_matrix_multiply ( @rows_cols_interleaved ) { my @rows = @rows_cols_interleaved[ 0 ..^ @rows_cols_interleaved.end ]; my @cols = @rows_cols_interleaved[ 0 ^.. @rows_cols_interleaved.end ]; my \$n = @rows.elems; my @matrix = (^\$n).map({ [ 0 xx \$n ] }); my @sequence = (^\$n).map({ [ 0 xx \$n ] }); # Run the algorithm my \$max_int = 2**31 - 1; for 1..\$n -> \$d { # diagonal --> the length of the chain for ^(\$n-\$d) -> \$i { # sub problems from my \$j = \$i + \$d; @matrix[\$i][\$j] = \$max_int; for \$i..^\$j -> \$k { my \$m = @matrix[\$i ][\$k] + @matrix[\$k+1][\$j] + @rows[\$i] * @cols[\$k] * @cols[\$j]; if \$m < @matrix[\$i][\$j] { @matrix[ \$i][\$j] = \$m; @sequence[ \$i][\$j] = \$k; } } } } # Return a string representing the best parenthesis groupings. # Uses @sequence as a global. sub parenthesize ( \$i, \$j ) { return "A{\$i+1}" if \$i >= \$j; my \$sij = @sequence[\$i][\$j]; return '(' ~ parenthesize( \$i, \$sij ) ~ parenthesize( \$sij+1, \$j ) ~ ')'; } say parenthesize( 0, \$n-1 ); } for \$*IN.lines { my @nums = .split( /\s+/ )ยป.Int; if +@nums < 2 { say "Input must consist of at least two integers."; next; } find_optimal_chain_for_matrix_multiply( @nums ); }