Problem 426703 · hard · Level 04 Non-Linear Data Structures

Polynomials That Do Arithmetic

py-dunder · operator overloading · reflected operators · polynomials

A computer-algebra teaching tool needs polynomials with integer coefficients that behave like numbers. Write a class Poly(coeffs=()), where coeffs lists the coefficients from the constant term upwards: Poly([1, 0, 3]) is 3x^2 + 1. Trailing zeros mean nothing (Poly([2, 0, 0]) == Poly([2])), and Poly() is the zero polynomial.

  • repr(p) is Poly([...]) without trailing zeros: Poly([1, 0, 3]), Poly([]).
  • str(p) is the usual form, highest power first: "3x^3 - 3x^2 + x - 1". A coefficient of 1 or -1 is not written except in the constant term, x^1 is written x, the first term has a leading - if it is negative, the others are joined with " + " or " - ", and the zero polynomial is "0".
  • p + q, p - q, p * q, -p and p ** n (for a whole number n >= 0) work, and so do mixes with integers on either side: 2 - p, 3 * p, p + 1.
  • p == q compares the polynomials, and a constant polynomial equals that integer: Poly([5]) == 5. Equal values have equal hashes, so {Poly([5]), 5} has one element.
  • p(v) evaluates p at an integer v; if v is itself a Poly, the result is the polynomial p(v(x)).
  • p[k] is the coefficient of x^k (0 beyond the degree), p.degree is the highest power with a non-zero coefficient (-1 for the zero polynomial), and bool(p) is False only for the zero polynomial.
  • p.derivative() returns the derivative.
  • divmod(p, q), p // q and p % q divide with remainder, so that p == q * (p // q) + p % q with (p % q).degree < q.degree. The divisor's highest coefficient must be 1 or -1 (otherwise ValueError), and dividing by zero raises ZeroDivisionError.

The tests write x for Poly([0, 1]), so that they can build polynomials such as 3 * x ** 2 + 1 (define x = Poly([0, 1]) after your class to try the same). The setup's raises(fn, *args) returns the name of the exception a call raises (or None).

Examples

Input:  p, q = Poly([1, 0, 3]), Poly([-1, 1])
        str(p), str(q), str(p * q), p(2), str(p(q)), repr(p - p)
Output: ('3x^2 + 1', 'x - 1', '3x^3 - 3x^2 + x - 1', 13, '3x^2 - 6x + 4', 'Poly([])')

Input:  [str(r) for r in divmod(x ** 3 - 1, x - 1)], str(2 - x), (x + 1) ** 3 == x ** 3 + 3 * x ** 2 + 3 * x + 1
Output: (['x^2 + x + 1', '0'], '-x + 2', True)

Constraints

  • Coefficients are integers (possibly huge); degrees up to 300.
  • Every operation returns a new Poly; operands never change.

Goals

  • Implement arithmetic operators, including the reflected ones, so polynomials and integers mix freely
  • Make objects callable, and let one `__call__` both evaluate and compose
  • Keep a canonical internal form so that equality, hashing and printing agree
Starting Python…