BUGFIX-66

Bug 24: Suboptimal Matrix Multiplication Tree

This code determines how to multiply n matrices such that the number of multiply-adds is minimized.
It takes as input the row/column counts of the n matrices, expressed as a slice of n+1 integers (rows).
Matrix i (for 0 <= i < n) has rows[i] rows and rows[i+1] columns, as required by matrix multiplication.
The output is a binary tree. Each leaf node of the tree is an integer i representing matrix i.
Each non-leaf node of the tree represents the multiplication of two matrices to yield a single matrix.
The minimum cost to multiply k consecutive matrices is found by evaluating all k-1 two-way splits.
The minimum cost is recorded in a table for every instance of k consecutive matrices (2 <= k <= n).
Each non-leaf node of the output tree corresponds to a two-way split of minimum cost.

Fix The Tiny Bug In This Go Code:

type MatMulNode struct { Left any Right any } func MatMulTree(rows []int) any { n := len(rows) - 1 if n < 1 { return nil } var ( costs = make([]int, n*n) splits = make([]int, n*n) ) for add := 1; add < n; add++ { for lo := 0; lo < n-add; lo++ { var ( hi = lo + add outer = rows[lo] * rows[hi+1] min = int(^uint(0) >> 1) split int ) for i := lo + 1; i <= hi; i++ { cost := outer * rows[i] cost += costs[lo*n+i] cost += costs[i*n+hi] if min > cost { min = cost split = i } } i := lo*n + hi costs[i] = min splits[i] = split } } var tree func(lo, hi int) any tree = func(lo, hi int) any { if lo == hi { return lo } i := splits[lo*n+hi] return &MatMulNode{ Left: tree(lo, i-1), Right: tree(i, hi), } } return tree(0, n-1) }

To receive a hint, submit unfixed code.