# First we implement the eerTree data structure of Rubinchik and Shur (this speeds up the backtracking searches)

class eerTree():  
    def __init__(self,word):
        self._word=''
        self._vertices={'':0,-1:-1}
        self._edges={'':{},-1:{}}
        self._links={'':-1,-1:-1}
        self._palSuf=-1
        self._palSufStack=[-1]
        self._newPalStack=[None]
        for i in range(len(word)):
            self.add(word[i])
       
    def __repr__(self):
        return "An eerTree for a string with %s palindromes."%(self.numPals())

    def numPals(self):
        count=1
        L=self._newPalStack
        for i in range(len(L)):
            if not L[i]==None:
                count+=1
        return count
   
    def add(self,letter):
        cs=self._palSuf
        self._newPal=False
        
        while not cs==-1:
            
            if len(cs)==len(self._word):
                cs=self._links[cs]
            
            csl=self._vertices[cs]
            
            if self._word[-csl-1]==letter:
                
                pal=letter+cs+letter
                
                if self._edges[cs].get(letter)==None:
                    self._newPal=True
                    self._vertices[pal]=len(pal)
                    self._edges[pal]={}
                    self._edges[cs][letter]=pal
                    ns=self._links[cs]
                    
                    while not ns==-1:
                        nsl=self._vertices[ns]
                        if self._word[-nsl-1]==letter:
                            
                            nextpal=letter+ns+letter
                            break
                        
                        ns=self._links[ns]
                            
                    if ns==-1:
                        nextpal=letter
                        
                    self._links[pal]=nextpal
                
                self._palSuf=pal
                
                break
            
            cs=self._links[cs]
            
        if cs==-1:
            if self._edges[cs].get(letter)==None:
                self._newPal=True
                self._vertices[letter]=1
                self._edges[letter]={}
                self._edges[-1][letter]=letter
                self._links[letter]=''
            self._palSuf=letter
            
        self._word+=letter
        self._palSufStack+=[self._palSuf]
        if self._newPal:
            self._newPalStack+=[cs]
        else:
            self._newPalStack+=[None]
        
    def pop(self):
        u=self._palSuf
        indicator=self._newPalStack.pop()
        if not indicator==None:
            del self._vertices[u]
            del self._links[u]
            del self._edges[u]
                
            if len(u)>1:
                v=u[1:-1]
            else:
                v=-1
            del self._edges[v][u[-1]]
        
        self._palSufStack.pop()
        self._palSuf=self._palSufStack[-1]
        self._word=self._word[:-1]

# Next we define some procedures for detecting top/bottom-(plus)-powers and specific factors in words

def PowerSuffix(w,top,bottom):  # Returns a suffix of w with exponent at least top/bottom, or "None" if w has no such suffix
    n=len(w)
    p=1
    while n*bottom>=p*top:
        i=0
        while w[-1-i]==w[-1-i-p]:
            if (i+1+p)*bottom>=p*top:
                return w[-1-i-p:]
            i+=1
            if i+p>=n:
                break
        p+=1
    return None

def PowerPlusSuffix(w,top,bottom):  # Returns a suffix of w with exponent greater than top/bottom, or "None" if w has no such suffix
    n=len(w)
    p=1
    while n*bottom>p*top:
        i=0
        while w[-1-i]==w[-1-i-p]:
            if (i+1+p)*bottom>p*top:
                return w[-1-i-p:]
            i+=1
            if i+p>=n:
                break
        p+=1   
    return None

def PowerPlus(w,top,bottom):  # Returns a factor of w with exponent greater than top/bottom, or "None" if w has no such factor
    p=[]
    for i in range(len(w)):
        p.append(w[i])
        Test=PowerPlusSuffix(p,top,bottom)
        if not Test==None:
            return Test 
    return None

def Power(w,top,bottom):  # Returns a factor of w with exponent at least top/bottom, or "None" if w has no such factor
    p=[]
    for i in range(len(w)):
        p.append(w[i])
        Test=PowerSuffix(p,top,bottom)
        if not Test==None:
            return Test     
    return None

def PowerPlusSuffixShortPeriod(w,top,bottom,per):  # Returns a suffix of w of exponent greater than top/bottom and period less than per, or "None" if w has no such suffix
    n=len(w)
    p=1
    while n*bottom>p*top and p<per:
        i=0
        while w[-1-i]==w[-1-i-p]:
            if (i+1+p)*bottom>p*top:
                return w[-1-i-p:]
            i+=1
            if i+p>=n:
                break
        p+=1
        
    return None

def HasBadSuffix(w,bad_factors):  # Returns a suffix of w belonging to bad_factors, or "False" if no suffix of w belongs to bad_factors
    for x in bad_factors:
        if w[-len(x):]==x:
            return x
    return False


# Some procedures for determining the image of words under morphisms/other maps

def Morph(f,w):  # Returns the image of w under the morphism f
    m=[]
    for i in range(len(w)):
        m+=f[w[i]]
    return m

def Add2Between10(w):  # Returns the word obtained from w by adding a 2 in the middle of every factor 10
    W=[]
    for i in range(len(w)-1):
        W+=[w[i]]
        if w[i]==1 and w[i+1]==0:
            W+=[2]
    W+=[w[-1]]
    return W

def ListToString(l): # Converts a list of integers to a string for ease of reading
    w=''
    for i in range(len(l)):
        w+=str(l[i])
    return w


# The main backtracking algorithm

def BackTrack(n,k,p,top,bottom,bad_factors,prefix):   # A backtracking search that finds a word of length n over k letters starting with prefix that is top/bottom-free, contains at most p palindromes and avoids all words in bad_factors, or returns the length of the longest word satisfying those properties
    longest = prefix   # longest word obtained so far
    T=eerTree('')
    w=[]
    for i in range(len(prefix)):
        w+=[prefix[i]]
        if PowerSuffix(w,top,bottom):
            print('The prefix you entered has a forbidden repetition.')
            return
        T.add(str(prefix[i]))
        if HasBadSuffix(w,bad_factors):
            print(f'The prefix you entered has the forbidden factor {HasBadSuffix(w,bad_factors)}.')
            return
    if T.numPals()>p:
        print(f'The prefix you entered has more than {p} palindromes.')
        return
    extension = [int(0)]   # the list that we add to prefix
    T.add('0')
    while extension:  # Continues while the length of extension is greater than zero (if extension is ever empty, then we have searched the whole tree)
        w = prefix + extension
        if PowerSuffix(w,top,bottom)==None and T.numPals()<=p and not HasBadSuffix(w,bad_factors):
            if len(w)>len(longest):
                longest=w       # w is the new longest word
            if len(w) == n:
                print("Found a word of length",n)  
                print(ListToString(w))     # Found a word of the desired length
                return w
            else:
                extension+=[0]  # If we have not yet reached length n, keep extending
                T.add('0')
        else:
            a = extension.pop()   # If w is no good, then back up!
            T.pop()
            
            while extension and a == k-1:  # Continue backing up until we reach the first letter that can be incremented by 1
                a = extension.pop()
                T.pop()

            if not a == k-1:  
                extension+=[a+1]   # Increment the last letter by 1
                T.add(str(a+1))
    
    print(f"There are only finitely many {top}/{bottom}-free words with at most {p} palindromes avoiding all factors in {[ListToString(x) for x in bad_factors]}. The longest such word has length {len(longest)}.")

    return len(longest)

def FindAllPowerFree(n,k,pattern,top,bottom,prefix=[]):   #Finds all words of length n over k letters starting with prefix that are top/bottom-(plus)-free (depending on whether pattern is PowerSuffix or PowerPlusSuffix)
    
    L=[] # Our list of top/bottom-(plus)-free words of length n
    longest = prefix 
    w=[]
    for i in range(len(prefix)):
        w+=[prefix[i]]
        if pattern(w,top,bottom):
            print('The prefix you entered has a forbidden repetition.')
            return
    extension = [int(0)]

    while extension:
        w = prefix + extension
        if pattern(w,top,bottom)==None:
            if len(w)>len(longest):
                longest=w
            if len(w) == n:
                L.append(w) # If we reach length n, add w to our list and back up
                a = extension.pop()
            
                while extension and a == k-1:
                    a = extension.pop()

                if not a == k-1:  
                    extension+=[a+1]

            else:
                extension+=[0]
                
        else:
            a = extension.pop()
            
            while extension and a == k-1:
                a = extension.pop()

            if not a == k-1:  
                extension+=[a+1]

    return L

def FindAllMinimalPowers(n,k,top,bottom):  # Returns all minimal top/bottom-plus-powers of period n over k letters (minimal in the sense that removing the first or last letter leaves a word whose exponent is at most top/bottom, and also in the sense that it contains no shorter top/bottom-plus plower as a factor)
    P=[]
    for w in FindAllPowerFree(n,k,PowerPlusSuffix,7,3):
        i=0
        indicator=True
        W=w.copy()
        while (n+i)*bottom<= n*top:
            W+=[w[i-n]]
            if PowerPlusSuffixShortPeriod(W,7,3,n):
                indicator=False
            i+=1
        if indicator:
            P.append(W)

    return P


# Backtracking search for Theorem 1(b)
print('')
print('---------- Backtracking search for Theorem 1(b) ----------')
BackTrack(1000,3,5,10,3,[],[0])
print('')

# Backtracking search for Theorem 1(c)
print('---------- Backtracking search for Theorem 1(c) ----------')
BackTrack(1000,3,15,2,1,[],[0])
print('')

# Backtracking search for Theorem 1(d)
print('---------- Backtracking search for Theorem 1(d) ----------')
BackTrack(1000,3,17,41,22,[],[0])
print('')

# Check of cube-free binary words of length at most 24 for Theorem 3(a)
print('---------- Check of short cube-free binary words for Theorem 3(a) ----------')
f=[[0,1,2],[0,0,1,2]]
indicator=True
for ell in range(1,25):
    for w in FindAllPowerFree(ell,2,PowerSuffix,3,1,prefix=[]):
        W=Morph(f,w)
        if not PowerPlus(W,10,3)==None:
            print(f'The f-image {W} of the word {w} contains the 10/3-plus-power {PowerPlus(W,10,3)}.')
            indicator=False
if indicator==True:
    print('The f-image of every binary cube-free word y of length at most 24 is 10/3-plus-free.')
print('')

# Backtracking search for Theorem 5
print('---------- Backtracking search for Theorem 5 ----------')
BackTrack(1000,3,6,9,4,[[1,1],[2,2]],[])
print('')
# Check of binary 7/3-plus-powers of period less than 18 for Theorem 5
print('---------- Check of short binary 7/3-plus-powers for Theorem 5 ----------')
indicator=True
for n in range(1,18):
    for w in FindAllMinimalPowers(n,2,7,3):
        W=Add2Between10(w)
        if PowerPlusSuffix(W,9,4)==None:
            print(f'The word {W} obtained from the 7/3-plus-power {w} by adding a 2 in the middle of every factor 10 contains no 9/4-plus-power.')
            indicator=False
if indicator==True:
    print('For every binary word w with exponent greater than 7/3 and period less than 18, the word obtained from w by adding a 2 in the middle of every factor 10 contains a factor of exponent greater than 9/4.')
print('')

# Backtracking search for Theorem 8(c)
print('---------- Backtracking search for Theorem 8(c) ----------')
BackTrack(1000,3,17,25,13,[[0,1,0]],[])
print('')

# Backtracking search for (a) => (b) in Lemma 15 
print('---------- Backtracking search for (a) => (b) in Lemma 15 ----------')
BackTrack(1000,3,16,2,1,[[0,1,0]],[])
print('')