import random


def powerList(theList):
    sublistList=[[]]
    for element in theList:
        newSublistList=[]
        for sublistElement in sublistList:
            newSublistList.append(sublistElement)
            newSublistList.append(sublistElement+[element])
        sublistList=newSublistList
    return sublistList

def lenNLists(listList,N):
    outLists=[]
    for eachList in listList:
        if len(eachList)==N:
            outLists.append(eachList)
    return outLists

def polyfieldAdd(polynomial1,polynomial2,add=lambda x,y:x+y):
    """Takes 2 polynomial lists and adds them"""
    return map(add,polynomial1,polynomial2)
#No. this is dumb. This is just map but with the argument order changed, and the default function being +.
#or not...?
fst = lambda x:x[0]

def polyWithZeroes(zeroesList,add=lambda x,y:x+y,prod=lambda x,y:x*y,neg=lambda x:-x,add0=0.,prod1=1.):
    numZeroes=len(zeroesList)
    outPoly=[add0 for __ in zeroesList]+[add0]
    zeroesPowerlist=powerList(zeroesList)
    for j in range(numZeroes+1):
        for l in lenNLists(zeroesPowerlist,j):
            negXs=map(neg,l)
            outPoly[j]=add(outPoly[j],reduce(prod,negXs,prod1))
    return outPoly

def evalPoly(inputX,polyList,add=lambda x,y:x+y,prod=lambda x,y:x*y,add0=0.,prod1=1.):
    """Evaluates the polynomial represented by polyList with the input inputX,
        uses optional arguments add,prod,add0,prod1 for addition, multiplication, etc, if specified.
        Non associative operations might give unwanted results."""
    outNum=add0
    mulBy=prod1
    for coeffcnt in polyList[::-1]:
        evaldTerm=prod(mulBy,coeffcnt)
        outNum=add(outNum,evaldTerm)
        mulBy=prod(mulBy,inputX)
    return outNum

def createLookup(pointList,add=lambda x,y:x+y,prod=lambda x,y:x*y,neg=lambda x:-x,inv=lambda x:(1/x),prod1=1.,add0=0.):
    partialPolys=[]
    partialZeroesPolys=[]
    outPoly=[add0 for __ in (pointList)]
    for i in range(len(pointList)):
        pointListPartialCopy=pointList[:i]+pointList[i+1:]
        xParts=map(lambda point:point[0],pointListPartialCopy)#this is the list of the zeroes for this partial polynomial
        currentPartialZeroesPoly=polyWithZeroes(xParts,add,prod,neg,add0,prod1)
        partialZeroesPolys.append(currentPartialZeroesPoly)
        polyAtX=evalPoly(pointList[i][0],currentPartialZeroesPoly,add,prod,add0,prod1)
        desiredYAtX=pointList[i][1]
        scalePartialZeroesPolyBy=prod(desiredYAtX,inv(polyAtX))
        currentPartialPoly=[prod(scalePartialZeroesPolyBy,partialZeroesCoeffcnt) for partialZeroesCoeffcnt in currentPartialZeroesPoly]
        partialPolys.append(currentPartialPoly)
        outPoly=polyfieldAdd(outPoly,currentPartialPoly,add)
    return outPoly

def createLookup0(pointList,add=lambda x,y:x+y,prod=lambda x,y:x*y,neg=lambda x:-x,inv=lambda x:(1/x),prod1=1.,add0=0.):
    """Creates a lookup function/object/thing
    First argument (pointList) should be a list or tuple of x y pairs.
    The result should be a list of the coefeccients of a polynomial that goes through all the points.
    This function also works for other fields (possibly only abelian fields?). (all fields are abelian))
    To use this function with other feilds, pass a function for the addition function, product function, negation function, and inverse function.
    """
    polynomialList=[0 for i in pointList]
    partialPolynomialListList=[[0 for j in pointList] for i in pointList]
    for i in range(len(pointList)):
        pointListPartialCopy=pointList[:i]+pointList[i+1:]
        partialPolynomialPowerlist=powerList(pointListPartialCopy)
        for j in range(len(pointList)):
            partialPolynomialListList[i][j]=reduce(add,[reduce(prod,map(neg,map((lambda x:x[0]),l)),prod1) for l in lenNLists(partialPolynomialPowerlist,j)],add0)
        #NOTE: you have to make it multiply/add the x values of the points, not the entire points! change that!
        #ok did that.
        yi=pointList[i][1]#this, divided by the next thing has to be multiplied by each thing in partialPolynomialListList to get the actual value of it
        denom=reduce(prod,[add(pointList[i][0],neg(x[0])) for x in pointListPartialCopy],1)
        multiplyEachPartialTermByThis=prod(yi,inv(denom))
        partialPolynomialListList[i]=[multiplyEachPartialTermByThis*x for x in partialPolynomialListList[i]]
    print partialPolynomialListList
    for j in range(len(pointList)):
        pass
    return [sum([partialPolynomialListList[i][j]for i in range(len(pointList))]) for j in range(len(pointList))]

        
def fieldEvalPolynomial(x,polynomialList,prod=lambda x,y:x*y,):
    pass


charAlphabet=" abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890."#this is a default, but you can change the numbersystem by replacing this with a different string
#it must have at lest 2 chars.
def strPairFractionAdd(strPair1,strPair2):#pair because fractions. But how do we include sign? maybe use triplets instead. Yes, seems good.
    pass

def signedStrAdd(signedStr1,signedStr2,charAlphabet=charAlphabet):
    """Adds two pairs of 1 or -1 and a string, treating them together as a signed integer"""
    i=0
    alphabetLength=len(charAlphabet)
    sign1=signedStr1[0]
    sign2=signedStr2[0]
    sameSign=sign1*sign2
    str1=signedStr1[1]
    str1=rstripZeros(str1,charAlphabet)
    str2=signedStr2[1]
    str2=rstripZeros(str2,charAlphabet)
    lenStr1=len(str1)
    lenStr2=len(str2)
    outStr=""
    outSign=1
    carry=False
    if(sameSign==-1):
        if(str1==str2):
            return (1,"")
        elif(signedStrCompMagnitude(signedStr1,signedStr2,charAlphabet)):
            if(sign2==-1):
                outSign=-1
                sign1,sign2=sign2,sign1
        else:
            if(sign1==-1):
                outSign=-1
                sign1,sign2=sign2,sign1
    elif(sign1==-1):
        outSign=-1
    while(True):
        try:
            digit1Char=str1[i]
            digit1Index=charAlphabet.index(digit1Char)
        except:
            digit1Index=0
        try:
            digit2Char=str2[i]
            digit2Index=charAlphabet.index(digit2Char)
        except:
            digit2Index=0
        newDigitIndex=sign1*digit1Index + sign2*digit2Index
        if(sameSign==1):
            newDigitIndex=abs(newDigitIndex)
        if(carry):newDigitIndex=newDigitIndex+sameSign
        if((newDigitIndex>=alphabetLength)or (newDigitIndex<0)):
            carry=True
        else:
            carry=False
        newDigitChar=charAlphabet[newDigitIndex%alphabetLength]
        outStr=outStr+newDigitChar
        i+=1
        if((i>=lenStr1) and (i>=lenStr2) and (not carry) ):
            break
    return (outSign,outStr)


def signedStrCompMagnitude(signedStr1,signedStr2,charAlphabet=charAlphabet):
    """returns True of the second string is greater, and False if the first string is greater, or if the two are equal."""
    #print "signedStr2 is:"
    #print signedStr2
    #print "end of signedStr2"
    i=0
    sign1=signedStr1[0]
    sign2=signedStr2[0]
    str1=signedStr1[1]
    str1=rstripZeros(str1,charAlphabet)
    str2=signedStr2[1]
    str2=rstripZeros(str2,charAlphabet)
    #print "str1 is\""+str1+"\"."
    #print "str2 is\""+str2+"\"."
    lenStr1=len(str1)
    lenStr2=len(str2)
    if(lenStr1>1 and str1[-1]==charAlphabet[0]):
        #raise NameError("str1 ended in zerochar, and was not zerochar")
        str1=str1.rstrip(charAlphabet[0])
    if(lenStr2>1 and str2[-1]==charAlphabet[0]):
        #raise NameError("str2 ended in zerochar, and was not zerochar")
        str2=str2.rstrip(charAlphabet[0])
    if(lenStr1>lenStr2):
        return False
    if(lenStr2>lenStr1):
        return True
    for i in range(lenStr1)[::-1]:
        if(charAlphabet.index(str1[i])>charAlphabet.index(str2[i])):
            return False
        if(charAlphabet.index(str2[i])>charAlphabet.index(str1[i])):
            return True
    
    return False

def signedStrMul(signedStr1,signedStr2,charAlphabet=charAlphabet):
    alphabetLength=len(charAlphabet)
    sign1=signedStr1[0]
    sign2=signedStr2[0]
    outSign=sign1*sign2
    str1=signedStr1[1]
    str2=signedStr2[1]
    lenStr1=len(str1)
    lenStr2=len(str2)
    listStrsToSum=[]
    zeroChar=charAlphabet[0]
    prefix=""
    #NOTE: optional possibly buggy speedup code starts here, comment it out if bugs.
    #if(lenStr2>lenStr1):
    #    (str1,str2)=(str2,str1)
    #    (lenStr1,lenStr2)=(lenStr2,lenStr1)
    #NOTE: questionable code "ends" here.
    for digit1Char in str1:
        try:
            digit1Index=charAlphabet.index(digit1Char)
        except:
            digit1Index=0
            print "warning, the digit1 was not found in charAlphabet."
        strToSum=prefix
        carry=0
        for digit2Char in (str2+zeroChar):
            try:
                digit2Index=charAlphabet.index(digit2Char)
            except:
                digit2Index=0
                print "warning, the digit2 was not found in charAlphabet."
                
            digitToAddIndex=digit1Index*digit2Index+carry
            digitToAddChar=charAlphabet[digitToAddIndex%alphabetLength]
            carry=digitToAddIndex/alphabetLength
            strToSum=strToSum+digitToAddChar
        listStrsToSum+=[(1,strToSum)]
        #print strToSum
        prefix+=zeroChar
    #print "listStrsToSum has the value:"
    #print listStrsToSum
    #print "."
    outStr=reduce(signedStrAdd,listStrsToSum,(1,""))[1] #map(lambda x:(1,x),listStrsToSum)
    if((len(outStr)>1) and (outStr[-1]==zeroChar)):
        outStr=outStr[:-1]
    return (outSign,outStr)

def strDiv(strNumerator,strDenominator,charAlphabet=charAlphabet):
    """returns (strQuotient,strRemainder) given strNumerator and strDenuminator, in the base system based on charAlphabet"""
    global strQuotient
    global strRemainder
    global quotDigitIndex
    #print "charAlphabet is \""+charAlphabet+"\"."
    strQuotient=""
    strRemainder=""
    for numeChar in strNumerator[::-1]:
        strRemainder=numeChar+strRemainder
        #print "strRemainder is : \""+strRemainder+"\"."
        quotDigitIndex=0
        while(not signedStrCompMagnitude((1,strRemainder),(1,strDenominator),charAlphabet)):
            quotDigitIndex+=1
            #print "in while string remainder:"
            #print strRemainder
            strRemainder=signedStrAdd((1,strRemainder),(-1,strDenominator),charAlphabet)[1]
            #print strRemainder
        quotDigitChar=charAlphabet[quotDigitIndex]
        strQuotient=quotDigitChar+strQuotient
    strQuotient=rstripZeros(strQuotient,charAlphabet)
    strRemainder=rstripZeros(strRemainder,charAlphabet)
    return (strQuotient,strRemainder)
def rstripZeros(strIn,charAlphabet=charAlphabet):
    """removes trailing zeroChars provided the string is longer than one char"""
    if(len(strIn)>1):
        return strIn.rstrip(charAlphabet[0])
    else:
        return strIn
def strGCD(str1,str2,charAlphabet=charAlphabet):
    """Finds the greatest common divisor of the two strings in the base based on charAlphabet (little endian). Ints are Unsigned. Uses the Eucidlean Algorithm"""
    if(strIsZero(str2)):
        return str1
    if(strIsZero(str1)):
        return str2
    if(signedStrCompMagnitude((1,str1),(1,str2),charAlphabet)):
        str1,str2=str2,str1
    while(not strIsZero(str1)):
        str1,str2=((strDiv(str2,str1,charAlphabet)[1]),str1)
    return str2

def strIsZero(str1,charAlphabet=charAlphabet):
    if(len(str1)==0):
        return True
    if(str1==charAlphabet[0]):
        return True
    return False

def strFracIsZero(frac1,charAlphabet=charAlphabet):
    sign1,strNume,strDenom=frac1
    if((strNume in ["",charAlphabet[0]]) and not strIsZero(strDenom,charAlphabet)):
        return True
    return False

        

def strFracSimplify(frac,charAlphabet=charAlphabet):
    """Simplifies a string fraction of from (sign,StrNumerato,strDenominator)"""
    (sign1,strNumerator,strDenominator)=frac
    commonFactor=strGCD(strNumerator,strDenominator,charAlphabet)
    strNumerator=strDiv(strNumerator,commonFactor,charAlphabet)[0]
    strDenominator=strDiv(strDenominator,commonFactor,charAlphabet)[0]
    return (sign1,strNumerator,strDenominator)

def strFracMul(strFrac1,strFrac2,charAlphabet=charAlphabet):
    """muls two str fractions and simplifies."""
    (sign1,strNumerator1,strDenominator1)=strFrac1
    (sign2,strNumerator2,strDenominator2)=strFrac2
    signOut,strNumeratorOut=signedStrMul((sign1,strNumerator1),(sign2,strNumerator2),charAlphabet)
    strDenominatorOut=signedStrMul((1,strDenominator1),(1,strDenominator2),charAlphabet)[1]
    strFracOut=(signOut,strNumeratorOut,strDenominatorOut)
    strFracOut=strFracSimplify(strFracOut,charAlphabet)
    return strFracOut

def strFracAdd(strFrac1,strFrac2,charAlphabet=charAlphabet):
    if(strFracIsZero(strFrac1,charAlphabet)):
        return strFracSimplify(strFrac2,charAlphabet)
    elif(strFracIsZero(strFrac2,charAlphabet)):
        return strFracSimplify(strFrac1,charAlphabet)
    (sign1,strNumerator1,strDenominator1)=strFrac1
    (sign2,strNumerator2,strDenominator2)=strFrac2
    strDenominatorOut=signedStrMul((1,strDenominator1),(1,strDenominator2),charAlphabet)[1]
    strDenomGCD=strGCD(strDenominator1,strDenominator2,charAlphabet)
    strDenominatorOut=strDiv(strDenominatorOut,strDenomGCD,charAlphabet)[0]
    strA=strDiv(strDenominator2,strDenomGCD,charAlphabet)[0]
    strB=strDiv(strDenominator1,strDenomGCD,charAlphabet)[0]
    newStrNumerator1=signedStrMul((sign1,strNumerator1),(1,strA),charAlphabet)
    newStrNumerator2=signedStrMul((sign2,strNumerator2),(1,strB),charAlphabet)
    signOut,strNumeratorOut=signedStrAdd(newStrNumerator1,newStrNumerator2,charAlphabet)
    fracOut=(signOut,strNumeratorOut,strDenominatorOut)
    return strFracSimplify(fracOut,charAlphabet)

def strFracNeg(strFrac1,charAlphabet=charAlphabet):
    """returns negative strFrac1"""
    (sign1,strNumerator1,strDenominator1)=strFrac1
    return (-sign1,strNumerator1,strDenominator1)

def strFracInv(strFrac1,charAlphabet=charAlphabet):
    """returns inverted strFrac1"""
    (sign1,strNumerator1,strDenominator1)=strFrac1
    return (sign1,strDenominator1,strNumerator1)

#createLookup(pointList,add=lambda x,y:x+y,prod=lambda x,y:x*y,neg=lambda x:-x,inv=lambda x:(1/x),prod1=1.,add0=1.)

def randStr(length,charAlphabet=charAlphabet):
    return ''.join(random.choice(charAlphabet) for x in range(length))

def strPoly(fracPairList,charAlphabet=charAlphabet):
    """makes a polynomial list that goes through the given strFrac pairs as points."""
    PStrFracAdd=lambda x,y:strFracAdd(x,y,charAlphabet)
    PStrFracMul=lambda x,y:strFracMul(x,y,charAlphabet)
    PStrFracNeg=lambda x:strFracNeg(x,charAlphabet)
    PStrFracInv=lambda x:strFracInv(x,charAlphabet)
    return createLookup(fracPairList,PStrFracAdd,PStrFracMul,PStrFracNeg,PStrFracInv,(1,charAlphabet[1],charAlphabet[1]),(1,"",charAlphabet[1]))

def strWZeroesPoly(fracZeroesList,charAlphabet=charAlphabet):
    """makes a polynomial list that goes through the given strFrac pairs a points."""
    PStrFracAdd=lambda x,y:strFracAdd(x,y,charAlphabet)
    PStrFracMul=lambda x,y:strFracMul(x,y,charAlphabet)
    PStrFracNeg=lambda x:strFracNeg(x,charAlphabet)
    #PStrFracInv=lambda x:strFracInv(x,charAlphabet)
    return polyWithZeroes(fracZeroesList,PStrFracAdd,PStrFracMul,PStrFracNeg,(1,"",charAlphabet[1]),(1,charAlphabet[1],charAlphabet[1]))

def evalStrPoly(inputX,polyList,charAlphabet=charAlphabet):
    """evaluates a polynomial list of string ratios (polyList) at the given string radio inputX. Specify base system string with the charAlphabet argument."""
    PStrFracAdd=lambda x,y:strFracAdd(x,y,charAlphabet)
    PStrFracMul=lambda x,y:strFracMul(x,y,charAlphabet)
    return evalPoly(inputX,polyList,PStrFracAdd,PStrFracMul,(1,"",charAlphabet[1]),(1,charAlphabet[1],charAlphabet[1]))

def strPolyAutoDenominators(strPairList,charAlphabet=charAlphabet):
    """makes a polynomial list that goes through strFrac pairs as points, which are determines by the string pair inputs, which act as the numerators."""
    inputStrs=map(lambda point:point[0],strPairList)
    outputStrs=map(lambda point:point[1],strPairList)
    inputStrFracList=[(1,inputStr,charAlphabet[1]) for inputStr in inputStrs]
    outputStrsDenomList=[charAlphabet[1] for __ in outputStrs]#change this to random strings that have no common factor with the numerator later.
    outputStrFracList=map(lambda numerator,denominator:(1,numerator,denominator),outputStrs,outputStrsDenomList)
    fracPairList=map(lambda inputFrac,outputFrac:(inputFrac,outputFrac),inputStrFracList,outputStrFracList)
    return strPoly(fracPairList,charAlphabet)

def strFracMakeProper(strFrac1,charAlphabet=charAlphabet):
    (sign1,strNumerator1,strDenominator1)=strFrac1
    strIntPart,strRemainderPart=strDiv(strNumerator1,strDenominator1,charAlphabet)
    return sign1,strIntPart,strRemainderPart,strDenominator1

def strFracMakeImproper(strProperFrac,charAlphabet=charAlphabet):
    sign1,strIntPart,strRemainderPart,strDenominator1=strProperFrac
    __,strNumeratorOut=signedStrAdd((1,strRemainderPart),signedStrMul((1,strIntPart),(1,strDenominator1)))
    strFracOut=sign1,strNumeratorOut,strDenominator1
    return strFracSimplify(strFracOut,charAlphabet)

def decToBase(num,charAlphabet=charAlphabet):
    lenAlphabet=len(charAlphabet)
    outStr=""
    assert charAlphabet != ""
    #assert int(num)==num
    while(num>=1):
        digit=num%lenAlphabet
        outStr=outStr+charAlphabet[digit]
        num=int(num/lenAlphabet)
    return outStr