Matrix chain multiplication test cases

Daily Programmer - Matrix Chain Multiplication.md

Description

Consider the problem of matrix multiplication. A matrix A of shape (n, m) may be multiplied by a matrix B of shape (m, p) to produce a new matrix A * B of shape (n, p). The number of scalar multiplications required to perform this operation is n * m * p.

Now consider the problem of multiplying three or more matrices together. It turns out that matrix multiplication is associative, but the number of scalar multiplications required to perform such operation depends on the association.

For example, consider three matrices of the following shapes:

A: (3, 5)
B: (5, 7)
C: (7, 9)

The matrix multiplication (A * B) * C would require 294 scalar multiplications while the matrix multiplication A * (B * C) would require 450 scalar multiplications.

The challenge is to find the optimal order for a chain of matrix multiplications given the shapes of the matrices.

Formal Inputs and Outputs

Your program should accept as input the number of matrices followed by their shapes. For the example above, the inputs would be:

3
3 5
5 7
7 9

Your program should output the optimal number of scalar multiplications and the association tree, where the leaves of the tree are the indices of the matrices. So for the example above, the outputs would be:

294
((0, 1), 2)

where 0 refers to the matrix A, 1 refers to B and 2 refers to C. Note that matrix multiplication is not commutative, so the leaves of the tree will always be in order.

Challenge Inputs

Challenge 1:

4
14 14
14 2
2 4
4 5

Challenge 2:

8
9 16
16 4
4 1
1 7
7 2
2 11
11 4
4 16

Challenge 3:

16
12 11
11 6
6 2
2 10
10 13
13 11
11 7
7 8
8 13
13 3
3 10
10 4
4 8
8 3
3 5
5 8

Bonus

An optimizer is no good if it takes longer than the solution it finds. Simply trying all combinations requires a runtime of O(2^(n)). A dynamic programming solution exists with a runtime of O(n^(3)), and the best known algorithm has a runtime cost of O(n * log(n)). Can you find these optimized solutions?

The following link contains additional test cases for 32, 64, and 128 matrices: https://gist.github.com/cbarrick/ce623ce2904fd1921a0da7aac3328b37

Hints

This is a classic problem taught in most university level algorithms courses. Mosts textbooks covering dynamic programming will discuss this problem. It even has its own Wikipedia page.

Finally

Have a good challenge idea?

Consider submitting it to /r/dailyprogrammer_ideas

input_004.txt

4
14 14
14 2
2 4
4 5

input_008.txt

8
9 16
16 4
4 1
1 7
7 2
2 11
11 4
4 16

input_016.txt

16
12 11
11 6
6 2
2 10
10 13
13 11
11 7
7 8
8 13
13 3
3 10
10 4
4 8
8 3
3 5
5 8

input_032.txt

32
3 11
11 16
16 4
4 4
4 3
3 6
6 13
13 7
7 9
9 3
3 6
6 8
8 3
3 3
3 1
1 1
1 4
4 7
7 7
7 7
7 15
15 12
12 3
3 4
4 1
1 1
1 5
5 15
15 6
6 9
9 10
10 1

input_064.txt

64
13 6
6 7
7 12
12 14
14 7
7 7
7 5
5 13
13 5
5 11
11 11
11 15
15 11
11 3
3 1
1 7
7 11
11 15
15 6
6 8
8 3
3 7
7 2
2 3
3 13
13 9
9 11
11 14
14 3
3 4
4 9
9 16
16 3
3 16
16 13
13 2
2 5
5 14
14 10
10 4
4 9
9 15
15 4
4 16
16 14
14 13
13 4
4 12
12 9
9 11
11 6
6 14
14 9
9 6
6 14
14 2
2 7
7 3
3 4
4 4
4 12
12 2
2 5
5 16

input_128.txt

128
3 7
7 13
13 12
12 6
6 10
10 8
8 9
9 12
12 5
5 9
9 3
3 7
7 13
13 13
13 12
12 12
12 1
1 9
9 10
10 3
3 5
5 10
10 8
8 8
8 15
15 9
9 4
4 8
8 6
6 7
7 2
2 14
14 4
4 10
10 1
1 1
1 7
7 2
2 16
16 14
14 7
7 1
1 16
16 3
3 3
3 9
9 13
13 16
16 8
8 7
7 2
2 12
12 14
14 16
16 5
5 12
12 7
7 3
3 16
16 2
2 15
15 15
15 8
8 1
1 3
3 11
11 7
7 6
6 6
6 1
1 8
8 10
10 11
11 5
5 8
8 8
8 5
5 1
1 12
12 14
14 10
10 8
8 2
2 8
8 4
4 7
7 9
9 11
11 1
1 1
1 5
5 7
7 7
7 12
12 13
13 12
12 5
5 14
14 12
12 13
13 11
11 9
9 5
5 3
3 1
1 14
14 16
16 15
15 6
6 14
14 6
6 11
11 7
7 11
11 7
7 16
16 15
15 1
1 16
16 2
2 14
14 2
2 10
10 9
9 8
8 15
15 7
7 15

Thanks for posting this. Could you please include the answers as well for verification?

Wow, I wrote this up ages ago.

Do you plan on using it? I don't really have time to write a solver until maybe this weekend.

If you do plan on using this, I'll make time to write the solver and get the answers.

The solutions is a textbook dynamic programming problem.

Here are my solutions:
input_004.txt : 572
input_008.txt : 496
input_016.txt : 2048
input_032.txt : 1459
input_064.txt : 4784
input_128.txt : 8851

I did actually write a solver back in 2020, but I had apparently forgotten about it by the time I commented in 2021.

Thanks @artisanbk - Your answers are the same ones I get. Though I suppose the prompt also asks to provide the actual chain.

For the record, my answers are below. The 128 size takes 500ms on my Apple M1 Pro.

$ python3 --version
Python 3.14.3

$ uname -a
Darwin <redacted> 25.2.0 Darwin Kernel Version 25.2.0: Tue Nov 18 21:09:40 PST 2025; root:xnu-12377.61.12~1/RELEASE_ARM64_T6000 arm64 arm Darwin

$ time python3 ./matrix_chain.py < input_004.txt
572
((0, 1), (2, 3))
python3 ./matrix_chain.py < input_004.txt  0.02s user 0.01s system 87% cpu 0.034 total

$ time python3 ./matrix_chain.py < input_008.txt
496
((0, (1, 2)), ((((3, 4), 5), 6), 7))
python3 ./matrix_chain.py < input_008.txt  0.02s user 0.01s system 87% cpu 0.039 total

$ time python3 ./matrix_chain.py < input_016.txt
2048
((0, (1, 2)), ((((((((((((3, 4), 5), 6), 7), 8), 9), 10), 11), 12), 13), 14), 15))
python3 ./matrix_chain.py < input_016.txt  0.03s user 0.01s system 88% cpu 0.040 total

$ time python3 ./matrix_chain.py < input_032.txt
1459
(0, (1, (2, (3, (4, (5, (6, (7, (8, (9, (10, (11, (12, (13, (14, (15, ((((((((16, 17), 18), 19), 20), 21), 22), (23, 24)), (25, (26, (27, (28, (29, (30, 31)))))))))))))))))))))))
python3 ./matrix_chain.py < input_032.txt  0.03s user 0.01s system 88% cpu 0.048 total

$ time python3 ./matrix_chain.py < input_064.txt
4784
((0, (1, (2, (3, (4, (5, (6, (7, (8, (9, (10, (11, (12, (13, 14)))))))))))))), ((((((((((((((((((((((((((((((((((((((((((((((((15, 16), 17), 18), 19), 20), 21), 22), 23), 24), 25), 26), 27), 28), 29), 30), 31), 32), 33), 34), 35), 36), 37), 38), 39), 40), 41), 42), 43), 44), 45), 46), 47), 48), 49), 50), 51), 52), 53), 54), 55), 56), 57), 58), 59), 60), 61), 62), 63))
python3 ./matrix_chain.py < input_064.txt  0.07s user 0.01s system 95% cpu 0.085 total

$ time python3 ./matrix_chain.py < input_128.txt
8851
((0, (1, (2, (3, (4, (5, (6, (7, (8, (9, (10, (11, (12, (13, (14, (15, 16)))))))))))))))), ((((((((((((((((((((((17, 18), 19), 20), 21), 22), 23), 24), 25), 26), 27), 28), 29), 30), (31, (32, (33, 34)))), (35, (((36, 37), (38, (39, (40, 41)))), ((((((((((42, 43), 44), 45), 46), 47), 48), 49), 50), (51, (52, (53, (54, (55, (56, (57, (58, (59, (60, (61, (62, 63))))))))))))), ((64, (65, (66, (67, (68, 69))))), (((((70, 71), 72), 73), (74, (75, (76, 77)))), ((((((78, 79), 80), 81), 82), (83, (84, (85, (86, (87, 88)))))), (89, (((((((((((((((90, 91), 92), 93), 94), 95), 96), 97), 98), 99), 100), 101), 102), 103), 104), ((((105, 106), 107), 108), (109, (110, (111, (112, (113, (114, (115, (116, 117)))))))))))))))))), (((118, 119), 120), 121)), 122), 123), 124), 125), 126), 127))
python3 ./matrix_chain.py < input_128.txt  0.46s user 0.03s system 98% cpu 0.495 total