Навигация по странице
Тип 3
Переходим к третьему типу заданий 24. К нему мы отнесем задания с формулировками, которые содержат фразу «символы не стоят рядом».
Здесь по логике будет проще использовать метод с заменой и разделением строки на подстроки. Представьте, что вам нужно найти максимальную длину подстроки, в которой символы A и B не стоят рядом.
Допустим, есть такой отрывок строки: «ABСCACACACABCACAB». Как вы будете рассуждать, если вас попросят найти подстроку, в которой нет пары AB?
Для начала вы найдете все нужные пары AB в строке (на рисунке их выделим оранжевым цветом).
Вторым вашим действием будет определить все символы между B и A. Но для удобства проще будет поставить какие-либо символы-разделители между буквами A и B в паре AB, например, пробел.
В таком случае мы можем разделить подстроку по пробелу и получить уже список строк. Тогда нам остаётся только найти длины этих строк и определить наибольшее значение среди них.
В нашем случае максимальная длина подстроки, в которой символы A и B не стоят, рядом равна 10.
В этом и заключается метод с заменой и разделением строки. Но такие задачи также запросто решаются и через регулярные выражения. Продемонстрируем это на примере со следующей формулировкой.
Задание 2401
«Текстовый файл состоит не более, чем из 107 строчных букв английского алфавита. Найдите максимальную длину подстроки, в которой символы a и d не стоят рядом»
Давайте составим строку, которая будет служить нам примером, и визуализируем её. Пусть это будет строка «adссacacacadcacad». Выделим на рисунке искомые пары символов.
То есть нам нужно, чтобы и до, и после нашей строки находилась пара символов «ad» (или «da»). Причём между этими парами можем захватывать 1 и более (квантификатор «+») любых символов.
Но нам также нужно учесть, что этот квантификатор должен быть «ленивым», то есть захватывать как можно меньше символов между парами «ad» (или «da»).
Иначе здесь вместо двух подстрок «ссacacac» и «cac» получим всего одну – «ссacacacadcac», которая находится между самой первой и самой последней парой «ad».
Главное – не забыть добавить еще два символа, ведь мы ищем подстроки строго между парами «ad», но не учитываем, что в эту подстроку входят оба символа: «d» слева и «a» справа.
С общей логикой разобрались, переходим к составлению регулярного выражения. Для наглядности будем составлять его из трёх частей, но вы можете писать все части в одном регулярном выражении.
Начнем с того, что определим выражение для ленивого поиска любого символа в количестве 1 и более штук:
sym_lazy = r'.+?'
Теперь переходим к определению пар «ad» или «da». Нам на помощь придут ретроспективная и опережающая проверки.
Для определения пары «слева» от нужной подстроки напишем такое выражение с ретроспективной проверкой «(?<=…)»:
left_pair = r'(?<=ad|da)'
По аналогии будем определять пару и «справа», только теперь используя опережающую проверку «(?=…)»:
right_pair = r'(?=ad|da)'
Соединяем три части в одно выражение через f-строки:
pattern = rf'{left_pair}{sym_lazy}{right_pair}'
Дописываем в нашу программу считывание данных с файла, работу функции finditer() и поиск максимальной длины подстроки.
import re
with open('2401.txt', 'r') as file:
data = file.readline()
sym_lazy = r'.+?'
left_pair = r'(?<=ad|da)'
right_pair = r'(?=ad|da)'
pattern = rf'{left_pair}{sym_lazy}{right_pair}'
matches = re.finditer(pattern, data)
# Ищем максимальную длину строки
answer = max([len(match.group()) for match in matches])
# К ответу добавляем потерянные символы (d или a)
print(answer + 2)
Теперь мы готовы дать ответ на это задание – число 2252.
Пример 1
Формулировка задания теперь будет такой:
Задание 2411
«Текстовый файл состоит из арабских цифр (0, 1, …, 9).
Определите максимальное количество идущих подряд символов в прилагаемом файле, среди которых нет символов 1 и 2, а также 1 и 3 стоящих рядом.
Для выполнения этого задания следует написать программу»
Сначала решим это задание через регулярные выражения, а затем способом с заменой и разделением строки.
Регулярное выражение для ленивого поиска любого символа здесь будет таким же, как и в прошлом примере:
sym_lazy = r'.+?'
Но количество пар здесь будет побольше. Поскольку тут нам даны сразу две пары, то составим отдельное выражение с ними:
pairs = r'(12)|(21)|(13)|(31)'
В переменную pattern все также подставляем написанные ранее выражения, не забывая оборачивать выражение из pairs в скобки для рекурсивной и опережающей проверок:
pattern = rf'(?<={pairs}){sym_lazy}(?={pairs})'
Полный код для решения этого задания выглядит так:
import re
with open("2411.txt") as file:
data = file.readline()
sym_lazy = r'.+?'
pairs = r'(12)|(21)|(13)|(31)'
pattern = rf'(?<={pairs}){sym_lazy}(?={pairs})'
matches = re.finditer(pattern, data)
# Ищем максимальную длину строки
answer = max([len(match.group()) for match in matches])
# К ответу добавляем потерянные символы (1 или 2)
print(answer + 2)
В результате получаем число 339.
Теперь решим это задание вторым способом. Сначала все как обычно – считываем строку из файла в data.
with open('2411.txt', 'r') as file:
data = file.readline()
Но дальше нам необходимо расставить пробелы между парами 1 и 2, а также 1 и 3. Сделаем это с помощью замен:
data = data.replace("12", "1 2")
data = data.replace("13", "1 3")
data = data.replace("21", "2 1")
data = data.replace("31", "3 1")
С помощью метода split() разделяем изменённую строку по пробельным символам. И вычисляем максимальное значение длины строк в списке data.
data = data.split() answer = max(map(len, data)) print(answer)
Итоговый код для этого задания будем таким:
with open('2411.txt', 'r') as file:
data = file.readline()
data = data.replace("12", "1 2")
data = data.replace("13", "1 3")
data = data.replace("21", "2 1")
data = data.replace("31", "3 1")
data = data.split()
answer = max(map(len, data))
print(answer)
И на экране, конечно же, видим то же самое число – 339.
Пример 2
Рассмотрим еще одно 24 задание третьего типа. Формулировка здесь такая:
Задание 2417
«Текстовый файл состоит не более, чем из 1 200 000 прописных символов латинского алфавита. Определите максимальное количество идущих подряд символов, среди которых любые два символа из набора Q, R, S в различных комбинациях (с учётом повторений) не стоят рядом.
Для выполнения этого задания следует написать программу»
Решать его будем все так же через замены, но в этот раз не получится просто расставлять пробельные символы между нужными парами. Здесь придётся делать замены символов Q, R и S на какой-то один другой символ, например, на точку.
Тогда разделять подстроки будет по двум точкам, стоящим рядом, которые будут соответствовать любой комбинации пар символов Q, R и S.
Начнём составлять алгоритм на таком примере: допустим, что нам дана строка «SSACAQBAQSBRBARQABQQ». Нужно найти все подстроки, расположенные между парами из символов Q, R и S (такие пары выделены оранжевым).
Логично предположить, что нужно разбить исходную строку на подстроки, которые находятся между выделенными парами. Но мы же не будем все комбинации пар передавать в метод split()?
Можно же просто заменить нужные символы на точки, тогда в split() останется просто передать две точки, по которым и будет разбиваться исходная строка.
В итоге получим такие 3 подстроки:
Но в процессе рассуждения мы упустили важную деталь: нам подходят не подстроки между парами символами, а эти подстроки, содержащие в начале и в конце по одному символу из пары. То есть в «SSACAQBAQSBRBARQABQQ» такими будут:
- SACAQBAQ
- SBRBAR
- QABQ
То есть к длине каждой полученной нами подстроки необходимо добавить еще по 2 символа, которые мы удалили, используя split(): один в начале и один в конце строки.
Наш алгоритм готов, теперь реализуем его в коде. Считываем данные из файла:
with open('2417.txt') as file:
data = file.readline()
Проводим замены:
data = data.replace("Q", ".")
data = data.replace("R", ".")
data = data.replace("S", ".")
И разделяем строку на подстроки по двум точкам «..»:
data = data.split("..")
Вычисляем наибольшую длину среди всех элементов списка data и прибавляем к полученному значению число 2.
answer = max(map(len, data))
print(answer + 2)
Программа целиком выглядит так:
with open('2417.txt') as file:
data = file.readline()
data = data.replace("Q", ".")
data = data.replace("R", ".")
data = data.replace("S", ".")
data = data.split("..")
answer = max(map(len, data))
print(answer + 2)
В результате на экране видим ответ на это задание – число 544.