Codewars: Multiplying Polynomials

Question

I'm trying to solve the following Kata from Codewars in Python.

My code produces the desired result for all the tests, yet it is not optimal, so it takes too much time to accomplish the big tests.

def set_var(pol_1, pol_2):
    if any(char.isalpha() for char in pol_1):
        for char in pol_1:
            if char.isalpha():
                return char
    elif any(char.isalpha() for char in pol_2):
        for char in pol_2:
            if char.isalpha():
                return char
    # if there is only a constant term
    return 'x'

def str_to_dict(polynomial, var):
    # exclude spaces 
    pol_no_space = ''.join([char for char in polynomial if not char.isspace()])
    # replace '-' with '+-' to separate terms lates
    pol_sep = pol_no_space.replace('-', '+-')
    # split into terms using '+' as a separator
    pol_terms = pol_sep.split('+')
    pol_terms = [term for term in pol_terms if term]

    # add powers 1 and 0
    for i in range(len(pol_terms)):
        if pol_terms[i][-1].isalpha():
            pol_terms[i] += '^1'
        elif pol_terms[i].lstrip('-').isdigit():
            pol_terms[i] += var + '^0'

    # add coefficient 1 to those terms that don't have it
    for i in range(len(pol_terms)):
        # if 0th char is a variable
        if pol_terms[i].lstrip('-')[0].isalpha():
            if pol_terms[i][0] == '-':
                pol_terms[i] = pol_terms[i].replace('-', '-1')
            else:
                pol_terms[i] = '1' + pol_terms[i]
    
    sep = var + '^'
    pol_dict = {}

    for term in pol_terms:
        coeff, power = term.split(sep)
        pol_dict[int(power)] = int(coeff)
    return dict(sorted(pol_dict.items(), key=lambda item: item[0], reverse=True))

def mult_pol(p1, p2):
    res = {}
    for power1, coeff1 in p1.items():
        for power2, coeff2 in p2.items():
            power = power1 + power2
            coeff = coeff1 * coeff2
            if coeff != 0:
                if power in res:
                    if res[power] + coeff == 0:
                        del res[power]
                    else:
                        res[power] += coeff
                else:
                    res[power] = coeff
    return dict(sorted(res.items(), key=lambda item: item[0], reverse=True))


def dict_to_str(mult_res, var):
    if len(mult_res) == 0:
        return '0'
    else:
        res_str = ''
        for power in mult_res:
            if len(res_str):
                if mult_res[power] > 1:
                    res_str += '+' + str(mult_res[power])
                elif mult_res[power] == 1:
                    if power != 0:
                        res_str += '+'
                    else:
                        res_str += '+' + str(mult_res[power])
                elif mult_res[power] == -1:
                    if power != 0:
                        res_str += '-'
                    else:
                        res_str += str(mult_res[power])
                else:
                    res_str += str(mult_res[power])
            else:
                if mult_res[power] == 1 or mult_res[power] == -1:
                    if power > 0:
                        res_str += str(mult_res[power]).replace('1', '')
                    else:
                        res_str += str(mult_res[power])
                else:
                    res_str += str(mult_res[power])

            if power > 1:
                res_str += var + '^' + str(power)
            elif power == 1:
                res_str += var

    return res_str


def polynomial_product(polynomial_1: str, polynomial_2: str) -> str:
    # get the variable used in a polynomial
    var = set_var(polynomial_1, polynomial_2)

    # get dicts
    pol1_dict = str_to_dict(polynomial_1, var)
    pol2_dict = str_to_dict(polynomial_2, var)
    
    # multiply dicts
    res_dict = mult_pol(pol1_dict, pol2_dict)

    # get the string representation
    return dict_to_str(res_dict, var)

The main function here is polynomial_product(polynomial_1, polynomial_2). I want to use only built-in functions and methods (e.g. I don't want to use the module re or something like that).

Any suggestions on how to improve the code are of great help.

Answer 1

automated test suite

Including a test suite or other calls with example input would have been nice.

---

break out helper

def set_var(pol_1, pol_2):

The pair of _ underscores in the formal parameters is slightly odd, whatever.

As far as naming goes, this appears to be more of a find_var() or perhaps get_var() -- consider renaming.

If you break out a _private helper this could be a one liner:

    return _get_var(poly1) or _get_var(poly2) or "x"

(Recall that or is short circuiting, so v() or w() or "x" bails on the first disjunct that evaluates as truthy.)

---

use standard builtin methods

    # exclude spaces 
    pol_no_space = ''.join([char for char in polynomial if not char.isspace()])

Thank you for the # comment, it's helpful. But the code is tediously verbose. Most folks would express it as polynomial.replace(" ", ""), direct enough that no comment is needed. (Unless there's some CR / LF / TAB item in the requirements that I missed.)

Kudos, I feel the .replace('-', '+-') was a good call.

    pol_terms = [term for term in pol_terms if term]

I don't understand that if term filtering. It seems to suggest that 2+ or x+2+ or x++2 would be valid polynomials, which I don't agree with. Breaking out a helper would have given you an opportunity to """document""" the details. Including a test suite would offer a similar opportunity to describe details.

Maybe the affected input starts out x + -2? Which then becomes x++-2, and hilarity ensues. Perhaps a surgical regex would have been a better choice than the .replace('-', '+-') blunt instrument.

You mentioned a desire to exclusively use built-in functions (no import re), without describing why the requirements force such a straitjacket upon the implementation. You still have an opportunity to carefully avoid introducing ++- substrings, even without a regex, which would obviate the need for dealing with ++- cleanups later.

---

choose names carefully

Suppose you had gone to the trouble of adding optional type hinting:

def str_to_dict(polynomial: str, var: str) -> dict:

The identifier name is true, but it's sort of vacuous, it's obvious from the signature.

Better to say that we will regularize() the polynomial, or standardize() it, putting it in standard form. And then spell out in the """docstring""" that we deal with +/- terms, unity coefficients, and missing {x^1, x^0} factors.

This function isn't exactly too long, but it's kind of on the long side. Adopt similar naming when you break out one or more helpers.

Here's a hint: when you feel the need to write a # foo comment, the code is telling you that breaking out a def _foo(): helper might be appropriate.

---

In def multiply_polynomials, this seems tedious:

            if coeff != 0:
                if power in res:
                    if res[power] + coeff == 0:
                        del res[power]
                    else:
                        res[power] += coeff
                else:
                    res[power] = coeff

Use a defaultdict(str).

Consider postponing the zero cleanup until the end, when you're outputting a sorted dict.

---

use terminology from the business domain

Here the business domain is mathematics, a field which defines many terms.

def dict_to_str(mult_res, var):

I suppose "multiplication result" is accurate. But most people would call that a product, just as an addition result would be a sum.

    if len(mult_res) == 0:
        return '0'
    else:
        ...

Ditch the else. It will save you one level of indent for the rest of the function.

Honestly, that for loop is not at all easy to read. I confess I don't understand why we bifurcate on initial vs non-initial term. I'm sure it's right, it's just that the motivation is non-obvious. And then within each part there's lots of repetition but also significant changes.

We need comments, helpers, docstrings, testcases. Take a flame thrower to that for loop and just replace it all.

In contrast, polynomial_product() is a beautiful high-level piece of code, very direct, which builds on the useful helpers you've defined. Strive to write more code like that.

Answer 2

it takes too much time to accomplish the big tests

If all is well (I did not profile the code, but you should) then only mult_pol should be significant for big polynomials. It's the only part that should take quadratic time.

Efficient sparse polynomial multiplication is complicated. Efficient dense polynomial multiplication can be pretty easy, depending on what algorithm you use. Since the kata specifies "0 <= degree <= 4500", you can use dense polynomial multiplication. That should be worse for very sparse polynomials (eg x⁴⁵⁰⁰+1), you could handle those separately.

Dense polynomial multiplication is similar to big-integer multiplication, minus some carries. You can use the same algorithms with minor modifications (which actually make them simpler), ranging from Karatsuba to FFT-based algorithms. They're so similar in fact that you can encode the coefficients into two big-integers, multiply them, and extract the coefficients of the products from the integer product. In Python in particular this is a useful technique since it delegates the heavy lifting to an efficient built-in (though I have not tried how it actually compares), in general it can be useful if the coefficients are small.

Answer 3

First, this is good quality code. I can read it and understand what each part is accomplishing. I am going to concentrate on two improvements in your code. First, some functions are doing too much work. Second, more functions are needed.

Doing less work

Let's look at the first half of set_var().

    if any(char.isalpha() for char in pol_1):
        for char in pol_1:
            if char.isalpha():
                return char

The if any() statement searches the entire string, checking if any character is a letter. The for char in pol_1: if char.isalpha() block searches the entire string, checking if any character is a letter. We only need to do the search once, so let's get rid of the if any() check.

def set_var(pol_1, pol_2):
    for char in pol_1:
        if char.isalpha():
            return char
    for char in pol_2:
        if char.isalpha():
            return char
    # if there is only a constant term
    return 'x'

This version of set_var() will only take half the time of the original. Furthermore, since both loops are identical, we can do both loops within another loop to reduce redundancy.

def set_var(pol_1, pol_2):
    for pol in (pol_1, pol_2):
        for char in pol:
            if char.isalpha():
                return char
    # if there is only a constant term
    return 'x'

The function str_to_dict() does too much work in a different way. All of the string manipulation is constantly constructing new strings since strings in python are immutable (unchangeable after creation). Instead, let's try scanning the string and interpreting parts with another function. First, we need to locate the start and end of each term within the string.

def str_to_dict(polynomial, var):
    parsed_polynomial = {}
    term_start = 0
    for position, char in enumerate(polynomial):
        if char in "+-":
            coefficient, exponent = parse_term(polynomial[term_start : position], var)
            parsed_polynomial.setdefault(exponent, 0)
            parsed_polynomial[exponent] += coefficient
            term_start = position
    coefficient, exponent = parse_term(polynomial[term_start:], var) # get final term
    parsed_polynomial.setdefault(exponent, 0)
    parsed_polynomial[exponent] += coefficient
    return parsed_polynomial

A few things to notice:

• The polynomial string is never edited. This should save lots of time on larger polynomials.
• There's no need to treat positive or negative terms separately.
• All of the complicated parsing of the polynomial terms happens in the new function parse_term(). Using a new function here makes the structure of the surrounding code clearer, since it only does one thing: locate the substrings that represent separate terms.

The parse_term() function will be detailed in the next section.

There is a similar problem in dict_to_str(). Every statement that modifies res_str (e.g., res_str += '+') creates an entirely new string just to add one character. What we want to do is build all of the individual substrings for each term and then join them all at once.

def dict_to_str(parsed_polynomial, var):
    maximum_exponent = max(parsed_polynomial.keys())
    poly_str = ''.join(term_string(parsed_polynomial.get(exponent, 0), var, exponent) for exponent in range(maximum_exponent, -1, -1))
    return poly_str.lstrip("+") or '0' # or '0' handles all coefficients == 0

The term_string() function takes a coefficient, a variable, and an exponent in order to create a string version of the term (the inverse of parse_term()). This will be detailed in the next section. More importantly, there is no sorting of the polynomial terms because we just count down from the largest exponent with range().

Finally, there's mult_poly(). Two parts of this function are doing too much work.

            if coeff != 0:
                if power in res:
                    if res[power] + coeff == 0:
                        del res[power]
                    else:
                        res[power] += coeff
                else:
                    res[power] = coeff

Checking if the resulting coefficient is zero and deleting the entry is wasted effort. We can just skip null coefficients when writing out the string. Also, the setdefault() method on dicts negates the need to check for an existing entry.

                res.setdefault(power, 0)
                res[power] += coeff

We are also sorting the exponents when writing the string, so return res is sufficient.

def mult_pol(p1, p2):
    res = {}
    for power1, coeff1 in p1.items():
        for power2, coeff2 in p2.items():
            power = power1 + power2
            coeff = coeff1 * coeff2
            res.setdefault(power, 0)
            res[power] += coeff
    return res

New functions

In the previous section, we assumed we had a function named parse_term(term, var) that could return the coefficient and exponent. Let's figure out that function. First, we know the term can have one of a few forms:

1. "{number}{variable}^{number}"
2. "{variable}^{number}"
3. "-{variable}^{number}"
4. "{number}{variable}"
5. "{number}"
6. "{variable}"
7. "-{variable}"
8. ... perhaps others I'm forgetting

Anyway, one way we can put the var argument to use is to split the term and examine what we get.

def parse_term(term, var):
    parts = term.replace(" ", "").split(var) # spaces matter for parsing, so delete them
    if len(parts) == 1: # var is not in term, must be bare number
        return int(parts[0] or '0'), 0 # or 0 handles empty string terms

    coefficient_part, exponent_part = parts

    if not coefficient_part or coefficient_part == "+": # term = "+x^n"
        coefficient = 1
    elif coefficient_part == "-": # term = "-x^n"
        coefficient = -1
    else:
        coefficient = int(coefficient_part)

    if not exponent_part: # term is Ax
        exponent = 1
    else: # term is Ax^n
        exponent = int(exponent_part[1:]) # skip "^"

    return coefficient, exponent

Now we need the term_string() function, the inverse of the previous function. Since there are special cases for both the coefficient and the variable and exponent, let's write function for each of those and combine them. It's easier to think about smaller pieces.

def term_string(coefficient, var, exponent):
    if coefficient == 0:
        return ""
    return coeff_str(coefficient, exponent) + var_str(var, exponent)

def coeff_str(coefficient, exponent):
    if coefficient == 1 and exponent > 0:
        return "+"
    if coefficient == -1 and exponent > 0:
        return "-"
    return ("+" if coefficient >= 0 else "") + str(coefficient)

def var_str(var, exponent):
    if exponent == 0:
        return ""
    if exponent == 1:
        return var
    return f"{var}^{exponent}"

Speed

This code gets just under the time limit of 12 seconds.

The power of libraries

I know you said that you only wanted to use builtin functions, but I think it's useful to show how searching for existing libraries can sometimes be a better use of labor than optimizing code. Just to show how powerful library algorithms can be, here's a version of mult_pol() that completes the tests in under 2 seconds.

def mult_pol(p1, p2):
    # Convert both polynomials to arrays of coefficients in increasing exponent order
    p1c = np.array([p1.get(n, 0) for n in range(1 + max(p1.keys()))])
    p2c = np.array([p2.get(n, 0) for n in range(1 + max(p2.keys()))])
    
    pc = np.convolve(p1c, p2c)
    return dict(zip(range(len(pc)), pc))

The NumPy function np.convolve() implements the convolution operation on two arrays of numbers, which just happens to be equivalent to polynomial multiplication when those arrays are polynomial coefficients in increasing power order.