main.py

from typing import List, Tuple

class Polynomial:
    def __init__(self, neg: List[float], pos: List[float]):
        """
        Initialize the polynomial.
        - neg: Coefficients for negative exponents, ordered from x^{-1}, x^{-2}, ...
        - pos: Coefficients for non-negative exponents, ordered from x^{0}, x^{1}, ...
        """
        self.neg = neg.copy()  # e.g., [a1, a2, ...] for a1*x^{-1} + a2*x^{-2} + ...
        self.pos = pos.copy()  # e.g., [b0, b1, ...] for b0*x^{0} + b1*x^{1} + ...

    def contract(self) -> Tuple['Polynomial', int]:
        """
        Contract the polynomial by removing the first negative coefficient
        and shifting the remaining coefficients.

        Returns:
            A tuple containing the new Polynomial and the number of shifts performed.
        """
        n = len(self.neg)
        if n > 1:
            # Remove the first coefficient and reverse the remaining
            shifted_neg = self.neg[1:].copy()
            shifted_neg.reverse()
            # Append positive coefficients
            new_pos = shifted_neg + self.pos.copy()
            shift = n - 1
        else:
            # If there's only one or no negative coefficients
            new_pos = self.pos.copy()
            shift = 0
        # Reset negative coefficients to [0]
        new_neg = [0]
        # Create the new polynomial
        new_poly = Polynomial(new_neg, new_pos)
        return new_poly, shift

    def __str__(self):
        """
        String representation of the polynomial.
        """
        terms = []
        # Add negative exponent terms
        for i, coeff in enumerate(self.neg):
            if coeff != 0:
                terms.append(f"{coeff}x^-{i+1}")
        # Add non-negative exponent terms
        for i, coeff in enumerate(self.pos):
            if coeff != 0:
                if i == 0:
                    terms.append(f"{coeff}")
                else:
                    terms.append(f"{coeff}x^{i}")
        return " + ".join(terms) if terms else "0"

# Example 1
print("=== Example 1 ===")
# Polynomial P(x) = 3x^{-1} + 1x^{-2} + 4x^{0} + 5x^{1}
P = Polynomial(neg=[3, 1], pos=[4, 5])
print(f"Original P(x): {P}")

# Contract the polynomial
P_contracted, shift = P.contract()
print(f"Contracted P'(x): {P_contracted}, Shift: {shift}")

# Example 2
print("\n=== Example 2 ===")
# Polynomial Q(x) = 2x^{-3} + 1x^{-2} + 3x^{-1} + 4x^{0} + 5x^{1} + 6x^{2}
Q = Polynomial(neg=[3, 1, 2], pos=[4, 5, 6])
print(f"Original Q(x): {Q}")

# Contract the polynomial
Q_contracted, shift_q = Q.contract()
print(f"Contracted Q'(x): {Q_contracted}, Shift: {shift_q}")