Advent of Code 2020 (26 части серии)
В котором я исследую полностью переполненное решение проблем, которое не Regex: Государственные машины!
Все упомянутые в этом посте: Штатные машины, список пометки, PYTRANSIONTS, String Bibчищик
Ссылка на вызов на Advent of Code 2020 сайта 2020
Задача представлена в качестве задачи анализа паролей, вам предоставляется список строк, которые имеют определенный формат, и попросили применить некоторые правила проверки.
Приведенный пример был:
1-3 a: abcde 1-3 b: cdefg 2-9 c: ccccccccc
Формат:
- Номер (низкий диапазон)
- тире
- Номер (высокий ассортимент)
- Космос
- письмо (рассматриваемое письмо)
- Колон и пространство
- строка для проверки
Правило проверки: Строка для проверки должна содержать рассматриваемое письмо между Низкий и высоко раз (включительно).
Для этой задачи есть две части: анализ, который является акт предпринятия некоторого ввода и извлечения полезных «битов» (тренажера спойлера: regex); И валидация, которая принимает эти «биты» и применяет некоторые правило для выяснения, считается ли он действительным или нет. Из этих двух частей это разбор, тем более сложная часть.
Чтение файла
Как обычно, данные поставляются как одна «запись» на строку в текстовом файле. Я рассуждаю с накоплением, так как я уже много охватил о чтении файлов в день 01, и пропустить прямо к хорошему веду:
data = open("input.txt").readlines()
Результат:
['1-2 x: xpxc\n', '1-5 b: bwlbbbbcq\n', '3-5 v: qvjjdhvl\n', '9-12 t: ttfjvvtgxtctrntnhtt\n', ...
Вот и все. Ничего больше. Хотя Python использовать контекстный менеджер с открытым () как FP: Чтобы открыть файлы (по причинам, по которым я упоминал ранее), для такого короткого упражнения я бросаю осторожность на ветра в пользу удобства.
Так как мы хотим простой массив строк, Readleines () Функция хорошая и простая, чтобы использовать, хотя она в конечном итоге с некоторыми дополнительными новыми линиями в конце строк ( \ n символы в выходе выше), те, кто будет игнорировать код позже, поэтому я не будет беспокоить их.
Наивеное решение
Я буду спереди и говорю, что этот вопрос кричит Regex. В любое время у вас есть такая проблема анализа, когда данные хорошо отформатированы, но не существующий машиночитаемый формат (например, XML, json и т. Д.), а не разграничен регулярным способом (например, CSV), Regex может быть ответ.
Но для вашего развлечения я собираюсь посвятить этот пост, чтобы идти в любое направление, которое не регулярно (часть 2 будет охватывать решение Regex, которое существенно короче).
Итак, если мы не допускаем Regex, как бы мы это сделали? На самом деле это не так. Когда мы работаем с низкоуровневыми системами (код, который должен работать на очень небольших ресурсах, или работать очень быстро), часто необходимо проанализировать структурированные данные.
Большинство подходов для такого рода данных включают чтение входящей строки одного символа одновременно и принять наиболее подходящие действия для каждого персонажа в зависимости от того, что оно и что было раньше. Давайте распустим одну из многих записей данных, и посмотрите на него:
entry = data[3]
print(entry)
for char in entry:
print(char)
Выход
9-12 t: ttfjvvtgxtctrntnhtt 9 - 1 2 t : t t f j v v t g x t c t r n t n h t t
Это те данные, с которыми мы имеем дело. Обратите внимание, что Python довольно рад, позволяя вам повторить один символ во время над строкой, используя все удобные для ... как Отказ
Так что, если бы я был машиной, делая это, что бы я делал? Может быть, что-то вроде этого:
- Я вижу 9. Это число, отличное, так как я ищу первый «низкий» номер, я пойду, что
- Я вижу тире. Хорошо, это не было еще одним номером, поэтому необходимо сделать «низкий» номер, давайте перейдем к поиску номера «высокого»
- Я вижу 1. Это число, отличное, я пойду, что для «высокого» числа
- Я вижу 2. Это еще одно число, положить его вместе с предыдущим
- Я вижу пространство. Хорошо, это означает, что мы закончили с помощью «высокого» числа, двигаясь на поисках буквы
- Я вижу «т». Хорошо, это мой характер и т. Д.
Как видите, потому что номера иногда проводят несколько символов, мы не можем просто сломать его в приятные, предсказуемые персонажи, которые считают, что мы должны прочитать каждый персонаж, чтобы решить, куда он должен идти, и делаем ли мы с помощью сканирования для ценность.
Другими словами: «Какое состояние мы находимся в« вопросах »(где государство, вероятно, является одним из« чтения низкого числа »,« чтение высокого числа »и т. Д.)
С учетом того, что мы можем повторно указать наш алгоритм читать больше, как это:
- Когда я нахожусь в состоянии «читать низкое число». Если я увижу номер, добавьте это в низкую строку. Если я увижу характерный характер, двигайся на Состояние «чтение большого количества»
- Когда я в состоянии «читать высокое число». Если я увижу номер, добавьте это в высокую строку. Если я вижу космический персонаж, переходите на состояние «чтение буквы» и так далее.
Теперь, когда мы устанавливаем, что нам нужна идея «государства», мы можем написать код, который выглядит что-то подобное:
low_str = ""
high_str = ""
letter = ""
password = ""
state = "low"
for char in entry:
print(f"State: {state}, {char}")
if state == "low":
if char in "0123456789":
low_str += char
elif char == "-":
state = "high"
elif state == "high":
if char in "0123456789":
high_str += char
elif char == " ":
state = "letter"
elif state == "letter":
if char in "abcdefghijklmnopqrstuvwxyz":
letter += char
elif char == ":":
state = "password"
elif state == "password":
if char in "abcdefghijklmnopqrstuvwxyz":
password += char
print(f"Low: {low_str}, High: {high_str}, Letter: {letter}, Password: {password}")
Выход
State: low, 9 State: low, - State: high, 1 State: high, 2 State: high, State: letter, t State: letter, : State: password, State: password, t State: password, t State: password, f State: password, j State: password, v State: password, v State: password, t State: password, g State: password, x State: password, t State: password, c State: password, t State: password, r State: password, n State: password, t State: password, n State: password, h State: password, t State: password, t State: password, Low: 9, High: 12, Letter: t, Password: ttfjvvtgxtctrntnhtt
Немного глоток. Но это важная конструкция – «государственная машина». Государственные машины чрезвычайно важны в программном обеспечении, так как их можно использовать в качестве строительных блоков сложного поведения на основе набора правил. Они используются во всем, из какого режима светодиодная панель находится на вашей микроволновке, для управления поведением роботов, чтобы декодировать данные, поступающие на ваш WiFi прямо сейчас (неудивительно, просто как мы декодируем эту строку упражнения проверки паролем с помощью Государственная машина, вы также можете декодировать сетевые протоколы с чем-то похожим).
Приводящий к станке
Государственные машины настолько важны, что я не собираюсь двигаться на Regex. Код выше раздражает и справляется, чтобы написать, мы можем немного починить его.
Во-первых, эти большие константы могут быть удалены, поскольку собственный Python Строка
if char in "abcdefghijklmnopqrstuvwxyz":
Может стать:
if char in string.ascii_lowercase:
(а также string.digits )
Во-вторых, этот код annyign для поддержания того, что эти номера проверки и правила сочетаются друг с другом в довольно плотном битовом коде. Мы можем лучше держать его в чистоте и использовать кучу удобных функций для повторного использования:
def is_number(char):
return char in string.digits
def is_letter(char):
return char in string.ascii_lowercase
def is_separator(char):
return char in " -:"
Мы также можем добавить некоторые функции, чтобы помочь добавить буквы на наше low_str. и High_str Переменные:
low_str = ""
high_str = ""
def ingest_low(char):
low_str += char
def ingest_high(char):
high_str += char
Но это не отличная практика, чтобы сделать это точно так, потому что low_str Как уже определено, на самом деле являются глобальными переменными, которые мутируются внутри этих функций. Это плохая форма (целая тема сама). Мы должны придерживаться всего вышеперечисленного в классе, чтобы держать вещи в капсулировании:
class PasswordParser:
def __init__(self):
self.low_str = ""
self.high_str = ""
self.letter = ""
self.password = ""
def ingest_low(self, char):
self.low_str += char
def ingest_high(self, char):
self.high_str += char
def ingest_letter(self, char):
self.letter += char
def ingest_password(self, char):
self.password += char
def is_number(self, char):
return char in string.digits
def is_letter(self, char):
return char in string.ascii_lowercase
def is_separator(self, char):
return char in " :-"
@property
def low(self):
return int(self.low_str) if self.low_str else 0
@property
def high(self):
return int(self.high_str) if self.high_str else 0
Уведомление в конце там, я добавил несколько титров в качестве удобства, чтобы преобразовать эти строки в INT для удобства.
Государственный машинный код теперь может выглядеть так:
parser = PasswordParser()
state = "low"
for char in entry:
print(f"State: {state}, {char}")
if state == "low":
if parser.is_number(char):
parser.ingest_low(char)
elif parser.is_separator(char):
state = "high"
elif state == "high":
if parser.is_number(char):
parser.ingest_high(char)
elif parser.is_separator(char):
state = "letter"
elif state == "letter":
if parser.is_letter(char):
parser.ingest_letter(char)
elif parser.is_separator(char):
state = "password"
elif state == "password":
if parser.is_letter(char):
parser.ingest_password(char)
print(f"Low: {parser.low}, High: {parser.high}, Letter: {parser.letter}, Password: {parser.password}")
Если честно, это не целый лоток или более читабельный, мы вроде на полпути через приводящие его. Обратите внимание, как каждое состояние содержит два Если Проверки, которые решают, привлекать ли данные, а еще один, чтобы решить, следует ли переключать состояние.
Поэтому мы можем обобщить это и построить наш собственный класс статемахин, в который мы можем зарегистрировать функцию проверки, а также функцию перехода для каждого состояния, а не нужно, чтобы выписать целую кучу Если заявления.
Это «решенная проблема»
Вот вещь. Возвращаясь к тому, что я сказал последнее сообщение, в то время как весело и воспитание для написания кода, многие проблемы, которые мы сталкиваемся в реальном мире, не новы, и, вероятно, есть библиотеки, которые уже существуют, чтобы решить проблему. Штатные машины определенно являются «решенной проблемой». Они используются везде!
В экосистеме библиотек Python есть хороший под названием Переходы (которые я использовал в моей робототехнике). переходы (Как предполагает, что имя) позволяет определить ваши штатные машины более декларационально с точки зрения переходов между государствами, правила, регулирующие эти переходы, и триггеры, которые вызывают возникновение этих переходов.
Быть декларативным означает, что вы можете подумать о государственных машинах с точки зрения этих государств и переходов и правил, а не в Nitty Gritty для реализации.
Вот что вышеуказанный код выглядит когда реализован с использованием Переходы :
from transitions import Machine
parser = PasswordParser()
machine = Machine(parser, ["low", "high", "letter", "password"], initial="low")
machine.add_transition("consume", "low", "low", conditions=["is_number"], after=["ingest_low"])
machine.add_transition("consume", "low", "high", conditions=["is_separator"])
machine.add_transition("consume", "high", "high", conditions=["is_number"], after=["ingest_high"])
machine.add_transition("consume", "high", "letter", conditions=["is_separator"])
machine.add_transition("consume", "letter", "letter", conditions=["is_letter"], after=["ingest_letter"])
machine.add_transition("consume", "letter", "password", conditions=["is_separator"])
machine.add_transition("consume", "password", "password", conditions=["is_letter"], after=["ingest_password"])
Как видно, вместо того, чтобы быть состоит из целой кучкой маленького Если С заявлениями, штат-машина в настоящее время состоит из семи правил перехода.
machine.add_transition("consume", "low", "low", conditions=["is_number"], after=["ingest_low"])
Возьмите эту строку например. Это определяет правило перехода из «низкого» состояния обратно в «низкое» состояние, если условие является «Is_Number». Это необходимо, потому что, когда мы находимся в «низком» состоянии, получение ряда должно держать нас в этом состоянии, так как нам может потребоваться искать другой номер. Этот код также указывает, что «ingest_low» – это функция для запуска (с входящими данными) после того, как этот переход произойдет, эта функция помогает собрать наши номера вместе. Первый аргумент «потребляющий» – это триггер, который приводит к тому, что это правило перехода для попытки запустить.
Если бы мы были нарисовать диаграмму с переходной экономикой для вышесказанного, она будет выглядеть что-то подобное:
Со всей установкой фактическое выполнение состояния простую:
for char in entry:
print(f"State: {parser.state}, {char}")
parser.consume(char)
print(f"Low: {parser.low}, High: {parser.high}, Letter: {parser.letter}, Password: {parser.password}")
Я не буду воспроизводить вывод, так как он идентичен в прошлом времени.
Для каждого персонажа мы говорим, что штат-машина выстрелить «потреблять» триггер, который на самом деле для этой машины вызывает все переходы (независимо от того, будет ли фактический переход, зависит от состояний и правил перехода). Внутренне машина пройдет через аналогичный набор логики к тому, что мы определили раньше, но нам не нужно было написать один Если персонаж, и код немного очищен, поскольку он объявляет Что «нужно сделать, а не« как »его необходимо сделать (отличительной чертой« декларативного программирования »)
Так что мы идем. Анализатор на основе автомата. Как так же весело, как государственные машины, они, однако, являются полностью чрезмерными для этой проблемы, поскольку Regeex решает все это очень быстро. Я пойду на это решение в моем следующем посте.
Advent of Code 2020 (26 части серии)
Оригинал: “https://dev.to/meseta/advent-of-code-day-02-a-59m0”