Expanding powers of expressions of the form ax+b

Question

I solved the following problem:

Write a function expand that takes in an expression with a single, one character variable, and expands it. The expression is in the form (ax+b)^n where a and b are integers which may be positive or negative, x is any one-character long variable, and n is a natural number. If a = 1, no coefficient will be placed in front of the variable. If a = -1, a "-" will be placed in front of the variable. The expanded form should be returned as a string in the form ax^b+cx^d+ex^f... where a, c, and e are the coefficients of the term, x is the original one character variable that was passed in the original expression and b, d, and f, are the powers that x is being raised to in each term and are in decreasing order. If the coefficient of a term is zero, the term should not be included. If the coefficient of a term is one, the coefficient should not be included. If the coefficient of a term is -1, only the "-" should be included. If the power of the term is 0, only the coefficient should be included. If the power of the term is 1, the caret and power should be excluded.

Examples:

expand("(p-1)^3");      // returns "p^3-3p^2+3p-1"
expand("(2f+4)^6");     // returns "64f^6+768f^5+3840f^4+10240f^3+15360f^2+12288f+4096"
expand("(-2a-4)^0");    // returns "1"
expand("(-12t+43)^2");  // returns "144t^2-1032t+1849"
expand("(r+0)^203");    // returns "r^203"
expand("(-x-1)^2");     // returns "x^2+2x+1"

My solution passed all tests but I would like to know how it can be improved.

function expand(str) {
    const fac = n => n < 2 ? 1 : n * fac(n - 1);
    let result = '', [_, a, x, b, n] = str.match(/\((-?\d*)([a-z])([-+]\d+)\)\^(\d+)/);

    a = a ? a == '-' ? -1 : parseInt(a) : 1;
    b = parseInt(b); n = parseInt(n);

    for (let i = n; i >= 0; i--) {
        let k = n - i;
        let c = !b && k > 0
            ? 0
            : a**i * b**k * (k == 0
                ? 1
                : fac(n) / (fac(k) * fac(n - k)));

        if (Math.abs(c) == 1 && i > 0) c = c > 0 ? '+' : '-';
        else c = c > 0 ? `+${c}` : c;
        if (c) result += c;

        if (i > 0 && c) result += x;
        if (i > 1 && c) result += `^${i}`;
    }

    return result[0] == '+' ? result.substr(1) : result;
}

I got this problem from a coding challenges site. https://www.codewars.com/kata/binomial-expansion All the context that i had to solve it came from the description of the task.

I did not try to obfuscate the code. As Roland Illig stated, most of the single-letter variables come from the task. Variables a, x, b, n come from the parts of the input expression of the form (ax+b)^n. Variable k comes from a math formula n!/(k!(n-k)!) for the binomial coefficient. Variable c is the coefficient of the term being formed, and its mentioned in ax^b+cx^d+ex^f. So names come from problem's domain.

I mostly just do coding challenges for fun, and I like to golf things a bit. I concede the code lacks readability though.

My main concern is that small numbers like 203 have large factorials and produce overflow. One of the test cases is expand("(r+0)^203"); // returns "r^203". I did not wanted to treat this case separately. Hence I used conditions !b && k > 0 and k == 0 to avoid calculating factorials for "large" n when b == 0. I would like to change this with a better approach for calculating the binomial coefficients. Sadly I don't know enough math.

If someone solves this problem differently I would love to see their code.

I don't have too much experience writing questions in stackexchange and English is not my native language. Tried to format the text to the best of my ability. Thanks all for your patience.

Answer 1

You don't need the special case for k == 0. When k == 0, the result of the other expression will be 1 as well.

For this sequence of binomial coefficients you don't need to calculate the full fak expression each time. You can also start with c = a ** i, and then, for each k, multiply by (n - k) / (k + 1) * b / a. That's a bit faster and provides less risk of producing numeric overflows, which would result in slightly incorrect coefficients. The Wikipedia article on binomial coefficients should explain this in more detail.

Answer 2

Due to the lack of real context here (and issues I'll mention later), I can't really speak to the algorithm. I'll just focus on style.

First, you need to take far greater care in creating meaningful names. This is incredibly hard to comprehend; and naming is the biggest contributor to the problem.

Take a step back, pretend you didn't write this, and look at

let result = '', [_, a, x, b, n] = str.match(/\((-?\d*)([a-z])([-+]\d+)\)\^(\d+)/);

What are a, x, b, and n? Because they're coming from a regex match, they aren't self-descriptive. You need to give them proper names so that people like me (and others reading your code) can know the intent of the variable at a glance without needed to dig through and "discover" what they're for. I can't give suggestions due to the lack of context, but any names would be better than the single-letters being used now.

If the line gets long, split it up. Do the deconstruction on a second line if need-be.

---

I'm not a fan of your use of nested ternaries here. A line like

a = a ? a == '-' ? -1 : parseInt(a) : 1;

is unfortunate and takes longer to comprehend than it should, but is still mostly legible. At the very least, I'd add some brackets in so the grouping is more obvious:

a = a ? (a == '-' ? -1 : parseInt(a)) : 1;

or maybe, split that off into a function (local or otherwise):

function magnitude(a) {
    return a == '-' ? -1 : parseInt(a);
}

. . .

a = a ? magnitude(a) : 1;

At least now the line is simplified, and there's a name associated with part of the operation (magnitude was a bad guess. You know the intent so you'll be able to come up with a better name).

On the other hand though,

let c = !b && k > 0
    ? 0
    : a**i * b**k * (k == 0
        ? 1
        : fac(n) / (fac(k) * fac(n - k)));

is bad. You are attempting to cram far too much functionality into too small of a space. Between the lack of proper names and the density, this is very hard to comprehend. I would definitely split this up. Maybe split it over a couple lines (with descriptively-named variables holding intermediate results), or maybe even split some off into a function.

Along the same theme, you also have lines like

let result = '', [_, a, x, b, n] = str.match(/\((-?\d*)([a-z])([-+]\d+)\)\^(\d+)/);

b = parseInt(b); n = parseInt(n);

There's little need to put them on the same line like this. I always advocate for declarations to be split over multiple lines in most cases (with the exception being maybe a simple destructuring).

I would split these up:

let [_, a, x, b, n] = str.match(/\((-?\d*)([a-z])([-+]\d+)\)\^(\d+)/);
let result = "";

let b = parseInt(b);
let n = parseInt(n);

---

---

Overall, I would encourage you to spend far more time practicing making your code readable. Practice putting yourself in the shoes of someone who has never seen your code before. This can be hard to do, but allows you to find your own readability problems. I would also like to emphasize that dense, packed, small code is not good in most scenarios. If code needs to be minified, it can be run through a minifier after the fact. Your base source should be readable so it can be maintained into the future.

---

It was pointed out that a, x, b, and n are pulled directly from the question, so they're appropriate. If possible I still think they should have better names, but if those are the accepted names to be used in the math equation, or they're too arbitrary for proper names, then yes, they're fine. k and c though both seem like they're not directly related to the equation, so better name there would help.

Answer 3

This fac(n) / (fac(k) * fac(n - k) is an inefficient way to calculate n choose k. n choose k requires 2min(k, n-k) multiplications, yours does 2n multiplications. You iterate k from 0 to n, so yours does 2n^2+2n total multiplications over all coefficients -- the other one does about 1/4 of that.

Calculating a binomial coefficient of (a,b) is something that has limited inputs and outputs, and is greatly suited to being a function. Write that function.

I'd consider writing a term concept. A term is a coefficient, letter, and power of the letter; how that structure is defined is up to you.

Write code that prints a term, instead of mixing it in with the rest of the logic -- the single responsibility principle.

So you'd have code that (a) calculates n choose k, (b) given a linear term and a constant coefficient and n and k generates a binomial output term.

Your main loop is then "for each i from 0 to n, generate binomial term, print binomial term".

I'd also split the string-parsing code from the main body. Parsing a string "(ax+b)^n" into components is nearly completely orthogonal to the rest of the function's tasks.

Write a function that does that, and only that.

So, in pseudo code:

 function task( string input ) 
   [linear_coeff, variable, constant_coeff, exponent] = a_times_x_plus_b_pow_n_parse(input);
   for ( k from exponent downto 0 )
     output_coefficient = binomial_coefficient( linear_coeff, constant_coeff, k, exponent )
     term = make_term( output_coefficient, variable )
     print_term( term )

now write a_times_x_plus_b_pow_n_parse, binomial_coefficient, make_term and print_term functions.

The big difference is that someone reading your code can see what everything is and what each step is supposed to do. In real production, each of those functions can be reasonably unit tested.

Answer 4

Lets move above JavaScript 101

To OP, I first must address the quality of some parts of some of the given answers that concern me.

I am continually shocked at the misunderstanding of JavaScript here in Code Review, Sorry if I rub some the wrong way but please, we are professionals and our answers should reflect that fact.

Issues

• The naming critique is nit picking and not worthy of a mention as the abstract is not in the realm of natural language.

• The critique of the nested ternaries is a worry, particularly in this problem as it deals with JS strings and alternatives ignore the need to avoid string building concatenation overhead.

  I would expect a first year JS101 student to be thrown by nested ternaries, but not professionals, the ongoing emphasize in this forum on avoiding them makes it look like an undergrad hangout.

• No one noticed the precision problem!!!!

The review

I found your function to be of good quality, naming is kept simple and in line with what one would expect from a mathematician. Due to the nature of the problem I would not expect someone without that type of knowledge to modify or get near the function.

There are some simple style problems and can be DRY er

The only major issue is that there is no (implied or direct) accounting for the the precision issue,

Number precision

I am surprised that your function passes all the tests because the upper limit of the polynomial order is well above the floating point (Double) precision of JavaScript Numbers

Lets start with the most inefficient section of your code. The function you call fac that generates the factorial sequence.

The size of value grows very quickly with f(n) = f(70) = 1.197857166996989e100 that is close enough to a google to be called a 1.2 google

If we consider that Number.MAX_SAFE_INTEGER = 9.007199254740991e15 is 85 orders of magnitude below the 71st factorial any integer calculations around this range are going to produce rounding errors.

Ambiguous results due to precedence

This becomes even more pronounced as integer math seriously breaks down when we pass the precision limit.

For example lets strip out some of your code and look at the second line in the for loop. Substituting some constants to demonstrate the problem

const fac = n => n < 2 ? 1 : n * fac(n - 1);
const a = 3, b = 13, n = 23, i = 11;
const k = n - i;
const c = !b && k > 0 ? 0 : a**i * b**k * (k === 0 ? 1 : fac(n) / (fac(k) * fac(n - k)));

In this special case the last line assigning to c has some redundancy that one would naturally reduce to the following line

const c1 = a**i * b**k *  fac(n) / (fac(k) * fac(n - k));

We have not changed the equation, we have simply removed a brackets that separated the ternary with clause (k === 0 ? ...) (BTW could have been (!k ? ...).

However due to the way the rounding error is propagated the two lines c, c1 will return two different values

console.log(c) //  5.580277237278821e+24
console.log(c1) // 5.580277237278822e+24
console.log(c === c1) // false

The different is minor and inconsequential in the order we are using, ~1 billion apart, but as the result is a string and as there are many ways to correctly arrange the precedence of the calculations there are many results that are about correct yet would not pass a string comparison.

Why did your function pass?

For high order polynomials getting the correct answer, is either,

1. Just pure luck,
2. The test is inclusive of all rounding errors (seriously doubt that)
3. The test expects that you use BigInt in the calculations to avoid loss of precision (maybe but as you have passed all tests, my guess is that this is not so)
4. You are never passed a polynomial above the precision range of a double that can not be optimized. eg "(x+0)^204" does not suffer precision problem as all but the first coefficients are 0 and the first is 1 with the result "x^204"

Rewrite

If we consider that option 4 is the reality of the problem then we have a handy optimization available by using a lookup for the factorial sequence rather than calculating it of each coff. Limiting it to Number.MAX_SAFE_INTEGER we can cover that range up to fac(24)

PLEASE NOTE that this is the upper limit and that as the order approaches 24 the chance of precision error increases depending on the size of the values of a and b. The order 24 represents the max order that may return reliable results, not the max order that will. eg (12345235423875623537345x+1)^1 will likely fail.

Rewriting your function with some changes to address style and performance

• Use Number rather than parseInt
• Use constants for values that do not change
• Use the name p (power) or o (order) to replace n. I opt for 'p' as o is too near 0 for me (bad eyesight)
• Replace x with name
• Drop the unneeded assignment to _ underscore in the destructure declaration. eg const [ _, a, b] = [1,2,3] can also be written as const [ , a, b] = [1,2,3] you do not need to define unwanted items
• Rearrange the declarations a little. Assign the String.match to an array and then destructure to constants rather than variables.
• Avoiding the string building overhead of concatenating strings by using an array, to hold the coefficients (as strings) that is joined on the return to avoid overhead due to the need to iterate and reassign each time you concat a string variable.
• To further avoid the string building overhead we need to create a coefficient string in one expression and push that to an array of strings. That means we have no choise but to use NESTED ternaries
• Use the less noisy while loop and move the top and bottom coefficient out of the loop and be handled as special cases.
• Add tests for early exits possible when a = 0, p = 1 (p formaly n), eg "(x+0)^203" will return "x^203" without iterating 203 pointless coefficient calculations
• And some minor repeated calculations (and now a lookup) as stored constants rather than calculated. eg k - n === i so fac(k - n) can be fac(i) and fac(n) is the same each iteration so assign that to a constant facN before the loop.
• Add the function signed that returns the partial formatted coefficient string, with arguments to deal with leading sign.
• Add function finalCoff to handle the two cases when we tack on the last coff

Output change

One change to the output as it makes no sense as it stands. When simplifying, eg "0x^2 + 2" becomes "2" however your function returns an empty string for "0x^2 + 0" becomes "". This is not what one would expect, at minimum a number is expected, thus the function will return "0" rather than ""

As you are running this in a test environment you will likely not be ablue to close over the array facSeq so I have placed it inside the function.

function expandA(str) {
    const facSeq = [0,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368000,20922789888000,355687428096000,6402373705728000,121645100408832000,2432902008176640000,51090942171709440000,1.1240007277776077e21,2.585201673888498e22,6.204484017332394e23];
    const finalCoff = n => n < 0 ? n : (n ? "+" + n : "");
    const signed = (n, pow, plus = "+") => (
            n < 0 ? 
                (pow ? (n === -1 ? "-" : n) : (!pow ? n : "-")) : 
                (n ? plus + (n > 1 ? n : "") : "")
        ) + 
        (pow > 1 ? name + "^" + pow : (pow === 1 ? name : ""));

    const mt = str.match(/\((-?\d*)([a-z])([-+]\d+)\)\^(\d+)/)
    const [ , a, name, b, p] = [,
        mt[1] ? mt[1] == '-' ? -1 : Number(mt[1]) : 1,
        mt[2], Number(mt[3]), Number(mt[4])];

    if (a === 0) { return "" + b ** p }
    if (p === 1) { return (a ? signed(a, p, "") : "") + finalCoff(b) }
    const facN = facSeq[p];
    var i = p, coffs = [signed(a ** p, p, "")];
    while (i-- > 1) {
        const pos = p - i, cof = a ** i * b ** pos * facN / (facSeq[pos] * facSeq[i]);
        cof && coffs.push(signed(cof, i));
    }
    return coffs.join("") + finalCoff(b ** p);
}

If you find that this does not work, because the polynomials you need all coffs for are in orders greater than 24. You can reinstate the fac function, modified to lookup first and calculate if needed. NOTE still returns "0" rather than ""

function expandA(str) {
    const facSeq = [0,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368000,20922789888000,355687428096000,6402373705728000,121645100408832000,2432902008176640000,51090942171709440000,1.1240007277776077e21,2.585201673888498e22,6.204484017332394e23];
    const fac = n => facSeq[n] ? facSeq[n] : (n < 2 ? 1 : n * fac(n - 1));
    const finalCoff = n => n < 0 ? n : (n ? "+" + n : "");
    const signed = (n, pow, plus = "+") => (
            n < 0 ? 
                (pow ? (n === -1 ? "-" : n) : (!pow ? n : "-")) : 
                (n ? plus + (n > 1 ? n : "") : "")
        ) + 
        (pow > 1 ? name + "^" + pow : (pow === 1 ? name : ""));

    const mt = str.match(/\((-?\d*)([a-z])([-+]\d+)\)\^(\d+)/)
    const [ , a, name, b, p] = [,
        mt[1] ? mt[1] == '-' ? -1 : Number(mt[1]) : 1,
        mt[2], Number(mt[3]), Number(mt[4])];

    if (a === 0) { return "" + b ** p }
    if (p === 1) { return (a ? signed(a, p, "") : "") + finalCoff(b) }
    const facN = fac(p);
    var i = p, coffs = [signed(a ** p, p, "")];
    while (i-- > 1) {
        const pos = p - i, cof = a ** i * b ** pos * facN / (fac(pos) * fac(i));
        cof && coffs.push(signed(cof, i));
    }
    return coffs.join("") + finalCoff(b ** p);
}

Performance

using the second version function and testing for a even distribution of (nx+n)^m where m is 1 <= m <= 300 and n is -1000 < n < 1000 there is a marginal performance benefit of 10%

If we avoid rounding errors by only passing zero for the first term "nx" n = 0 when m > 20 and only making 5% of calls in the range m > 20 the performance increases is near 40%

The first version will not handle a full range but has an even better performance and may well pass the test suit you use. (excluding the "0")

Final

I expect this will get some down votes, and please do if you feel it warranted.

If you do please do provide a comment regarding the reasoning for the benefit of the OP and others.

I am not going to enter into debate and reply to comments of such nature unless specifically asked a question (collection of words ending with ?)

Answer 5

The readability of this code suffers for multiple reasons. The biggest thing I see is multiple ternary operators in a single line. It is wise to limit the code to only one ternary operator per line. If you have to use more than one, then consider using parentheses to help anyone reading your code.

As other have already pointed out, the variable names aren't very descriptive. Also, it is wise to wrap statements in curly braces, even for a single line - that way if you ever decide to add a line to the statement block you would be less likely to forget to wrap them.

So instead of lines like this:

if (Math.abs(c) == 1 && i > 0) c = c > 0 ? '+' : '-';
else c = c > 0 ? `+${c}` : c;
if (c) result += c;

if (i > 0 && c) result += x;
if (i > 1 && c) result += `^${i}`;

Use braces:

if (Math.abs(c) == 1 && i > 0) { c = c > 0 ? '+' : '-'; }
else { c = c > 0 ? `+${c}` : c; }
if (c) {result += c; }

if (i > 0 && c) { result += x;}
if (i > 1 && c) { result += `^${i}`; }

---

If you are going to use parseInt(), it is wise to specify the radix using the second parameter - unless you are using a unique number system like hexidecimal, octal, etc. then specify 10 for decimal numbers.

Always specify this parameter to eliminate reader confusion and to guarantee predictable behavior. Different implementations produce different results when a radix is not specified, usually defaulting the value to 10.¹

a = a ? a == '-' ? -1 : parseInt(a, 10) : 1;
b = parseInt(b, 10); n = parseInt(n, 10);

---

¹_{https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/parseInt#Parameters}