Решение наборов задач из курса CS50 «Введение в программирование на Python» — по одной: Набор задач 7

Читайте оригинальную статью в блоге здесь.

Мы находимся на седьмой неделе, и тема этой недели — всеобщий абсолютный фаворит. И что же это такое? Регулярные выражения, конечно же!

Извините за саркастическое вступление, но действительно, можно с уверенностью сказать, что регулярные выражения могут быть немного кошмарными — особенно для новичков. Однако, не сомневайтесь, это замаскированная суперсила.

Прежде чем мы начнем, я должен сделать обычную оговорку, что эти сообщения в основном посвящены тому, как подходить к решению проблем, а не давать прямые решения. Я также предполагаю, что вы читали объяснения задач, приведенные на сайте курса, так что ссылки, которые я делаю, будут понятны. Кроме того, вы можете найти все сообщения по предыдущим наборам задач в архиве.

Без лишних слов, давайте погрузимся в проблемы этой недели!

NUMB3RS

Первая задача, которую нам нужно решить, очень забавная. Мы проверяем действительные адреса IPv4, которые имеют формат #.#.#.#.# и имеют все свои номера в диапазоне от 0 до 255, включительно. Шаблон — это буквально все; мы ищем цифру, которая может встречаться от 1 до 3 раз, затем точку, затем еще одну цифру от 1 до 3 раз, затем еще одну точку, затем еще одну цифру, снова от 1 до 3 раз, затем точку, и, наконец, последнюю цифру, которая также может встречаться от 1 до 3 раз.

Следует обратить внимание на то, что эта схема должна быть целой — не должно быть ничего ни до, ни после нее. Таким образом, полученный нами ввод должен иметь этот шаблон только между началом и концом. Получить символ цифры и часть «от 1 до 3 раз» легко, если вы изучили документацию или любой другой ресурс в Интернете. Вы также знакомы с начальным и конечным ограничительными символами из лекции. Поскольку мы также знаем, как поместить эти цифры в каждую группу, мы можем проверить, находится ли каждая из них в диапазоне от 0 до 255 включительно. Это можно сделать с помощью простого цикла for, но я хочу показать функцию Python, которая может здесь пригодиться.

Допустим, у нас есть кортеж, в котором есть дома Хогвартса.
Мы хотим проверить, все ли предметы в нем относятся к Рейвенкло, потому что мы не хотим, чтобы нас беспокоили другие дома. Мы можем попробовать следующее:

def check_all(houses):
    return all([house == 'Ravenclaw' for house in houses])

Идея та же, что и здесь:

def check_all(houses):
    result = []

    for house in houses:
        result.append(house == 'Ravenclaw')

    if False in result:
        return False
    else:
        return True

Возможно, не совсем то, что происходит с all, но идея похожа и на эту, только здесь мы возвращаем False раньше времени (не будем называть это check_all, а check):

def check(houses):
    for house in houses:
        if house != 'Ravenclaw':
            return False
    return True

Если дома выглядят как ('Ravenclaw', 'Ravenclaw', 'Gryfindor', 'Ravenclaw'), check_all() вернет False!

Обратите внимание, что внутри функции all у нас есть список, и мы добавляем к нему условие. Затем мы проверяем, есть ли в этом списке False, если да, то возвращаем False, но в противном случае мы возвращаем True, если все условия в нашем списке True.

Аналогичную идею можно применить для проверки того, находится ли каждое число в группах совпадений в диапазоне от 0 до 255 включительно.

Для тестового файла достаточно рассмотреть только те случаи, которые приведены в объяснении задачи и check50.

Это было довольно забавно. Давайте посмотрим на следующую задачу.

Смотрите на Youtube

В этой задаче мы извлекаем и разбираем URL-адреса YouTube, чтобы их можно было легко вставить. Шаблон для нашей программы, опять же, уже дан, нам нужно реализовать функцию parse(), чтобы она вызывалась на main(). Для заданной строки, а именно s, как мы можем начать думать о разборе URL YouTube?

Для начала, мы знаем, что в данной задаче ссылка будет находиться внутри элемента iframe. Мы знаем, что в самом простом виде он будет выглядеть следующим образом:

<iframe src="http://www.youtube.com/embed/xvFZjo5PgG0"></iframe>

Мы знаем, что он должен начинаться с <iframe, за которым следует символ пробела, а затем src=". После этого идет ссылка, а также закрывающие кавычки, закрывающая угловая скобка > и закрывающий тег </iframe>.

Есть еще один момент, внутри ссылки может быть www — это означает, что перед «youtube» может быть ноль или более символов.
«youtube».

Если вы следили за этой серией статей, вы можете заметить, что я уже дал несколько тонких подсказок. Поиск соответствующих символов regex зависит от вас — что гораздо интереснее, и что вы можете найти в документации Python. Кроме того, существует множество способов реализации regex, так что то, как вы придете к решению, в конечном итоге будет зависеть от вас.

Прежде чем продолжить, обратите внимание, что это ссылка http, которую мы обязательно должны превратить в https по соображениям шифрования и безопасности. Если вы захватили эту часть как группу, это легко сделать с помощью условия или замены, как бы вы ни хотели это сделать.

Допустим, нам удалось получить URL http://www.youtube.com/embed/xvFZjo5PgG0, и все в порядке. Или нет?

Это было просто для одного атрибута, но что если у вас есть несколько атрибутов, например, такой:

<iframe width="560" height="315" src="https://www.youtube.com/embed/xvFZjo5PgG0" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>

Вы видите, что src встречается после width и height, а за ним следует куча других атрибутов. Теперь, если вы сделаете это не жадным способом, в качестве URL вы можете получить что-то вроде этого результата:

https://www.youtube.com/embed/xvFZjo5PgG0" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture

Это определенно не URL и не то, что мы ищем. Обратите внимание, что я упомянул термин «не жадный», что это вообще значит?

Допустим, у нас есть строка:

s = '"A string", and "another string".'

Мы хотим получить только "A string", а не "another string". Мы буквально ищем кавычки, один или несколько символов в них, а затем еще одну кавычку. Для простоты давайте сделаем это с помощью этого шаблона:

import re


if matches := re.search('(".+")', s):
    print(matches.group(1))

(Если вы не знакомы с ним, смотрите выражения присваивания для «оператора моржа»).

Однако то, что мы видим в терминале, — это не то, что мы хотим: "строка" и "другая строка".

Происходит то, что .+ выполняет жадный поиск. Однако мы можем предотвратить его превращение в ленивый поиск, просто добавив к нему вопросительный знак:

import re


if matches := re.search('(".+?")', s):
    print(matches.group(1))

Теперь мы видим "A string", как и хотели. Возможно, вам будет интересно посмотреть, как на самом деле работает жадное и ленивое сопоставление.

Использование ленивого квантификатора помогает нам получить URL в правильной форме. После этого нам нужно превратить его в более короткую версию. Мы делаем это, удаляя www или embed/, или .com. Другими словами, мы заменяем — или подменяем — эти части текста ничем. Нам также нужно заменить youtube на youtu.be для результирующей строки.

Как вы будете дальше реализовывать эти маленькие кусочки головоломки, опять же, зависит от вас, поскольку существует множество различных способов решения. Возможно, один из важных выводов — это знание разницы между жадным и ленивым подбором, и как с ними работать. Посмотрим, что нас ждет дальше.

Работа с 9 до 5

Я думаю, что эта проблема имеет так много различных путей решения, что у вас может даже возникнуть паралич анализа (по крайней мере, так было у меня). Что нам нужно сделать, так это преобразовать 12-часовой формат ввода в 24-часовой. При этом наши входные данные должны иметь определенную форму. Например, в нем должно быть слово «до», что-то вроде 9 AM to 5 PM. Мы можем указывать минуты, а можем и не указывать; наш ввод может быть 9 AM to 5 PM или 9:00 PM to 5:00 PM. Кроме того, ввод может подразумевать ночную смену, так что AM и PM могут быть обратными, например 10 PM to 8 AM. Все это кажется многовато, особенно если вы совсем новичок в регулярных выражениях, но, опять же, чтение документации и «ковыряние» в ней может дать некоторое представление. Я не очень доволен решением, которое я придумал, и определенно есть более элегантный способ подумать об этом. Но давайте попробуем понять потенциальный подход.

Во-первых, мы знаем, что можем захватить не только цифры часов и минут, но также AM и PM, поскольку их порядок имеет значение для нашей результирующей строки. Для первого числа (это час) мы знаем, что количество цифр в нем может быть 1 или 2 (например, 9 или 10). Нам нужна цифра, которая имеет от 1 до 2 повторений. После этого, по желанию, может быть двоеточие, за которым следует другая цифра, также имеющая от 1 до 2 повторений. Эта вторая часть предназначена для минут, так что если нам дано 10:00, мы можем захватить часть :00. После этого должен быть символ пробела, за которым следует либо AM, либо PM. Этого достаточно для описания 10:00 PM. После этого у нас есть еще один символ пробела, за которым следует строка «to», затем еще один символ пробела, за которым следует шаблон, который мы только что описали для 10:00 PM. Если мы фиксируем час, минуту и AM/PM как группы, вы можете вспомнить, что у нас также может быть вход, где минуты не указаны — в этом случае наша группа минут приведет к None. Однако мы можем очистить ее и заменить простым :00, так как если минуты не указаны, то предполагается 0. Если совпадения нет, мы также должны выдать ValueError. Для определения ночной смены (если PM наступает раньше AM), мы можем проверить, наступает ли индекс AM раньше PM в нашем списке очищенных групп. В этом случае у нас может быть переменная flag, в которой мы можем сказать, что «ночная смена» — это True или False. После этого нам нужно выполнить преобразование. Мы можем выделить условную ветвь для «не ночной смены» (то есть AM раньше PM), или ночной смены (PM раньше AM), и работать с соответствующими индексами часов и минут. При преобразовании необходимо понимать, что здесь мы не учитываем минуты, только часы. И для AM, если час равен 12, мы должны преобразовать его в 0, в противном случае оставьте его таким, как он указан. Для часа PM, если он равен 12, он должен оставаться 12, но для любого другого числа мы должны добавить к нему 12. Поскольку, похоже, существует много «условий if», я хотел бы упомянуть способ сделать это в Python одним движением. Итак, это может выглядеть примерно так:

hours_am = 0 if int(am_hour) == 12 else int(am_hour)
hours_pm = 12 if int(pm_hour) == 12 else int(pm_hour) + 12

Аналогично этому:

if int(am_hour) == 12:
    hours_am = 0
else:
    hours_am = int(am_hour)


if int(pm_hour) == 12:
    hours_pm = 12
else:
    hours_pm = int(pm_hour) + 12

Конечно, если это начинает усложняться и снижает читабельность, следует избегать чрезмерного использования однострочных слов, но в данном случае это имеет смысл для небольшой реализации.

Нам также нужно проверить, действительны ли часы и минуты — если часы находятся в диапазоне от 0 до 12 включительно, а минуты — в диапазоне от 0 до 59 включительно. Если любое из этих значений недействительно, нам также нужно вызвать ValueError.

И еще одно, нам также необходимо создать файл test_working.py для тестирования нашего кода. Если нет, то мы знаем, что check50 — это наш друг, который подскажет нам, какие тесты нужно пройти. Для проверки того, действительно ли наш код вызывает ValueError в нужных случаях, мы можем вспомнить, как это сделать из задачи «Заправка» из пятой недели.

Эта задача была немного сложной, и я намеренно оставил пробелы в некоторых пунктах, но в этом и есть ее смысл. Процесс мышления может отличаться, здесь я просто описал процесс решения, к которому я пришел, и, надеюсь, дал вам некоторое представление. Давайте посмотрим на следующее.

Регулярные выражения

В этом случае мы проверяем, есть ли в вводимых данных «um», но не считаем его внутри таких слов, как «yummy». Важная идея заключается в том, что мы ищем слово, поэтому оно должно иметь какие-то границы. Как следует из объяснения задачи, это должна быть граница между словом и несловом. Также она может находиться в начале или в конце предложения. Но мы также можем иметь ввод типа um?, за которым следует символ, не являющийся словом, так что мы можем иметь и это опционально. Нам также необходимо учитывать как прописные, так и строчные символы, и флаг re.IGNORECASE позаботится об этом.

В разделе подсказок уже упоминалась функция re.findall(), поскольку она возвращает список всех найденных совпадений, мы можем вернуть длину этого списка из нашей функции count(). Для тестов крайние случаи, которые нужно учитывать, уже приведены на странице объяснения задачи, и этого будет достаточно. Поначалу это выглядит устрашающе, но на самом деле это все, что нужно. Давайте рассмотрим последнюю задачу этой недели.

Проверка ответа

Эта проблема подчеркивает важную привычку, которую необходимо иметь: полагаться на хорошо проверенные библиотеки — нет необходимости упоминать о важности чтения их документации — когда приходит время. А это время может наступить, когда вам понадобится проверить адрес электронной почты. В этой проблеме мы можем выбрать одну из двух библиотек — validator-collection или validators. Нам даже не придется использовать модуль re самостоятельно, потому что эти библиотеки сделают все за нас.

Поскольку решение этой проблемы зависит от того, какую библиотеку вы используете, я не могу дать много подсказок. Документация действительно поможет вам для каждой из библиотек, нам также не нужно писать собственные тесты и для этой. Конечно, хорошей привычкой является обработка ошибок, и это практически все.

Работа с регулярными выражениями может быть действительно сложной, если вы никогда не использовали их раньше. Тем не менее, мы убедились, что это суперспособность, которая пригодится при решении любых проблем. На следующей неделе мы рассмотрим объектно-ориентированное программирование. До тех пор, счастливого кодирования.