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

Question

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

因此，如果颜色为 RG：结果为 B，如果颜色为 BR：结果为 G；等等...如果两种颜色相同，则会产生有问题的颜色。如果你没看懂，我把练习的link放到-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 for a very relevant example) and something like Luca's theorem.

接受的答案使用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]

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

Can you help me decreasing my code time execution?

python

rgb

colors