Matrix Chain Multiplication Order Optimisation

matrix_chain_mult_opt.js

class MatrixRes {
	constructor(rows, cols) {
		this.rows = rows;
		this.cols = cols;
	}

	sizeAfterMultiplyWith(other) {
		assert(this.canMultiplyWith(other));
		return new MatrixRes(this.rows, other.cols);
	}

	canMultiplyWith(other) {
		return this.cols == other.rows;
	}

	timeToMultiplyWith(other) {
		var output = this.sizeAfterMultiplyWith(other);
		var output_cells = output.rows * output.cols;
		return output_cells * this.cols * other.rows;
	}
}

function createResArrayFromIntArray(arr) {
	var res = [];
	var last = arr[0];
	for (var i = 1; i < arr.length; i++) {
		res.push(new MatrixRes(last, arr[i]));
		last = arr[i];
	}
	return res;
}

var assert = require("assert");

{
	var A = new MatrixRes(2, 2);
	var B = new MatrixRes(2, 1);
	assert(A.sizeAfterMultiplyWith(B).rows = 2);
	assert(A.sizeAfterMultiplyWith(B).cols = 1);
}

{
	var arr = createResArrayFromIntArray([2, 2, 1, 1]);
	assert(arr.length == 3);
	assert(arr[0].rows == 2);
	assert(arr[0].cols == 2);
	assert(arr[1].rows == 2);
	assert(arr[1].cols == 1);
	assert(arr[2].rows == 1);
	assert(arr[2].cols == 1);
}

function findOptimalParenthes(arr) {
	var cache = {};
	return findOptimalParenthes_aux(arr, cache);
}

function findOptimalParenthes_aux(arr, cache) {
	var cache_id = arr.map(function(a) {
		return a.rows + "x" + a.cols;
	}).join("*");

	if (cache[cache_id]) {
		return cache[cache_id];
	}

	var best;
	if (arr.length == 1) {
		console.log("Leaf @ 1");
		best = {
			result: arr,
			score: 0
		};
	} else if (arr.length == 2) {
		console.log("Leaf @ 2");
		best = {
			result: [ arr ],
			score: arr[0].timeToMultiplyWith(arr[1])
		};
	} else {
		console.log("Finding best way to split " + cache_id);

		for (var i = 0; i < arr.length - 1; i++) {
			var left = arr.slice(0, i + 1);
			var right = arr.slice(i + 1, arr.length);

			var left_res = findOptimalParenthes_aux(left, cache);
			var right_res = findOptimalParenthes_aux(right, cache);
			var score = left_res.score + right_res.score;

			if (!best || score < best.score) {
				best = {
					result: left_res.result.concat(right_res.result),
					score: score
				}
			}
		}
	}

	assert(best);

	cache[cache_id] = best;
	return best;
}

console.log("all good!");

function prettifyGroupings(arr) {
	if (arr.rows) {
		return arr.rows + "x" + arr.cols;
	} else {
		return arr.map(function(a) {
			return "(" + prettifyGroupings(a) + ")";
		}).join(" * ");
	}
}

var res = findOptimalParenthes(createResArrayFromIntArray([ 10, 100, 5, 50 ]));
console.log(prettifyGroupings(res.result));