8
\$\begingroup\$

I solved the following problem:

Write a function expand that takes in an expresion with a single, one character variable, and expands it. The expresion 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 coeficient 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 coeficient of a term is zero, the term should not be included. If the coeficient of a term is one, the coeficient should not be included. If the coeficient of a term is -1, only the "-" should be included. If the power of the term is 0, only the coeficient should be included. If the power of the term is 1, the carrot 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 can it 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 conceed 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 dont know enough math.

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

I dont 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.

\$\endgroup\$
  • 6
    \$\begingroup\$ What's with all the single-letter variables? Did you obfuscate this on purpose or do you always write like this? Genuinely concerned. \$\endgroup\$ – Mast Aug 26 at 5:47
  • \$\begingroup\$ Did you create the expanded form or was that also part of the challenge? \$\endgroup\$ – dfhwze Aug 26 at 6:05
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ How would I use (n - k) / (k + 1) * b / a to calculate de binomial coefficient? Can you elaborate on this please? How would it work for (r+0)^203? For k = 0 it would be (203 - 0) / (0 + 1) * 0 / 1 = 0. Thanks for your help. \$\endgroup\$ – haxor Aug 27 at 12:36
  • \$\begingroup\$ Did you read the Wikipedia article? \$\endgroup\$ – Roland Illig Aug 27 at 17:39
  • \$\begingroup\$ Im going through the Wikipedia page for Binomial Coefficient. It has several code samples that are far more efficient than the factorial formula. I will put that to use. Thank you for your help. \$\endgroup\$ – haxor Aug 28 at 2:33
7
\$\begingroup\$

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.

\$\endgroup\$
  • 3
    \$\begingroup\$ Most of the single-letter names come directly from the task, so there's nothing from with them. \$\endgroup\$ – Roland Illig Aug 25 at 22:24
  • 2
    \$\begingroup\$ @RolandIllig If you included comments describing the task there, they would be good. If you don't, it doesn't matter if the task used them (to me), they still suck as names. \$\endgroup\$ – Yakk Aug 26 at 14:46
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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 ?)

\$\endgroup\$
  • \$\begingroup\$ The naming critique is nit picking and not worthy of a mention as the abstract is not in the realm of natural language. I do believe even in math terms, critique on naming is warranted here. Naievely incrementing variable names in alphabetical order hurts readability. At some point we encounter f, which I would assume stands for function. I would have loved to see pairs of a multiplier and power (a, pa), (b, pb) and so on, rather than (a,b), (c,d). \$\endgroup\$ – dfhwze Aug 27 at 20:46
  • \$\begingroup\$ There are various things I like about your review. Mainly the focus on performance. My function passed the tests because of 4. You are never passed a polynomial above the precision range of a double that can not be optimized. The test suite does not check for high powers. But I knew my code was'nt good enough, that's why I posted here. The choise of the formula that uses factorial was the worse pick. Im reading about options to replace it. I will test your code and will use some of your proposed changes. Thanks a lot for taking the time to review my code. \$\endgroup\$ – haxor Aug 28 at 2:27
0
\$\begingroup\$

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.1

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

1https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/parseInt#Parameters

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.