p122 - Efficient Exponentiation

p122.py

def compute(limit):
    
    v = [0]*(limit + 1) #v[k] = minimum number of multiplication to get n^k
    count = 1 #Counting the number of solved k's. It's used to stop the while loop
    
    stack = [(1,)] #The start stack, the only path of length 0 in the tree
    currdepth = 1 #Keeping track of the current depth we are in the tree
    
    while count != limit:
        #We continue till we have found all 0 < k < 201

        nextstack = [] #We initalize a variable to store paths for the next round (That is the next level in the tree)
        
        while stack != []:
            path = stack.pop() #Get a current path
            m = path[-1] #Keep the maximum value to ensure our addition chain is strictly increasing
            
            for i in range(len(path) - 1, -1, -1):
                for j in range(i, -1, -1):
                    #Loop through the bath backwards (We do this because a path can only use elements previously seen)
                    
                    k = path[i] + path[j] #The new head of the path
                    
                    if k <= m:
                        #If the head is smaller than max, this is not a strictly increasing path
                        break
                        
                    if k <= limit:
                        #Do not process paths that go past our goal
                        if v[k] == 0:
                            #If we have not yet seen a path to the value k, then this must be a shortest path to k
                            v[k] = currdepth
                            count += 1
                            
                            if count == limit:
                                #Quickly exit the function, avoid processing extra paths
                                stack = []
                                nextstack = []
                                break   
                        nextstack.append(path + (k,)) #Add the created path to the nextstack to be processed in the next depth level
        #After current level is finished being processed, update the stack to the next depth
        stack = nextstack 
        currdepth += 1
    return sum(v)