Задача на декомпрессию строки. Почему код проходит не все тесты?

Question

[n3dimo4ka]

Здравствуйте! Нужна помощь с пониманием задачи. Задача:

Дана строка, состоящая из букв латинского алфавита. В целях ее компрессии разрешается любые ее непустые подстроки (подстрокой называется последовательность идущих подряд символов строки) сжимать по следующему правилу. Строка A, состоящая из повторений некоторой непустой строки B, записывается как символ «(», затем количество повторений (целое число от 1 до 105, записанное без ведущих нулей), затем строка B, и, наконец, символ «)». Например, строку ababab можно сжать, записав ее как (3ab).

В данной задаче допускается повторное сжатие подстрок строки. Разумеется, можно сжимать лишь части, состоящие только из букв латинского алфавита. Например, строку acacacaacacaca можно сжать, записав ее в виде (2acacaca), и осуществить дальнейшую компрессию: (2(3ac)a).

Ваша задача осуществить обратное преобразование, то есть преобразовать строку из сжатого вида в несжатый.

Входные данные

Во входном файле записана непустая строка в сжатом виде. Длина строки не превосходит 1000 символов.
Выходные данные

Выведите результат декомпрессии строки. Гарантируется, что длина ответа не превосходит 105 символов. Заметим, что в результате декомпрессии длина строки может уменьшиться.

У меня вопрос по поводу условия о уменьшении длины в результате декомпрессии. Когда такое может быть?

Так же я написал код, но он проходит не все тесты:

string = input()
#(3(2aba)) > (3abaaba) > (abaabaabaabaabaaba)
 
latest_close = string.rfind(')')
first_close = string.find(')')
latest_start = string.rfind('(')
 
def find_cnt(s):
    i = 0
    digit = ''
    while s[i].isdigit():
        digit += s[i]
        i += 1
    repeat = s[i:]
    return int(digit), repeat
 
 
 
while string.rfind(')') != -1:
    count, repeat = find_cnt(string[latest_start+1:first_close])
    repeated = ''
    for _ in range(count):
        repeated += repeat
    new_string = string[:latest_start] + repeated + string[first_close + 1:]
    string = new_string
 
    latest_close = string.rfind(')')
    first_close = string.find(')')
    latest_start = string.rfind('(')
 
print(string)

Прошу помощи в данных вопросах. Спасибо.

Answer 1

[Andrey Dugin]

К чему такие сложности

import re

def decode(encoded):
    def repl(m): return m.group(2) * int(m.group(1))
    reg = re.compile('\((\d+)(\w+)\)')
    while True:
        decoded = reg.sub(repl, encoded)
        if decoded == encoded:
            return decoded
        encoded = decoded 
        
assert decode('(2(3ac)a)') == 'acacacaacacaca'
assert decode('(3(2aba))') == 'abaabaabaabaabaaba'
assert decode('(3a)') == 'aaa'  # уменьшение длины

Comments

[Max Payne]

Пожалуйста, куратор тега, не советуйте присваивать лямбды переменным.

[Andrey Dugin]

Max Payne, почему? Это способ избежать создания функции через def или запихивания громоздкого определения lambda прямо в место её вызова, что не улучшает читаемость кода. Присвоение лямбды переменной ничем не отличается от стандартного создания функции с таким же именем:

def repl(m):
    return m.group(2) * int(m.group(1))

По той же причине - избежать визуальной замусоренности - я и регулярку вынес в отдельную строку. Можно было так:

decoded = re.sub('\((\d+)([a-z]+)\)', lambda m: m.group(2) * int(m.group(1)), encoded)

[Max Payne]

Andrey Dugin, Как минимум: использование def - единственный верный способ, предлагаемый PEP8 (PEP8 / Programming Recomendations).

По поводу "а можно было так" - лямбы для того и создавались, чтобы "можно было так".

[Max Payne]

Andrey Dugin, У меня есть некоторые сомнения по поводу того, в чем же будет отличие def repl от repl = lambda, но так сходу я много, наверное, не расскажу :)
То что можно сказать сходу, так это что def выполняется интерпретатором и область видимости там будет статична, а лямба это дженерик, который по этой же причине нельзя сериализовать, поэтому если так часто делать - в один день можно напороться на очень неприятную штуку. Конечно пока мы работаем с регулярками ничего страшного не будет.

[Andrey Dugin]

Max Payne, сам исходный код Python не всегда следует PEP8. Например, def __init__() должно писаться без отделения пустой строкой от объявления класса, но это редко кто соблюдает. Мне не жалко, я заменил в своём ответе lambda на однострочник с def.

[DmutruyH4k]

А если у нас заглавные буквы будут?
Предлагаю написать так:
reg = re.compile('\((\d+)([a-z, A-Z]+)\)')

[Andrey Dugin]

DmutruyH4k, \w+