This code is supposed to take a string of r (red), b (blue) and y (yellow) values and combine them, pairwise, to find one resulting colour. For example, 'rybbry' -> 'brbyb' -> 'yyrr' -> 'ybr' -> 'ry' -> 'b'. It works for small inputs, but forever for big ones. Too many nested loops?

def colour_trio(colours):
  while len(colours) > 1:
    new_colours = ''
    for i in range(len(colours) - 1):
      if colours[i:i 2] == 'rr' or colours[i:i 2] == 'by' or colours[i:i 2] == 'yb':
        new_colours = new_colours   'r'
      elif colours[i:i 2] == 'bb' or colours[i:i 2] == 'ry' or colours[i:i 2] == 'yr':
        new_colours = new_colours   'b'
      else:
        new_colours = new_colours   'y'
    colours = new_colours
  
  if len(colours) == 1:
    if colours[0] == 'b':
        return 'b'
    if colours[0] == 'y':
        return 'y' 
    if colours[0] == 'r':
        return 'r' 

CodePudding user response：

Your code makes use of repeated string concatencation. Each addition operation on a string takes O(n) time, because strings are immutable. This operation occurs O(n^2) times, so the runtime of your algorithm is O(n^3), where n is the length of the string.

One optimization is to use a list to store the letters, and then call ' '.join(), taking the runtime from O(n^3) to O(n^2):

def colour_trio(colours):
    result = colours
    
    while len(result) != 1:
        letters = []
        for fst, snd in zip(result, result[1:]):
            if fst == snd:
                letters.append(fst)
            else:
                [letter_to_add] = list(set('ryb') - set(fst) - set(snd))
                letters.append(letter_to_add)
            
        result = ''.join(letters)
        
    return result
    
print(colour_trio("rybbry")) # Prints "b"

CodePudding user response：

I think this is faster than the last solution I posted and faster than other solutions, I think classes make everything tidy looking, but you can re-work it to become a single function.

New Solution

colors = ['r', 'b', 'y']

def split(x):
    return [f'{Couple(i)}' if len(i)>1 else i for i in 
           [''.join(x[i:i 2]) for i in range(0, len(x), 2)]]

class Couple:
    def __init__(self, x) -> None:
        self.a = x[0]
        self.b = x[1]

    def __repr__(self) -> str:
        if self.a == self.b:
            return self.a
        return (set(colors).difference(set((self.a, self.b))).pop())

def ColoursTrio(x):
    while len(x) > 1:
        x = split(x)
    return x[0]

print(ColoursTrio('rybbry'))

or even shorter (and faster):

def ColoursTrio(x):
    
    while len(x) > 1:
        x = [f'''{i[0] if i[0] == i[1] 
            else  set("rby").difference(set((i[0],
            i[1]))).pop()}''' if len(i)>1 else i for i in 
            [''.join(x[i:i 2]) for i in range(0, len(x), 2)]]
    
    return x[0]

Old Solution

This is almost a bit convoluted but I think it's faster, I also think it's very similar to the one posted by @BrokenBenchmark (and I think his is better) so I'll add his example string too!

COLORS = ['r','b','y']

class ColorsCouple:
    def __init__(self, x:str, y:str) -> None:
        self.x = x
        self.y = y
    
    def mix(self):
        if self.x == self.y:
            return f'{self.x}'
        if 'y' in (self.x, self.y):
            return set(COLORS).difference((self.x, self.y)).pop()
        return 'y'

class Colors:
    def __init__(self, colors:str) -> None:
        self.colors = self.get_couples([*colors])
    
    def get_couples(self, element):
        return [element[x:x 2] for x in range(0, len(element), 2)]

    def get_color(self):
        colors = [ColorsCouple(*couples).mix() if len(couples)==2 else couples[0] for couples in self.colors]
        while len(colors)>1:       
            colors = self.get_couples(colors)
            colors = [ColorsCouple(*couples).mix() if len(couples)==2 else couples[0] for couples in colors]
        return colors[0]

    def __repr__(self) -> str:
        return f'{self.get_color()}'



print(Colors('rybbry'))