# Task

Given an array of roots of a polynomial equation, you should reconstruct this equation.

___

## Output details:

* If the power equals `1`, omit it: `x = 0` instead of `x^1 = 0`
* If the power equals `0`, omit the `x`: `x - 2 = 0` instead of `x - 2x^0 = 0`
* There should be no 2 signs in a row: `x - 1 = 0` instead of `x + -1 = 0`
* If the coefficient equals `0`, skip it: `x^2 - 1 = 0` instead of `x^2 + 0x - 1 = 0`
* Repeating roots should not be filtered out: `x^2 - 4x + 4 = 0` instead of `x - 2 = 0`
* The coefficient before `q^n` is always `1`: `x^n + ... = 0` instead of `Ax^n + ... = 0`

___

## Example:

```
polynomialize([0])        =>  "x = 0"
polynomialize([1])        =>  "x - 1 = 0"
polynomialize([1, -1])    =>  "x^2 - 1 = 0"
polynomialize([0, 2, 3])  =>  "x^3 - 5x^2 + 6x = 0"
```

___

## Tests:

```python
      Main suite:                  Edge cases:
 (Reference - 4000 ms)         (Reference - 30 ms)

N of roots | N of tests      N of roots | N of tests
-----------------------      -----------------------
    1-10   |   100              20-40   |    125
 700-750   |    25               2-20   |    125
```

Difficulty: introductory

Starter code:

def polynomialize(roots):
	

Solutions:
import re

def polynomialize(roots):
    
    def deploy(roots):
        r = -roots[0]
        if len(roots) == 1: return [r, 1]
        
        sub = deploy(roots[1:]) + [0]
        return [c*r + sub[i-1] for i,c in enumerate(sub)]
    
    coefs = deploy(roots)
    poly  = ' + '.join(["{}x^{}".format(c,i) for i,c in enumerate(coefs) if c][::-1])
    poly  = re.sub(r'x\^0|\^1\b|\b1(?=x)(?!x\^0)', '', poly).replace("+ -", "- ") + ' = 0'
    return poly

def poly(lst):
    ans = [1, -lst.pop()]
    while lst:
        ans.append(0)
        r = lst.pop()
        for i in range(len(ans)-1, 0, -1):
            ans[i] -= r*ans[i-1]
    return ans            

import re
def polynomialize(roots):
    if len(roots) == 1:
        if roots[0] == 0:
            return 'x = 0'
        elif roots[0] < 0:
            return 'x + ' + str(abs(roots[0])) + ' = 0'
        else:
            return 'x - ' + str(roots[0]) + ' = 0'
    if len([i for i in roots if i != 0]) == 0:
        return 'x^' + str(len(roots)) + ' = 0'
    
#    ans =  np.poly(roots)
    ans = poly(roots)
    ans1 = ans[:]
    
    final = []
    for i in range(len(ans[:-1])):
        try:
            if int(ans[i]) == 0:
                continue
        except:
            continue
        if int(ans[i]) == 1:
            num = len(ans1[:-1])-i
            if num == 1:
                final.append('x')
            else:
                final.append('x^{}'.format(str(num)))
        else:
            num = len(ans1[:-1])-i
            if num == 1:
                final.append(str(int(ans[i])) + 'x')
            else:
                final.append(str(int(ans[i])) + 'x^{}'.format(str(num)))
    if int(ans[-1]) != 0:
        final.append(str(int(ans[-1])))
    if isinstance(final[0], list):
        final = final[-1]
    answer = '+'.join(final)

    answer = answer.replace('+-', ' - ')
    answer = answer.replace('+', ' + ')
    answer = re.sub(" 1x", ' x', answer)
    return answer + ' = 0'

def polynomialize(roots):
    coeffs = [1]
    for root in roots:
        coeffs = [1] + [coeffs[i] + coeffs[i-1] * -root for i in range(1,len(coeffs))] + [-root * coeffs[-1]] 
    coeffs = [d for d in list(enumerate(coeffs[::-1]))[::-1] if d[1] != 0]
    r = ['{:+0d}x^{}'.format(d[1], d[0]) for d in coeffs if d[0]>1]
    r += ['{:+0d}x'.format(d[1]) for d in coeffs if d[0]==1]
    r += ['{:+0d}'.format(d[1]) for d in coeffs if d[0]==0]
    f = ' '.join(r).replace('+1x', '+x').replace('-1x', '-x').replace('-', '- ').replace('+', '+ ').lstrip('+').strip(' ')
    return f + ' = 0'

import numpy as np

string = lambda v: "" if not v else "x" if v == 1 else f"x^{v}"

def coefficients(roots):
    coeffs = [1, -roots.pop()]
    while roots:
        coeffs.append(0)
        r = roots.pop()
        for i in reversed(range(1, len(coeffs))):
            coeffs[i] -= r * coeffs[i-1]
    return coeffs

# numpy.poly1d gives slighty different coeffs
def polynomialize(roots):
    #coeffs = list(map(int, np.poly1d(roots, True)))
    coeffs = coefficients(roots)
    z = zip(reversed(range(len(coeffs))), coeffs)
    res = [string(next(z)[0])]
    res.extend(f" {'-+'[b > 0]} {(abs(b), '')[a and abs(b) == 1]}{string(a)}" for a,b in z if b)
    res.append(" = 0")
    return ''.join(res)

def polynomialize(roots):
    space_sign_space = lambda c: ' + ' if 0 < c else ' - '
    space_sign_space_num = lambda c: space_sign_space(c)  + (str(abs(c)) if abs(c) != 1 else '')
    max_power = len(roots)
    # Calculate coefficients
    coefs = [1, -roots[0]]
    if max_power > 1:
        for r in roots[1:]:
            coefs = [1,] + [c[0]-r*c[1] for c in zip(coefs[1:], coefs[:-1])] + [-r*coefs[-1],]
    # Construct equation (first line, separately as it needs no leading +)
    eq = 'x' + ('^' + str(max_power) if max_power > 1 else '')
    power = max_power
    # Loop for x^(max_power -1) up to x^2 if it exists
    for c in coefs[1:-2]:
        power -= 1
        if c == 0:
            continue
        eq += space_sign_space_num(c)
        eq += 'x^' + str(power)
    # Coefficient for x
    if (max_power > 1) and coefs[-2] != 0:
        eq += space_sign_space_num(coefs[-2])
        eq += 'x'
    # Coefficient for const
    if coefs[-1] != 0:
        eq += space_sign_space(coefs[-1]) + str(abs(coefs[-1]))
    eq += ' = 0'
    return eq

def polynomialize(roots):
    def add_root(poly, root):
        # Multiply poly * (x - root)
        poly1 = poly + [0] # Increase order (multiply by x)
        poly2 = [0] + [-root * coef for coef in poly] # Multiply by -root
        poly = [coef1 + coef2 for coef1, coef2 in zip(poly1, poly2)] # Add
        return poly
    def poly2str(poly):
        spoly = ""
        for i, coef in enumerate(poly):
            if i == 0:
                signum = ""
            elif coef > 0:
                signum = " + "
            elif coef < 0:
                signum = " - "
            else:
                continue
                
            if abs(coef) == 1:
                scoef = ""
            else:
                scoef = str(abs(coef))
            
            exp = len(poly)-i-1
            if exp == 1:
                sexp = "x"
            elif exp == 0:
                if scoef == "":
                    sexp = "1"
                else:
                    sexp = ""
            else:
                sexp = "x^"+str(exp)
            spoly += signum + scoef + sexp
        spoly += " = 0"
        return spoly
    
    poly = [1, -roots[0]]
    for root in roots[1:]:
        poly = add_root(poly, root)
        
    return poly2str(poly)
        
    
        


from functools import reduce

def toTerm(coef, power):
    if not coef or coef == 0: return ''
    if power == 0: 
        p = ''
    elif power == 1:
        p = 'x'
    else:
        p = 'x^' + str(power)
    
    term = ('' if abs(coef) == 1 and power > 0 else str(abs(coef))) + p
    return (' - ' if coef < 0 else ' + ') + str(term) if term else ''

def co2poly(coefs):
    terms = [toTerm(c, i) for i, c in enumerate(coefs)]
    terms.reverse()
    t = ''.join(terms)
    return (t[3:] if t.startswith(' +') else t[1:]) + ' = 0'

def toCoefs(coefs, root):
    return [ n * -root + c for (c, n) in zip([0] + coefs, coefs + [0]) ]

def polynomialize(roots):
    coefs = reduce(toCoefs, roots, [1])
    return co2poly(coefs)


def monomial(factor, index):
    if factor < 0:
        if factor == -1:
            if not index:
                return " - 1"
            return " - x" if index == 1 else " - x^{}".format(index)
        else:
            if not index:
                return " - {}".format(abs(factor))
            return " - {}x".format(abs(factor)) if index == 1 else " - {}x^{}".format(abs(factor), index)
    else:
        if factor == 1:
            if not index:
                return " + 1"
            return " + x" if index == 1 else " + x^{}".format(index)
        else:
            if not index:
                return " + {}".format(factor)
            return " + {}x".format(factor) if index == 1 else " + {}x^{}".format(factor, index)

def polynomialize(roots):
    length, roots, parameters = len(roots), filter(lambda i : i, roots), [1]
    for root in roots:
        parameters = [1] + [parameters[i+1] - root*parameters[i] for i in range(len(parameters)-1)] + [-parameters[-1]*root]
    return "".join([monomial(param, length-i) for i, param in enumerate(parameters) if param])[3:] + " = 0"

def monomial(factor, index):
    if factor < 0:
        if factor == -1:
            if not index:
                return " - 1"
            return " - x" if index == 1 else " - x^{}".format(index)
        else:
            if not index:
                return " - {}".format(abs(factor))
            return " - {}x".format(abs(factor)) if index == 1 else " - {}x^{}".format(abs(factor), index)
    else:
        if factor == 1:
            if not index:
                return " + 1"
            return " + x" if index == 1 else " + x^{}".format(index)
        else:
            if not index:
                return " + {}".format(factor)
            return " + {}x".format(factor) if index == 1 else " + {}x^{}".format(factor, index)


def polynomialize(roots):
    zeros, roots2, length = roots.count(0), [r for r in roots if r], len(roots)
    parameters = [1]
    for root in roots2:
        parameters = [1] + [parameters[i+1] - root*parameters[i] for i in range(len(parameters)-1)] + [-parameters[-1]*root]
    return "".join([monomial(param, length-i) for i, param in enumerate(parameters) if param])[3:] + " = 0"

def polynomialize(roots):
    poly = [1]
    for root in roots:
        new_poly = [1]
        for i in range(1, len(poly)):
            new_poly.append(poly[i] - root * poly[i - 1])
        new_poly.append(poly[-1] * -root)
        poly = new_poly
    
    str_poly = []
    for i, coeff in enumerate(poly):
        power = len(roots) - i
        if coeff < 0:
            str_poly.append(' - ')
        elif coeff > 0:
            if i:
                str_poly.append(' + ')
        else:
            continue
        coeff = abs(coeff)
        if power == 0 or coeff != 1:
            str_poly.append(str(coeff))
        if power != 0:
            str_poly.append('x')
        if power >= 2:
            str_poly.append('^')
            str_poly.append(str(power))
    return f'{"".join(str_poly)} = 0'