Doing Algebra in Code: Looking Past the Details To Focus on the Math

Do you know why it’s so hard to identify the math that we use in everyday life? It’s because of, well, life. The real-life details that surround the problem you’re trying to solve work very hard to obscure the underlying math problem.

I recently worked on a problem where we had to solve a linear equation whose coefficients aren’t known until runtime. There were roughly 14 varying inputs which all had a contribution to make to the slope and constant part of the function, and it became difficult for the whole team to work on it or even reason about it with any real confidence.

The hard part of this was recognizing the algebra beneath layers of domain-specific business rules, but the math problem is ultimately very simple. And I have Vicki Guan of AutoFi to thank for unraveling the most difficult part of the process for me.

Finding the algebra in code

I’m going to use a ridiculous and artificial example, because I want to write about the algebra itself. But I think this example makes the underlying problem more apparent. That problem boils down to a simple case of two linear equations in two variables, so apologies to anybody who came here looking for advanced linear algebra or Galois theory.

Suppose we’re building a survival video game in the mould of the classic Oregon Trail. In our game, the two supplies needed for survival are coffee and flour, so each time a player stops at a trading post, they’re given the option to purchase some amount of flour and some amount of coffee. Purchases are subject to two constraints: The player’s current budget and carrying capacity.

The task at hand is to build a feature that allows the player to purchase the right balance of coffee and flour to (a) spend all of their money and (b) fill their entire carrying capacity. 

The weight and cost constraints on a purchase can be written down in two simple equations:

/* (1) */ priceOfCoffee * poundsOfCoffee + priceOfFlour * poundsOfFlour = totalCost
/* (2) */ poundsOfCoffee + poundsOfFlour = totalPounds

To solve our problem, we need a function that takes in a given set of constraints (priceOfCoffee, priceOfFlour, totalCost, totalPounds) and returns the corresponding poundsOfCoffee and poundsOfFlour values to satisfy the equations.

Method 1: Solve the system of equations with algebraic manipulation

If we can rearrange (1) and (2) above in such a way that it gives us an equation for either poundsOfCoffee or poundsOfFlour expressed as a function of the given constraints, we’ve solved the problem. Here’s how that works using straight-forward substitutions and algebraic manipulation:

// start with (1) from above
priceOfCoffee * poundsOfCoffee + priceOfFlour * poundsOfFlour = totalCost

// replace poundsOfFlour with (totalPounds - poundsOfCoffee) using (2) above
priceOfCoffee * poundsOfCoffee + priceOfFlour * (totalPounds - poundsOfCoffee) = totalCost

// distribute `priceOfFlour` into `(totalPounds - poundsOfCoffee)`
priceOfCoffee * poundsOfCoffee + priceOfFlour * totalPounds - priceOfFlour * poundsOfCoffee = totalCost

// factor `poundsOfCoffee` out of the terms where it occurs
poundsOfCoffee * (priceOfCoffee - priceOfFlour) + priceOfFlour * totalPounds = totalCost

// subtract priceOfFlour * totalPounds from both sides
poundsOfCoffee * (priceOfCoffee - priceOfFlour) = totalCost - priceOfFlour * totalPounds

// divide both sides by (priceOfCoffee - priceOfFlour)
poundsOfCoffee = (totalCost - priceOfFlour * totalPounds) / (priceOfCoffee - priceOfFlour)

Now that we have an equation for poundsOfCoffee, we can write a function that balances the purchase to achieve the specified result:

function balancePurchase(priceOfCoffee, priceOfFlour, totalCost, totalPounds) {
  const poundsOfCoffee = (totalCost - priceOfFlour * totalPounds) / (priceOfCoffee - priceOfFlour);
  const poundsOfFlour = totalPounds - poundsOfCoffee;
  return {
    poundsOfCoffee,
    poundsOfFlour,
  };
}

This works fine, but it has one big disadvantage: It doesn’t make any sense without all that algebra. To determine whether a sign is wrong somewhere, a reader of this code needs to work out all of the algebra again, from scratch. Also, it duplicates logic. There’s surely another place in the code where the cost of the purchase is calculated based on the prices and amounts purchased, and the logic from that function is implicitly buried in this one, albeit inside-out.

Suppose our game’s doing great with beta testers, but there’s been a lot of talk on the forums about sales tax. We absolutely must have sales tax in the next version, or we’ll lose our following and the game will flop. This means we not only have to add sales tax to our cost-calculation function (pretty simple), but we also have to start all over with our purchase balancing algebra to get that function right too.

Method 2: Solve using the existing purchase totals

As I alluded to above, there’s already a function to calculate the total cost of the purchase:

function getTotalCost(priceOfCoffee, priceOfFlour, poundsOfCoffee, poundsOfFlour) {
  const totalForFlour = priceOfFlour * poundsOfFlour;
  const totalForCoffee = priceOfCoffee * poundsOfCoffee;
  return totalForCoffee + totalForFlour;
}

Because this function is linear in the amounts of coffee and flour purchased, we can develop a generic technique for solving linear equations, and apply it to this existing function. First we need a little bit of machinery.

The key to this is a higher-order function that can take in an unknown linear function and return its inverse. We’ll derive such a function starting from the point-slope equation of a line: y - y1 = m * (x - x1) where x and y are the variables, x1 and y1 are particular values for x and y that fit the equation, and m is the slope of the line. We’ll calculate m using the equation m = (y2 - y1) / (x2 - x1), where again (x1, y1) and (x2, y2) are pairs of values that fit the equation.

// point-slope
y - y1 = m * (x - x1)

// distribute m
y - y1 = m * x - m * x1

// add m * x1 to both sides
y - y1 + m * x1 = m * x

// divide both sides by m and flip left & right sides
x = (y - y1 + m * x1) / m

// cancel m from m * x1
x = (y - y1) / m + x1

Using this version, we can get a function that does the opposite of the linear function passed in.

// x1 and x2 must be distinct, valid inputs for linearFunction
function invertLinear(linearFunction, x1, x2) {
  const y1 = linearFunction(x1);
  const y2 = linearFunction(x2);
  const m = (y2 - y1) / (x2 - x1);
  return y => (y - y1) / m + x1;
}

// e.g.
linear = x => 3 * x + 1
inverse = invertLinear(linear, 1, 0)
linear(4)   // 13
inverse(13) // 4

The function arguments are linearFunction and a pair of x values to feed into linearFunction, in case the function doesn’t produce valid output for every number. It will work as long as (a) the function is really linear and (b) the function returns values for both x1 and x2 and (c) x1 and x2 are not the same number.

Having this, we can build a quick utility to solve a linear function for a particular value:

function solveLinear(linearFunction, desiredY, x1, x2) {
  return invertLinear(linearFunction, x1, x2)(desiredY);
}

And finally, to solve our dilemma at the trading post using algebra in code, we just need to apply this solver to the correct linear function. We first construct a new linear function, based on the above getTotalCost function, to calculate the total cost depending on the given constraints and the amount of coffee purchased. Then we use the solver to find out what x value (pounds of coffee) will give the desired y value (total cost).

function balancePurchase(priceOfCoffee, priceOfFlour, totalCost, totalPounds) {
  const linearFunction = function(poundsOfCoffee) {
    return getTotalCost(
      priceOfCoffee,
      priceOfFlour,
      poundsOfCoffee,
      totalPounds - poundsOfCoffee
    );
  }
  const poundsOfCoffee = solveLinear(linearFunction, totalCost, 0, 1);
  const poundsOfFlour = totalPounds - poundsOfCoffee;
  return { poundsOfCoffee, poundsOfFlour };
}

Note that the getTotalCost function embodies equation (1), while we use equation (2) to eliminate the need for poundsOfFlour so that linearFunction is a function of only one variable. This was pretty straight-forward because we only have two equations in two variables, and one of our equations was extremely simple. The next method introduces some more complicated machinery, but the upshot is that it will work for all kinds of systems of linear equations.

Method 3: Solve using linear algebra / matrices

Linear algebra is an extensive topic, so what follows is just a taste. The gist is that we can encode our formulas into matrices and vectors, which have their own arithmetic operations that can be used to calculate values or solve equations. To get started, we can rewrite / format our equations from above:

/* (1) */ priceOfCoffee * poundsOfCoffee + priceOfFlour * poundsOfFlour = totalCost
/* (2) */       1       * poundsOfCoffee +       1      * poundsOfFlour = totalPounds

Each equation multiplies poundsOfCoffee by a certain number, multiplies poundsOfFlour by another number, and adds the results to achieve a total. poundsOfCoffee and poundsOfFlour are the ‘variables’ we’ve been solving for, and the other numbers on the left-hand side are the coefficients applied to each variable by their respective equations. In linear algebra terms, the coefficients will make up the matrix encoding a transformation from an input vector (poundsOfCoffee, poundsOfFlour) into an output vector (totalCost, totalPounds). To calculate totalCost and totalPounds, we multiply the matrix and the input vector together, like so:

$latex 
\begin{bmatrix}
\texttt{priceOfCoffee}& \texttt{priceOfFlour}\\
\texttt{1}& \texttt{1}
\end{bmatrix}
*
\begin{bmatrix}
\texttt{poundsOfCoffee}\\
\texttt{poundsOfFlour}
\end{bmatrix}
=
\begin{bmatrix}
\texttt{totalCost}\\
\texttt{totalPounds}
\end{bmatrix}
$

Though matrix multiplication follows quite simple mechanics, we’ll use the mathjs library from npm. The syntax isn’t quite as readable as we’d like, but we can build some helper functions to hide the details:

// return a matrix based on the prices at a particular trading post
function purchaseMatrix(priceOfCoffee, priceOfFlour) {
  return mathjs.matrix([[priceOfCoffee, priceOfFlour], [1, 1]]);
}

// turn a flat array into a matrix
function vector(values) {
  const rows = values.map(value => [value]);
  return mathjs.matrix(rows);
}

// return the vector product as a flat array
function vectorProduct(matrix, vector) {
  const result = [];
  const product = mathjs.multiply(matrix, vector);
  for (let i = 0; i < vector.size()[0]; i++) {
    result.push(product.subset(mathjs.index(i, 0)));
  }
  return result;
}

With those details sorted out, we can write a function to calculate the totalCost and totalPounds for a given purchase:

function purchaseTotals(priceOfCoffee, priceOfFlour, poundsOfCoffee, poundsOfFlour) {
  const M = purchaseMatrix(priceOfCoffee, priceOfFlour);
  const v = vector([poundsOfCoffee, poundsOfFlour]);
  const [ totalCost, totalPounds ] = vectorProduct(M, v);
  return { totalCost, totalPounds };
}

That’s good and necessary, but it’s not really what we’re after. The reason we’re here is to calculate the appropriate amounts of each commodity to achieve a certain totalCost and totalPounds, and that’s where the linear algebra in code begins to pay off. Multiplication by the purchase matrix is a transformation mapping commodity amounts to totals, and it has an inverse transformation that maps totals to commodity amounts. That inverse is, appropriately enough, achieved by multiplication by the inverse of the purchase matrix.

function balancePurchase(priceOfCoffee, priceOfFlour, totalCost, totalPounds) {
  const M = purchaseMatrix(priceOfCoffee, priceOfFlour);
  const inverseOfM = mathjs.inv(M);
  const v = vector([totalCost, totalPounds]);
  const [ poundsOfCoffee, poundsOfFlour ] = vectorProduct(inverseOfM, v);
  return { poundsOfCoffee, poundsOfFlour };
}

All of the business rules live in the matrix, and in knowing where to put which values to get the correct outcome. To add sales tax to the matrix version, we’d just need to make a small update to the purchaseMatrix function. What’s more impressive, we could almost as easily adapt it to three commodities and three different equations, or five. We’d just have to adjust our matrix a bit and shepherd around some additional variables.

Under the hood, these algebra in code methods are all doing the same thing with varying degrees of abstraction and machinery, but they all apply to the same kind of problem: one where the number of independent equations matches the number of variables, yielding a unique solution. If there are more variables than equations, or if the problem is to optimize certain outcomes rather than match specific values, more advanced techniques like linear programming are called for.

If you enjoyed this post, have a look at more of my writing here!

---

code linear programming math software engineer