Найти максимальное количество идущих подряд троек символов X*Y, Z*Y

Рейтинг: 0Ответов: 2Опубликовано: 25.03.2023

Например, для строки XXY YXZ YXX YZZ YYY (для удобства разделено на тройки) необходимо найти максимальное количество подряд идущих троек вида X?Y, Z?Y. Так, количеством может быть 2 тройки подряд или 4 тройки подряд: 2 тройки - XXY Y XZY XXY ZZYYY; 4 тройки - X XYY XZY XXY ZZY YY. Собственно, если это не учитывать (что комбинации могут быть разными), то в ответе возникает 2 тройки подряд. Как это учесть в коде и реализовать понятным, лаконичным, практичным образом? Может, через регулярки? (нижний код c похожим примером на первый взгляд понять может быть трудно)

f = open('24-197.txt')
s = f.readline()
mx = 0
l = 0
i = 0
flag = False
while i < len(s) - 2:
    if s[i] in 'XZ' and s[i+2]=='Y':
        l = l  + 1
        i = i + 3
        flag = True
    else:
        mx = max(l, mx)
        l = 0
        if flag:
            i = i - 2
        else:
            i = i + 1
        flag = False
    
print(mx)
f.close() #->6

второе решение по вопросу:

s = 'XXYYXZYXXYZZYYY'
max_ = c = 0

for j in 0,1,2:
    c = 0
    for i in range(j,len(s)-2,3):
        if s[i]+s[i+1]+s[i+2] in ('XZY','XXY','XYY', 'ZYY','ZXY','ZZY'):
            c+=1
            max_ = max(max_,c)
        else:
            c = 0
    print("j: %d max: %d"%(j,max_))
python строки
Источник: Stack Overflow на русском

Ответы

▲ 0

Можно попробовать конечные автоматы - одновременно идут три штуки, стартующие в позициях, кратных 3, в позициях 3k+1, в позициях 3k+2. Это будет довольно развесисто, но легко читаемо.

Например, для автомата в позиции 3k начальное состояние st=0. Встретили в этой позиции X или Z - переходим в состояние 1. В позиции 3k+1, если состояние нулевое, то оно и сохраняется, иначе прибавляем единицу. В позиции 3k+2, если состояние нулевое, то оно и сохраняется, иначе, если встретили Y - прибавляем единицу, если другой символ - выдаем количество троек st//3 и сбрасываем st в 0. В позиции 3k, если состояние ненулевое, и встретили Y - выдаем количество троек st//3 и сбрасываем st в 0, а если встретили X или Z - прибавляем единицу и т.д.

Аналогично для автоматов со сдвинутым началом.

▲ 0

Первое решение ошибается на строке XXY - возвращает 0, а должно вернуть 1.

Второе решение выглядит рабочим. Его можно ускорить - внешний цикл заменить на три счётчика, убрать индексы из внутреннего цикла, убрать работу со средним элементом в if. Будет что-то такое:

def longest(s):

    def gen():
        it = iter(s)
        next(it, None)
        next(it, None)

        f0, f1, f2 = 0, 0, 0
        for c1, c2 in zip(s, it):
            if c1 in 'XZ' and c2 == 'Y':
                f0, f1, f2 = f1, f2, f0 + 1
                yield f2
            else:
                f0, f1, f2 = f1, f2, 0


    return max(gen(), default=0)


with open('24-197.txt') as f:
    print(longest(f.readline()))