Найти максимальное количество идущих подряд троек символов X*Y, Z*Y
Например, для строки 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_))
Ответы (2 шт):
Можно попробовать конечные автоматы - одновременно идут три штуки, стартующие в позициях, кратных 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 - прибавляем единицу и т.д.
Аналогично для автоматов со сдвинутым началом.
Первое решение ошибается на строке 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()))