Рубрики
Без рубрики

Advent of Code 2020: день 07 с использованием грамматики Python PEG + NetworkX

Еще одна возможность вытащить эту грамматику PEG для анализа, на этот раз я рад иметь возможность … Tagged с появлением кода, Python, Data Science.

Advent of Code 2020 (26 серии деталей)

Еще одна возможность вытащить эту грамматику PEG для анализа, на этот раз я рад иметь возможность покопаться в новой библиотеке, которую я раньше не использовал, Networkx, мощная библиотека графиков (вид данных, а не на рисунок) для Python.

Вещи, упомянутые в этом посте: Грамматики экспрессии (PEG), теория графика, направленные ациклические графики (DAGS), библиотека NetworkX, Graph Traversal, рекурсивные функции

Ссылка на вызов на веб -сайте Advent of Code 2020

Представленная задача – на самом деле проблема обхода дерева/графика. Вам представлены большой набор «правил», которые определяют, что «цветная» сумка может содержать то, что еще «цветные» сумки.

Например, возьмите два примера правила:

light red bags contain 1 bright white bag, 2 muted yellow bags.
bright white bags contain 1 shiny gold bag.

По сути, это означает, что «светло -красный» является родителем «ярко -белого» и родителем «приглушенного желтого». А во второй строке «Ярко -белый» – родитель «блестящего золота». Объединяя эти два правила вместе, мы можем сказать, что «светло -красный» – это бабушка и дедушка «блестящее золото»

Схематически, как дерево:

Light Red
|
|--Bright White
|  |
|  |--Shiny Gold
|
|--Muted Yellow

На этом этапе неясно, могут ли эти отношения образовать петлю – например, приглушенный желтый цвет может содержать светло -красный. Если это так, то эта проблема меняется с дерева на направленный график, поскольку отношения только в одну сторону (предвещающие предвещание). Мы узнаем позже только после того, как загрузим все правила и подробно рассмотрим их.

Вход в диапазон

Поскольку ввод поступает в виде хорошоформатированного текста с линиями с переменной шириной, это кажется идеальным подходящим для анализатора ПЭГ, как описано в день 04. Использование анализатора PEG с посетителем узла также позволяет нам обрабатывать каждый узел по мере его анализа, сохраняя одну или две петли. Как обычно, я буду использовать экономный Библиотека для Python. Импорт его с от экономного импорта Грамматика

Давайте построим грамматику PEG по одной части за раз. Сначала давайте рассмотрим эту запись:

bright gray bags contain 2 bright gold bags, 5 dull lavender bags.

Давайте разделим это на две части, родительская часть: Яркие серые сумки содержат А потом детская часть: 2 ярких золотых мешка, 5 тупых лавандовых мешков А потом все, что находится в конце линии, период и дополнительный символ Newline (это необязательно, потому что в последней строке в документе ее нет)

Родительская часть легко определить, это просто:

  • цвет, который всегда два слова
  • «Сумки содержат» (со всеми пробелами

Колыбец только для этого относительно просто

from parsimonious.grammar import Grammar
grammar = Grammar(r"""
    PARETN    = COLOR " bags contain "
    COLOR     = ~r"\w+ \w+"
""")

Тестирование:

print(grammar.parse("""bright gray bags contain """))

Выход

Дети часть состоит из одной или нескольких детей, которая может выглядеть как:

  • начинается с номера
  • пространство
  • цвет, который всегда два слова
  • пространство
  • Либо сумка единственный или сумки множественное число
  • Либо , или если В конце отрывка мы знаем, что следующий персонаж будет Анкет

Таким образом, мы можем соответствующим образом построить нашу грамматику PEG:

grammar = Grammar(r"""
    ENTRY     = PARENT CHILDREN "." "\n"?
    PARENT    = COLOR " bags contain "
    CHILDREN  = CHILD+
    CHILD     = NUMBER " " COLOR " " BAGBAGS SEPARATOR

    NUMBER    = ~r"\d+"
    COLOR     = ~r"\w+ \w+"
    BAGBAGS   = ("bags" / "bag")
    SEPARATOR = ~r"(, |(?=\.))"
""")

Я сделал немного странной вещи с сепаратором, я попросил его сделать (, |(?=\.)) что означает «либо , или смотреть на . персонаж Но не поймайте это ». Мы не хотим захватывать Анкет персонаж для сепаратора, потому что он нуждается там, чтобы соответствовать конец записи. Это известно как «позитивный матч» в режиме. Я думаю, что колышка может быть написан без него, но я решил использовать это, чтобы все было немного проще I

Тестирование этого на примере:

print(grammar.parse("""bright gray bags contain 2 bright gold bags, 5 dull lavender bags."""))

Выход

Хотя это выглядит как много текста, большая часть его будет игнорирована. Если мы удалим линии, с которыми мы на самом деле ничего не сделаем, это будет выглядеть так:

Это ближе к данным, которые мы на самом деле будем использовать.

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

bright orange bags contain 5 dim bronze bags.

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

    LINE      = (ENTRY / TERMINAL)

    TERMINAL  = PARENT "no other bags." "\n"?
    ENTRY     = PARENT CHILDREN "." "\n"?

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

grammar = Grammar(r"""
    DOCUMENT  = LINE+
    LINE      = (ENTRY / TERMINAL)

    TERMINAL  = PARENT "no other bags." "\n"?
    ENTRY     = PARENT CHILDREN "." "\n"?

    PARENT    = COLOR " bags contain "
    CHILDREN  = CHILD+
    CHILD     = NUMBER " " COLOR " " BAGBAGS SEPARATOR

    NUMBER    = ~r"\d+"
    COLOR     = ~r"\w+ \w+"
    BAGBAGS   = ("bags" / "bag")
    SEPARATOR = ~r"(, |(?=\.))"
""")

Теперь, когда мы сможем анализировать данные, мы будем использовать Nodevisitor Parsimonious для прохождения нашего проанализированного синтаксического дерева, чтобы собрать необходимую информацию. Я объяснил некоторые из этого уже в день 04, так что не слишком много в этом не займет. Код:

class BagVisitor(NodeVisitor):
    def visit_ENTRY(self, node, visited_children):
        parent, children, *_ = visited_children
        print("Entry", parent, "=>", children)

    def visit_PARENT(self, node, visited_children):
        return visited_children[0]

    def visit_CHILD(self, node, visited_children):
        return visited_children[2]

    def visit_COLOR(self, node, visited_children):
        return node.text

    def generic_visit(self, node, visited_children):
        return visited_children or node

bv = BagVisitor()
bv.grammar = grammar

VIST_COLOR () Метод, вероятно, является ядром нашего анализатора, его задача состоит в том, чтобы справиться с цветовым узлом, вытащить матч и вернуть его вверх в поднятые узлы, которые включают в себя родитель и ребенка, которые затем проходят его вверх по течению. К тому времени, когда мы доберемся до Vite_Entry () У нас хорошо форматированные значения цвета для родителей и детей.

Вышеупомянутое ставит print () Стейттин внутри Vite_Entry () , чтобы мы могли успешно проанализировать каждую запись. Запуск примера данных:

bv.parse("""light red bags contain 1 bright white bag, 2 muted yellow bags.
dark orange bags contain 3 bright white bags, 4 muted yellow bags.
bright white bags contain 1 shiny gold bag.
muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.
shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.
dark olive bags contain 3 faded blue bags, 4 dotted black bags.
vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.
faded blue bags contain no other bags.
dotted black bags contain no other bags.""")

Выход

Entry light red => ['bright white', 'muted yellow']
Entry dark orange => ['bright white', 'muted yellow']
Entry bright white => ['shiny gold']
Entry muted yellow => ['shiny gold', 'faded blue']
Entry shiny gold => ['dark olive', 'vibrant plum']
Entry dark olive => ['faded blue', 'dotted black']
Entry vibrant plum => ['faded blue', 'dotted black']

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

Построение графика

Чтобы создать график, мы будем использовать чрезвычайно мощный пакет сетевого анализа Networkx Анкет Это установлено и импортируется с Импорт NetworkX как nx Анкет

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

graph = nx.Graph()
graph.add_node("A")
graph.add_node("B")
graph.add_edge("A", "B")
nx.draw(graph, with_labels=True)

Выход:

Networkx достаточно умна, чтобы не создавать дополнительные узлы, если мы пытаемся использовать одно и то же имя, это делает нашу жизнь простым, поскольку нам не нужно проверять, существуют ли узлы. Добавляем add_node () и add_edge () Функции для нашего Nodevisitor в нужных местах, и он выводит график Networkx, когда он анализирует:

class BagVisitor(NodeVisitor):
    def parse(self, *args, **kwargs):
        self.graph = nx.Graph()
        super().parse(*args, **kwargs)
        return self.graph

    def visit_ENTRY(self, node, visited_children):
        parent, children, *_ = visited_children
        for child in children:
            self.graph.add_edge(parent, child)

    def visit_PARENT(self, node, visited_children):
        return visited_children[0]

    def visit_CHILD(self, node, visited_children):
        return visited_children[2]

    def visit_COLOR(self, node, visited_children):
        self.graph.add_node(node.text)
        return node.text

    def generic_visit(self, node, visited_children):
        return visited_children or node

bv = BagVisitor()
bv.grammar = grammar

Этот код теперь анализирует и возвращает график, который можно проанализировать! Использование:

graph = bv.parse(input)

Давайте нарисуем график, который выходит, когда мы используем демонстрационные данные, является вводом:

pos = nx.nx_agraph.graphviz_layout(graph)
nx.draw(graph, pos=pos, with_labels=True)

Выход

Welp, ясно, что это график, а не дерево. Таким образом, нам нужно переключить тип графа на направленные графики, поскольку у нас есть четкая связь между родителями и детьми между узлами (родительская сумка содержит отношения с детской сумкой). Это может просто сделать путем переключения нкс Graph () к нкс Digraph () Наши края уже все указывают в правильном направлении. Это заставляет нашу диаграмму получать маленькие стрелки на краях, указывающих направление отношений.

Держись, это не хорошо, давай дадим ему несколько цветов.

Так-то лучше. Помните, что это все еще пример данных, приведенных в вопросе, я буду графин нашего полного графика в секунде.

Анализ графика

Эта часть вопроса в основном сводится к «сколько родителей/бабушек и дедушек/предков там к блестящему золоту сумка?

Чтобы найти это, мы буквально просто просим Networkx дать нам наш список предков:

ancestors = list(nx.ancestors(graph, "shiny gold"))

Выход

['bright white', 'light red', 'dark orange', 'muted yellow']

Что мы здесь делаем, если мы не собираемся получить фантазию с цветами?

colors = []
for item in graph.nodes.keys():
    if item == "shiny gold":
        colors.append( "gold")
    elif item in ancestors:
        colors.append("chartreuse")
    else:
        colors.append("violet")
pos = nx.nx_agraph.graphviz_layout(graph)
nx.draw(graph, pos=pos, node_color=colors, edge_color="grey", with_labels=True)

Выход

Хорошо, давайте сделаем это по -настоящему сейчас, с нашими реальными данными:

Визуализации в стороне, захват Лен (предки) дает наш ответ на вопрос.

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

Интересно, что это говорит нам о том, что в графике нет петлей, потому что если бы они были, число было бы бесконечным. Другими словами, этот направленный график является ациклическим; Направленный ациклический график (DAG), с которым те из вас, работающие с данными и трубопроводами CI, могут быть знакомы.

Поэтому сначала нам нужно обновить наш аналогичный анализатор, чтобы сохранить эти оценки с краями. Нашим Nodevisitor становится:

class BagVisitor(NodeVisitor):
    def parse(self, *args, **kwargs):
        self.graph = nx.DiGraph()
        super().parse(*args, **kwargs)
        return self.graph

    def visit_ENTRY(self, node, visited_children):
        parent, children, *_ = visited_children
        for count, child in children:
            self.graph.add_edge(parent, child, count=count)

    def visit_PARENT(self, node, visited_children):
        return visited_children[0]

    def visit_CHILD(self, node, visited_children):
        return (visited_children[0], visited_children[2])

    def visit_COLOR(self, node, visited_children):
        self.graph.add_node(node.text)
        return node.text

    def visit_NUMBER(self, node, visited_children):
        return int(node.text)

    def generic_visit(self, node, visited_children):
        return visited_children or node

Теперь за сложную часть. Поскольку в то время как мы знаем, сколько мешков находится внутри любой сумки, мы не знаем, сколько мешков находится внутри этих мешков, пока не пойдем. Мы должны рекурсивно открывать сумки до конца, где есть мешки, не содержащие других мешков, чтобы умножить общее количество мешков. Мы должны написать рекурсивную функцию обхода (оказывается, оказалась первой глубиной). К сожалению, у Networxx нет никаких инструментов, которые просто дадут нам ответ, поэтому мы должны написать нашу собственную рекурсивную обход с умножением счета:

def get_count(parent):
    count = 0
    for child in graph.neighbors(parent):
        count += get_count(child) * graph.edges[parent, child]["count"]
    return 1 + count

Другими словами: за каждую сумку заведите своих детей и для каждого ребенка, умножьте, сколько из этих детских мешков у него есть с тем, сколько еще мешков внутри каждого ребенка. Также не забудьте добавить один для самой оригинальной сумки.

Это может немного подать код:

def get_count(parent):
    return 1 + sum(get_count(child) * graph.edges[parent, child]["count"] for child in graph.neighbors(parent))

get_count("shiny gold") - 1

Мы должны вычесть 1 в конце, потому что вопрос хочет, сколько мешков блестящее золото Содержит, не считая себя. Ответ, который дает, – это ответ, который хочет.

Визуализация края с их числами на примере данных:

Я также произвел эту визуализацию для реальных данных, но было так много всего, что это не так много взглянуть. Запуск полных данных и вывод значения get_count ("блестящее золото") - 1 Получает результат, разыскиваемый в этой части сегодняшнего вызова.

Полный код для всех частей этой задачи:

from parsimonious.grammar import Grammar, NodeVisitor
import networkx as nx

grammar = Grammar(r"""
    DOCUMENT  = LINE+
    LINE      = (ENTRY / TERMINAL)

    TERMINAL  = PARENT "no other bags." "\n"?
    ENTRY     = PARENT CHILDREN "." "\n"?

    PARENT    = COLOR " bags contain "
    CHILDREN  = CHILD+
    CHILD     = NUMBER " " COLOR " " BAGBAGS SEPARATOR

    NUMBER    = ~r"\d+"
    COLOR     = ~r"\w+ \w+"
    BAGBAGS   = ("bags" / "bag")
    SEPARATOR = ~r"(, |(?=\.))"
""")

class BagVisitor(NodeVisitor):
    def parse(self, *args, **kwargs):
        self.graph = nx.DiGraph()
        super().parse(*args, **kwargs)
        return self.graph

    def visit_ENTRY(self, node, visited_children):
        parent, children, *_ = visited_children
        for count, child in children:
            self.graph.add_edge(parent, child, count=count)

    def visit_PARENT(self, node, visited_children):
        return visited_children[0]

    def visit_CHILD(self, node, visited_children):
        return (visited_children[0], visited_children[2])

    def visit_COLOR(self, node, visited_children):
        self.graph.add_node(node.text)
        return node.text

    def visit_NUMBER(self, node, visited_children):
        return int(node.text)

    def generic_visit(self, node, visited_children):
        return visited_children or node

bv = BagVisitor()
bv.grammar = grammar

graph = bv.parse(open("input.txt").read())

# Part 1
print("ancestor bags", len(nx.ancestors(graph, "shiny gold")))

# Part 2
def get_count(parent):
    return 1 + sum(get_count(child) * graph.edges[parent, child]["count"] for child in graph.neighbors(parent))

print("total bags", get_count("shiny gold")-1)

Впереди!

Advent of Code 2020 (26 серии деталей)

Оригинал: “https://dev.to/meseta/advent-of-code-day-07-peg-networkx-in-python-16hg”

Читайте ещё по теме: