Interval DP: matrix chains and partitions

import random
import re

from chain import chain_order


def evaluate(order, dims):
    """The cost of an order string, checking that it names A1 ... An once each, in order."""
    tokens = re.findall(r"\(|\)|A\d+", order)
    assert "".join(tokens) == order, f"unexpected characters in {order!r}"
    pos = 0
    nxt = [1]

    def expr():
        nonlocal pos
        assert pos < len(tokens), f"{order!r} ends too early"
        tok = tokens[pos]
        pos += 1
        if tok.startswith("A"):
            assert int(tok[1:]) == nxt[0], f"{order!r}: expected A{nxt[0]} at this point"
            i = nxt[0]
            nxt[0] += 1
            return dims[i - 1], dims[i], 0
        assert tok == "(", f"{order!r}: unexpected {tok}"
        r1, c1, k1 = expr()
        r2, c2, k2 = expr()
        assert pos < len(tokens) and tokens[pos] == ")", f"{order!r}: a product needs exactly two parts"
        pos += 1
        return r1, c2, k1 + k2 + r1 * c1 * c2

    rows, cols, cost = expr()
    assert pos == len(tokens) and nxt[0] == len(dims), f"{order!r} does not use every matrix exactly once"
    return cost


def slow_cost(dims, i, j):
    if i == j:
        return 0
    return min(slow_cost(dims, i, k) + slow_cost(dims, k + 1, j) + dims[i - 1] * dims[k] * dims[j] for k in range(i, j))


def check(dims, expected=None):
    cost, order = chain_order(list(dims))
    assert evaluate(order, dims) == cost, f"{order!r} does not cost {cost}"
    if expected is not None:
        assert cost == expected, (dims, cost)
    return cost


def test_small_chains():
    """a single matrix, two matrices and the three-matrix pipeline"""
    assert check([10, 20], 0) == 0
    assert check([3, 4, 5], 60) == 60
    assert check([1000, 20, 500, 10], 300_000) == 300_000


def test_six_matrices():
    """the six-matrix chain of the lesson"""
    assert check([12, 40, 8, 50, 6, 30, 16]) == 10_848


def test_random_chains():
    """on 200 random chains, as cheap as the best of every order"""
    rng = random.Random(9)
    for _ in range(200):
        dims = [rng.randint(1, 30) for _ in range(rng.randint(2, 8))]
        assert check(dims) == slow_cost(dims, 1, len(dims) - 1), dims

import { test, assert } from 'mysmartcopilot:test';
import { chainOrder } from './chain.mjs';

// The cost of an order string, checking that it names A1 ... An once each, in order.
function evaluate(order, dims) {
  const tokens = order.match(/\(|\)|A\d+/g) ?? [];
  assert.equal(tokens.join(''), order, `unexpected characters in "${order}"`);
  let pos = 0;
  let next = 1;
  const expr = () => {
    assert.ok(pos < tokens.length, `"${order}" ends too early`);
    const tok = tokens[pos++];
    if (tok.startsWith('A')) {
      assert.equal(Number(tok.slice(1)), next, `"${order}": expected A${next} at this point`);
      next++;
      return [dims[next - 2], dims[next - 1], 0];
    }
    assert.equal(tok, '(', `"${order}": unexpected ${tok}`);
    const [r1, c1, k1] = expr();
    const [, c2, k2] = expr();
    assert.ok(pos < tokens.length && tokens[pos] === ')', `"${order}": a product needs exactly two parts`);
    pos++;
    return [r1, c2, k1 + k2 + r1 * c1 * c2];
  };
  const [, , cost] = expr();
  assert.ok(pos === tokens.length && next === dims.length, `"${order}" does not use every matrix exactly once`);
  return cost;
}

function slowCost(dims, i, j) {
  if (i === j) return 0;
  let best = Infinity;
  for (let k = i; k < j; k++) best = Math.min(best, slowCost(dims, i, k) + slowCost(dims, k + 1, j) + dims[i - 1] * dims[k] * dims[j]);
  return best;
}

function check(dims) {
  const { cost, order } = chainOrder(dims.slice());
  assert.equal(evaluate(order, dims), cost, `"${order}" does not cost ${cost}`);
  return cost;
}

test('a single matrix, two matrices and the three-matrix pipeline', () => {
  assert.equal(check([10, 20]), 0);
  assert.equal(check([3, 4, 5]), 60);
  assert.equal(check([1000, 20, 500, 10]), 300000);
});

test('the six-matrix chain of the lesson', () => {
  assert.equal(check([12, 40, 8, 50, 6, 30, 16]), 10848);
});

test('on 200 random chains, as cheap as the best of every order', () => {
  let seed = 9;
  const random = () => (seed = (seed * 48271) % 2147483647) / 2147483647;
  for (let t = 0; t < 200; t++) {
    const dims = Array.from({ length: 2 + Math.floor(random() * 7) }, () => 1 + Math.floor(random() * 30));
    assert.equal(check(dims), slowCost(dims, 1, dims.length - 1), JSON.stringify(dims));
  }
});