#!/usr/bin/python
# coding: utf-8

#--------------------------------------------------------------------
# Fichero:  dividir.py
# Objetivo: Dividir polinomios
# Autor:    Pedro Reina
# Fecha:    M.15.3.2016
# Licencia: CC0 1.0 Universal
#           https://creativecommons.org/publicdomain/zero/1.0/
#--------------------------------------------------------------------

#------------------------------------------------
# Variables del programa
#------------------------------------------------

#------------------------------------------------
# Módulos necesarios
#------------------------------------------------

# Para leer la línea de órdenes
import sys

# Para usar coeficientes fraccionarios
from fractions import Fraction

#------------------------------------------------
# Funciones del programa
#------------------------------------------------

#------------------------------------------------
# Convierte una cadena en un polinomio
def Polinomio(Cadena):
    # Tomamos los datos de la cadena separados por espacios
    Lista = Cadena.split()

    # Convertimos cada dato en una fracción
    return [Fraction(n) for n in Lista]

#------------------------------------------------
# Convierte un polinomio en una cadena para mostrar
def Cadena(Polinomio):
    # Averiguamos el grado del polinomio
    GradoPolinomio = len(Polinomio) - 1

    # Preparamos la cadena que vamos a devolver
    Cadena = ''

    # Pasamos por todos los monomios
    GradoMonomio = GradoPolinomio
    for Monomio in Polinomio:
        # No tenemos en cuenta los ceros
        if Monomio:
            # Preparamos el coeficiente
            if Monomio > 0 and GradoMonomio != GradoPolinomio:
                Coeficiente = '+'
            else:
                Coeficiente = ''
            if Monomio != 1:
                if Monomio.denominator != 1 and GradoMonomio:
                    if Monomio > 0:
                        Coeficiente += '(' + str(Monomio) + ')'
                    else:
                        Coeficiente += '-(' + str(-Monomio) + ')'
                else:
                    Coeficiente += str(Monomio)
            # Preparamos la parte literal
            if GradoMonomio == 0:
                ParteLiteral = ''
            elif GradoMonomio == 1:
                ParteLiteral = 'x'
            else:
                ParteLiteral = 'x^' + str(GradoMonomio)
            # Preparamos el separador
            Separador = ' ' if GradoMonomio else ''
            # Lo juntamos todo
            Cadena += Coeficiente + ParteLiteral + Separador
        GradoMonomio -= 1

    # Caso especial: el polinomio 0
    if Cadena == '': Cadena = '0'

    # Devolvemos la representación como cadena
    return Cadena

#------------------------------------------------
# Realiza la división de dos polinomios
def Divide(Dividendo, Divisor):
    # Vemos los grados de los polinomios
    GradoDividendo = len(Dividendo) - 1
    GradoDivisor = len(Divisor) - 1

    # Comparamos los grados
    if GradoDividendo < GradoDivisor:
        # Caso trivial, no es realmente una división
        Cociente, Resto = [0], Dividendo

    else:
        # Tiene sentido usar el algoritmo de división
        Cociente = []
        DividendoParcial = Dividendo[:]
        DivisorExtendido = Divisor + [0]*(GradoDividendo-GradoDivisor)
        GradoDividendoParcial = GradoDividendo

        # Vamos dividiendo grado a grado
        while GradoDividendoParcial >= GradoDivisor:
            # Vemos a cuánto cabe
            Monomio = DividendoParcial[0] / Divisor[0]
            # Lo guardamos en el cociente
            Cociente.append(Monomio)
            # Restamos
            DividendoParcial = [D-Monomio*d for (D, d) in
                                zip(DividendoParcial, DivisorExtendido)]
            # Quitamos el monomio de mayor grado
            DividendoParcial.pop(0)
            DivisorExtendido.pop()
            GradoDividendoParcial -= 1

        # Hemos terminado la división, nos queda el resto
        Resto = DividendoParcial

    # Devolvenos los resultados
    return (Cociente, Resto)

#------------------------------------------------
# El programa
#------------------------------------------------

# Informamos al usuario
print 'División de polinomios'
print '======================'

# Vemos cuántos argumentos nos han pasado
Narg = len(sys.argv)

# Si no son exactamente tres, nos quejamos
if Narg != 3:
    print 'Uso: ' + sys.argv[0] + ' dividendo divisor'
    print 'Ejemplo: ' + sys.argv[0] + " '1 2/3 0 -5' '1 -7/5 8'"

# Si son tres, seguimos
else:
    # Tomamos los datos de la línea de órdenes
    Dividendo = sys.argv[1]
    Divisor = sys.argv[2]

    # Convertimos los datos en polinomios
    Dividendo = Polinomio(Dividendo)
    Divisor = Polinomio(Divisor)

    # Informamos de los datos recibidos
    print 'Dividendo: ' + Cadena(Dividendo)
    print 'Divisor: ' + Cadena(Divisor)

    # Hacemos la división
    Cociente, Resto = Divide(Dividendo, Divisor)

    # Informamos de los resultados calculados
    print 'Cociente: ' + Cadena(Cociente)
    print 'Resto: ' + Cadena(Resto)

# Hemos acabado; informamos al usuario
print 'Terminado.'