你能帮我减少代码执行时间吗？

Question

我正在做一个关于Codewars的练习，练习（他们的语言是kata）包括在几次操作后返回一个字母，R G或B。我们得到的字符串如下：RGBGBRRB。我们要做一个倒金字塔。。。金字塔的每一行都是这样构建的：here

因此，如果颜色是RG：它的结果是B，如果颜色是BR：它的结果是G；等如果这两种颜色是相同的，就会产生问题的颜色。如果你不明白，我把练习的链接-here-

这是我的代码，从一个角度来看，它是有效的，但Codewars的服务器不允许超过12秒的代码执行时间，我的是其中的一部分。。。你能帮我编一个更快的代码吗

#define the function we have to code

def triangle(row):
    while len(row) > 1: #loop will stop when 'row' will be one char length 
        inter = '' #intermediate string which will be row at the end of the while loop
        inter2 = [None, None] #it is a list where the code put the colour letters to be ''calculated''
        
        for i, color in enumerate(row): #'for' loop which make the new 'line' of inverted pyramid
            if inter2[0] is None: #if the first item of intermediate list isn't a colour yet
                inter2[0] = color
            else: #if the first item of intermediate list is already a colour
                inter2[1] = color #put second colour in second item of the intermediate list
                #'if' condition to add letter to the new ''row'' of the ''inverted pyramid''
                if inter2[0] == inter2[1]: inter += inter2[0]
                if 'R' in inter2 and 'G' in inter2: inter +='B'
                if 'R' in inter2 and 'B' in inter2: inter += 'G'
                if 'G' in inter2 and 'B' in inter2: inter += 'R'
                inter2 = [color, None] #make the future intermediate list (so the first if 
condition will not be used anymore)
            row = inter                 
    return row[0] #return the final colour letter

Answer 1

这是一项具有挑战性的工作。为了超过12秒的时间限制，您可能需要使用一些组合数学（有关非常相关的示例，请参见here）和类似Luca's theorem的东西

公认的答案here使用C进行了更详细的讨论，但原理是相同的。在Python中，可能的解决方案如下所示：

def get_mapping():
    return {'R': 0, 0: 'R',
            'G': 1, 1: 'G',
            'B': 2, 2: 'B',
            }


def signat(n):
    res = []
    i = 0
    while n > 0:
        n, m = divmod(n, 3)
        if m > 0:
            res.append((i, m))
        i += 1
    return res[::-1]


def triangle_recursive(row, sig, pos, acc, accm):
    if pos == len(sig):
        return get_mapping()[row[acc]] * accm
    
    res = 0
    for i in range(sig[pos][1] + 1):
        acc_part = acc + (i * (3 ** sig[pos][0]))
        accm_part = accm
        
        if sig[pos][1] == 2 and i == 1:
            accm_part *= 2
            
        res += triangle_recursive(row, sig, pos + 1, acc_part, accm_part)
    return res % 3


def triangle(row):
    sig = signat(len(row)-1)
    color_val = triangle_recursive(row, sig, 0, 0, 1)
    
    if len(row)%2 == 0:
        color_val = (-1 * color_val) % 3
        
    return get_mapping()[color_val]