🔒 Help optimizing a solution

[balmy lodge]

Hi, i was solving this coding problem ( https://www.codewars.com/kata/5a331ea7ee1aae8f24000175 ) which in short is about reducing a string composed of letters indicating colors 'R' ,'G', 'B' into a single letter with rules like : combining red and green gives blue so : 'R' + 'G' will be reduced to 'B' similarly , 'B' and 'G' give 'R' and so on.
my idea is to recursively reduce the string in each iteration by combing every two adjacent colors until it becomes a single letter and return it, but that doesnt seem to be optimal in terms of time since i cant pass the random tests in a short amount of time, my question is, how can i optimize this even further ? because to me, it seems that this is the best we can do.

here's the code :

def triangle(row):
  color_lookup = {
  ('R', 'R'): 'R', ('R', 'G'): 'B', ('R', 'B'): 'G',
  ('G', 'R'): 'B', ('G', 'G'): 'G', ('G', 'B'): 'R',
  ('B', 'R'): 'G', ('B', 'G'): 'R', ('B', 'B'): 'B',
  }
  while len(row) > 1:
    row = [color_lookup[row[i], row[i+1]] for i in range(len(row)-1)]
  return row[0]

Thanks!

[uneven umbra]

@balmy lodge

Python help channel opened

Remember to:

• Ask your Python question, not if you can ask or if there's an expert who can help.
• Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
• Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.

[trail laurel]

interesting problem 🙂 I don't have the answer but I had a thought: if row[i] == row[i+1] you just return row[i], and if they aren't the same you return the third letter. have you considered a solution based on this?

[trail laurel]

judging from comments it seems to be a mathy problem. maybe an upside-down pascal's triangle

[balmy lodge]

thanks for responding! the approach you proposed first works as a solution I hadn't considered it from that perspective at the start also since i think you checked the comments, were they in constant time ? because i think there might be some formula for this by mapping colors to numbers or something

[trail laurel]

comments didnt have solutions, but I'm guessing there's a linear solution awaiting the skilled mathematician's discovery

[fossil elk]

This works for me:

from functools import cache
from itertools import pairwise


colours = 'RBG'


@cache
def merge(a, b):
    if a == b:
        return a
    return colours.replace(a, '').replace(b, '')


def triangle(pattern):
    while len(pattern) > 1:
        new = []
        for a, b in pairwise(pattern):
            new.append(merge(a, b))
        pattern = ''.join(new)
    return pattern


patterns = ['B',                    # 'B'
            'GB',                   # 'R'
            'RRR',                  # 'R'
            'RGBG',                 # 'B'
            'RBRGBRB',              # 'G'
            'RBRGBRBGGRRRBGBBBGG',  # 'G'
           ]


for pattern in patterns:
    print(triangle(pattern))

[uneven umbra]

Python help channel closed

This help channel has been closed and it's no longer possible to send messages here. If your question wasn't answered, feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.