Finding simplest solution to list equality python

Question

I am looking for a module or a function to write that does the following in Python:

Say I have two matrices:

left = ['2B', '1A', '2A+1B']
right = ['8C', '3C', '2D']

I want to find the smallest whole numbers for A, B, C, and D (all must be greater than 0) such that

left = right

So, in this case, we have:

2*B = 8*C
A = 3*C
2*A + B = 2*D

Therefore,

A = 3
B = 4
C = 1
D = 5

My matrices are formatted as shown above - they are lists of strings with each capital letter needed to be solved for.

The matrices can be arbitrary size, I just chose length 3 as an example.

Any ideas? Thanks!

EDIT: Someone in the comments made a good point. I guess there is a possibility that there are two solutions, one with A being "smallest" and another with B being "smallest". But in my case, I am using this as a chemical equation balancer, so as far as I know this can never happen - there should always be one correct, smallest solution.

Answer 1

In general, you are trying to solve a system of equations over the integers, which is no simple task (check out this paper).

However there are some tools that can help, assuming you put in the work to transform your lhs, rhs lists into a matrix representing your system.

The fantastic SymPy package is a good place to start, they have a set of solvers which allow you to specify the system along with external constraints (like being a positive integer).

Note that in your example, you have four unknowns and three equations, meaning that your solution will have at least one free variable, which will add some complexity to your overall solution.