Here is my solution to @reggaemuffin's second Coding Challenge. Warning, it's become a pretty long post because there were a lot of tricky parts that I wanted to explain. If you're not a programmer this might bore you to death.
I hope at least to give some other JavaScript developers a little insight in how one could tackle this problem. I'm always open for suggestions and improvements, maybe I can learn a bit from your insights too. Especially on the math part of the problem I feel like I'm overlooking some things.
The problem
@reggaemuffin described the problem as follows:
Implement a Polynomial class taking an a string formula that abides to these specifications:
- parse the polynomial given as a string, f.e.
+1x^0 -5x^1 +3x^2- implement a few methods, add, substract, multiply, divide
- implement the standart to-string method of you language to give back a polynomial in above format
Remarks:
- The format is pretty easy to parse. If you want a challenge, try accepting more loose polynomials like
1+2xor3x^{12}-6 x^2.- Try adding more methods, derive and integrate will be fun.
- Bonus points for:
--handling edge cases
--good coding practices and modularity
--useful and meaningful tests
--beautiful (readable, self-documenting) code
I am not a math wizard at all, so I'm not going to add any derive or integrate methods. I'm also skipping subtract and divide as they should be trivial after implementing add and multiply.
I will try to parse looser formulas, although I don't understand what the curly braces are for so I'm going to ignore them (specifications unclear).
As for tests, I know they are very important in production code, but they are not a challenge to me. The problem at hand definitely is though, and it's taking me a lot of time already. I'm omitting tests.
Creating a class
As per specification, our class will have roughly this outline.
class Polynomial {
constructor(input) {
// Parse the input into something to do math with
}
toString() {
// return the parsed input back as a string
}
add(polynomial) {
// add the polynomial to the current polynomial
}
multiply(polynomial) {
// multiply the polynomial with the current polynomial
}
}
Storing the Polynomial in numbers
First we have to decide how exactly to store the polynomial in such a way that we can do mathematical operations on it. Let's take the following expression as an example to dissect:
-3x^3 + 15x^2 + 5x - 12
We can split that into these groups:
-3x^3, +15x^2, +5x, -12
Or, in other words, of x to the power 3 there are -3 occurences, and of x to the power 2 there are 15 occurences. So really we're just counting powers. To do the same with the other two groups we rely on the mathematical fact that x^1 equals x and x^0 equals 1. So of x with the power 1 there are 5 and of x to the power 0 there are -12.
This polynomial can be expressed in a simple JavaSript object (or rather a Map, as our data matches this description)
{
3: -3,
2: 15,
1: 5,
0: -12
}
Parsing the formula
Now that we know how to store the Polynomial, we can write some code. First we want to remove all whitespaces and split the resulting string into the different groups using a regular expression:
/[+-]?\d+x?(\^\d+)?/g)
In simple terms, this regex looks for parts in the input that contain an optional + or - followed by one or more numbers, followed by an optional x, which in turn might be followed by an optional ^ and more numbers.
Then we loop through these groups and parse them to get the numbers for the coefficient and power, reducing them into a counter Map as shown above.
constructor(formula) {
const whitespace = /\s+/g;
const groups = /[+-]?\d+x?(\^\d+)?/g;
this.count = formula.replace(whitespace, '')
.match(groups)
.reduce((all, group) => {
const [coefficient, power] = this._parseGroup(group);
return all.set(power, coefficient);
}, new Map);
}
Parsing each group is done by splitting the group at the x and converting both sides to numbers.
_parseGroup(group) {
const [coefficient, power] = group.split('x');
return [Number(coefficient), this._parsePower(power)];
}
When parsing the power we have to check for implicit powers. If there was no x the right side is undefined (power is 0), if there is an x but no power the right side is an empty string (power is 1).
_parsePower(power) {
switch (power) {
case undefined:
return 0;
case '':
return 1;
default:
return Number(power.replace('^', ''));
}
}
Returning the Polynomial as a string
Now that we know the rules and have a count of all the powers and coefficients, we can turn that back into a string.
For this, first we loop through the counter, sort them by power (after addition they might be out of order) and convert each group back to a string representation. After joining them together, we have an ugly formula in the format +2x^2+4x^1-3x^0.
We prettify that a bit before returning.
toString() {
const formula = [...this.count.entries()]
.sort((a, b) => b[0] - a[0])
.map(this._toGroup)
.join('');
return this._prettifyFormula(formula);
}
When converting to a group string, we need to take in account that minus signs are part of the numbers but the plus signs aren't.
_toGroup([power, coefficient]) {
const plus = (coefficient >= 0) ? '+' : '';
return `${plus}${coefficient}x^${power}`;
}
Prettifying pretty much speaks for itself. The only notable part is the regex operationsInBetween, where we use a negative lookbehind to check for a + or - but only if it's not at the start of the line.
_prettifyFormula(formula) {
const operationsInBetween = /(?!^)([+-])/g;
const plusAtStart = /^\+/;
return formula.replace('^1', '')
.replace('x^0', '')
.replace(operationsInBetween, ' $1 ')
.replace(plusAtStart, '');
}
Adding
Adding polynomials is quite straight forward. Take this example:
5x + 3 + 3x^2 -5x + 5
For each power in the second group, we check if one was already present in the first group. If not, we add that power with its coefficient to our counter. If it is present we add up the coefficients of the two.
We end up with:
3x^2 + 8
add(polynomial) {
for (const [power, coefficient] of polynomial.count) {
const resultingCoefficient = (this.count.get(power) || 0) + coefficient;
this.count.set(power, resultingCoefficient);
}
}
Multiply
To multiply polynomial, we not only multiply the coefficients but also add up the powers. For example:
5x^2 + 3 * 3x
Here each group on the left is multiplied by 3x, which changes the powers too (x^2 times x is x^3)
In most cases we need to delete the old entry from our counter and add in a new one with the new power. For powers of 0 this isn't necessary, but it can't hurt. I prefer a little redundancy over yet another exception.
A tricky case here is when two multiplications end up with the same power. For example:
3x^2 + x * 3x - 2
We end up with two groups that result in a power of 2 (3x^2 * -2 and x * 3x). These two need to be added to each other, so before we write the "new" power in our counter we need to check if one is already present. Thankfully we already solved that problem earlier.
Oh and make sure to iterate over a copy of the counter, otherwise you'll be adding new values while still iterating and you end up in an infinite loop. This kills the browser.
multiply(polynomial) {
for(const [power, coefficient] of new Map(this.count)) {
this.count.delete(power);
for(const [newPower, newCoefficient] of polynomial.count) {
const resultingPower = power + newPower;
const existingCoefficient = this.count.get(resultingPower) || 0;
const resultingCoefficient = existingCoefficient + coefficient * newCoefficient;
this.count.set(resultingPower, resultingCoefficient);
}
}
}
Demo
Now that we have all the methods, let's put it all together. This jsFiddle has the code, plus a function in the bottom that creates some Polynomials and adds/multiplies them. It logs the results to the console. (I wanted to add a UI but I have plenty of other apps to build). Play around with it by changing the input formulas in the top of the script.
I hope you enjoyed and/or learned something! I sure did both, this wasn't very easy but it was a lot of fun figuring out.