24. Подсчет символов: #297633
Текстовый файл состоит из цифр от $1$ до $6$, знаков операций «$-$» и «$*$» (вычитание и умножение) и заглавных латинских букв $A$, $B$, $C$, $D$. Определите максимальное количество символов в непрерывной последовательности символов, состоящей из буквы $A$, за которой следует корректное арифметическое выражение с целыми неотрицательными числами, записанными в десятичной системе счисления.
Задача проще предыдущих на выражения, и вот почему. Цифра $0$ в файле отсутствует вовсе, значит вопрос о ведущих нулях снимается сам собой: любая непустая цепочка цифр — корректное число. Кроме того, старт жёстко зафиксирован буквой $A$, никакой свободы выбора левой границы нет.
Значит алгоритм такой. Находим каждую букву $A$ и пытаемся прочитать сразу за ней максимально длинное корректное выражение. Выражение — это число, за которым идёт любое количество пар «знак операции плюс число». Буквы $B$, $C$, $D$ и сама $A$ внутрь попасть не могут, они обрывают чтение.
Удобнее всего доверить чтение регулярному выражению: жадный поиск сам возьмёт самый длинный корректный кусок и откатится назад, если наткнётся на два знака подряд или на букву сразу после знака. Длина ответа — это длина выражения плюс единица на саму букву $A$.
import re
s = open('24-27.txt').read().strip()
pat = re.compile(r'[1-6]+(?:[-*][1-6]+)*') # число (знак число)*
best = 0
for m in re.finditer('A', s):
i = m.start()
e = pat.match(s, i + 1) # читаем выражение сразу за A
if e:
best = max(best, 1 + (e.end() - i - 1)) # +1 — сама буква A
print(best) # 85
Проверка найденного фрагмента: длина $85$, начинается он с буквы $A$, а остаток целиком распознаётся как корректное выражение. Кончается фрагмент на $543$, а дальше в файле идёт $—B$: два знака подряд, поэтому продлить его нельзя.
Если бы в алфавите присутствовал ноль, задача усложнилась бы ровно на один пункт — пришлось бы отдельно разбирать числа с ведущими нулями, как в разборах выше.