코드 2020의 출현: 07일째 Python PEG 문법 사용 +NetworkX

40200 단어 datasciencepythonadventofcode
또한PEG 문법으로 해석할 수 있는 기회가 생겼습니다. 이번에는 제가 이전에 사용하지 않았던 새로운 라이브러리인 NetworkX, 강력한 Python 도형 라이브러리 (데이터 구조 클래스, 그림 클래스가 아닌 데이터 구조 클래스) 를 깊이 연구할 수 있는 기회를 갖게 되어 기쁩니다.
본고에서 언급한 내용은 표현식 문법(PEG), 도론, 유방향 무환도(DAG), NetworkX 라이브러리, 도표, 귀속 함수 해석

1부 도전


Link to challenge on Advent of Code 2020 website
직면한 도전은 사실상 하나의 나무/그림 범람 문제이다.색상 패키지에 포함할 수 있는 다른 색상 패키지를 정의하는 일련의 규칙을 볼 수 있습니다.
예를 들어, 두 규칙을 예로 들면 다음과 같습니다.
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 해석기에 적합한 것 같습니다.노드 접근자가 있는 PEG 파서를 사용하면 각 노드를 분석할 때 이를 처리하여 한두 개의 순환을 절약할 수 있다.여느 때와 마찬가지로, 나는 파이톤의 parsimonious 라이브러리를 사용할 것이다.from parsimonious.grammar import Grammar를 사용하여 가져오기
PEG 구문을 한 번에 하나씩 구성해 봅시다.우선 이 항목을 고려해 봅시다.
bright gray bags contain 2 bright gold bags, 5 dull lavender bags.
상위 섹션: bright gray bags contain 및 하위 섹션: 2 bright gold bags, 5 dull lavender bags 다음에 행 끝에 있는 문자, 마침표 및 선택적 줄 바꿈(문서의 마지막 행에 줄 바꿈 문자가 없으므로 선택 사항) 두 섹션으로 나눕니다.
상위 부품은 쉽게 정의할 수 있지만 다음과 같습니다.
  • 항상 두 단어의 색깔
  • "짐 포함"(모든 공간 포함
    • 이 방면의 연계는 상대적으로 간단하다
    from parsimonious.grammar import Grammar
grammar = Grammar(r"""
    PARETN    = COLOR " bags contain "
    COLOR     = ~r"\w+ \w+"
""")
    테스트:
    print(grammar.parse("""bright gray bags contain """))
    출력
    <Node called "PARENT" matching "bright gray bags contain ">
    <RegexNode called "COLOR" matching "bright gray">
    <Node matching " bags contain ">
    하위 부품은 다음과 같이 하나 이상의 하위 부품으로 구성될 수 있습니다.
  • 숫자
    • 로 시작
  • 공간
  • 항상 두 단어의 색깔
  • 공간
  • 단수bag 또는 복수bags
  • 또는 , 또는 글의 끝에 있으면 다음 문자가 .인 것을 알 수 있습니다.
    • 따라서 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"(, |(?=\.))"
""")
    나는 구분자로 이상한 일을 했다. 나는 그것을 하라고 했다. (, |(?=\.)). ",, 아니면 앞으로 . 문자를 보든지, 포착하지 마라."라는 뜻이다.우리는 항목의 끝과 일치하는 구분자 . 문자를 포착하고 싶지 않다.이것은 정규 표현식에서'적극적인 전망'이 일치한다고 불린다.나는 PEG가 그것을 쓰지 않고 작성할 수 있다고 생각하지만, 나는 그것을 사용하여 일을 전체적으로 좀 더 간단하게 하기로 선택했다
    우리
    하나의 예에서 이 점을 테스트하다.
    print(grammar.parse("""bright gray bags contain 2 bright gold bags, 5 dull lavender bags."""))
    출력
    <Node called "ENTRY" matching "bright gray bags contain 2 bright gold bags, 5 dull lavender bags.">
    <Node called "PARENT" matching "bright gray bags contain ">
        <RegexNode called "COLOR" matching "bright gray">
        <Node matching " bags contain ">
    <Node called "CHILDREN" matching "2 bright gold bags, 5 dull lavender bags">
        <Node called "CHILD" matching "2 bright gold bags, ">
            <RegexNode called "NUMBER" matching "2">
            <Node matching " ">
            <RegexNode called "COLOR" matching "bright gold">
            <Node matching " ">
            <Node called "BAGBAGS" matching "bags">
                <Node matching "bags">
            <RegexNode called "SEPARATOR" matching ", ">
        <Node called "CHILD" matching "5 dull lavender bags">
            <RegexNode called "NUMBER" matching "5">
            <Node matching " ">
            <RegexNode called "COLOR" matching "dull lavender">
            <Node matching " ">
            <Node called "BAGBAGS" matching "bags">
                <Node matching "bags">
            <RegexNode called "SEPARATOR" matching "">
    <Node matching ".">
    <Node matching "">
    많은 텍스트처럼 보이지만 대부분 무시된다.만약 우리가 실제로 어떤 일도 하지 않을 선을 제거한다면, 그것은 이렇게 될 것이다.
    <Node called "ENTRY">
    <Node called "PARENT">
        <RegexNode called "COLOR" matching "bright gray">
    <Node called "CHILDREN">
        <Node called "CHILD">
            <RegexNode called "NUMBER" matching "2">
            <RegexNode called "COLOR" matching "bright gold">
        <Node called "CHILD">
            <RegexNode called "NUMBER" matching "5">
            <RegexNode called "COLOR" matching "dull lavender">
    이것은 우리가 실제로 사용하는 데이터에 더욱 가깝다.
    우리가 주의해야 할 또 다른 일은, 우리가 짐을 휴대하는 것을 허락하지 않는 특수한 상황이 하나 더 있다는 것이다
    bright orange bags contain 5 dim bronze bags.
    이를 위해 우리는 터미널의 특례를 추가하고 윗부분을 1로 끌어올려 한 줄을 입구나 터미널로 허용할 것이다
        LINE      = (ENTRY / TERMINAL)

    TERMINAL  = PARENT "no other bags." "\n"?
    ENTRY     = PARENT CHILDREN "." "\n"?
    마지막으로 각 항목을 각각 PEG 파서에 입력했던 이전과 달리 이번에는 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"(, |(?=\.))"
""")
    이제 데이터를 분석할 수 있습니다.parsimonious의 NodeVisitor를 사용하여 해석된 문법 트리를 옮겨다니며 필요한 정보를 수집할 것입니다.나는 이미 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
    visit_COLOR() 방법은 아마도 우리 해석기의 핵심일 것이다. 그의 작업은 색 노드를 처리하고 일치하는 것을 추출하여 상위 노드로 되돌려주는 것이다. 이는 부 노드와 하위 노드를 포함하고 상위 노드로 다시 상류로 전달하는 것이다.우리가 도착했을 때 visit_ENTRY(), 우리는 이미 학부모와 아이들에게 양식이 좋은 색깔 값을 제공했다.
    위에서 print()statemetn을 visit_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를 사용할 것이다.이것은 import networkx as 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는 같은 이름을 사용하려고 하면 추가 노드를 만들지 않기 때문에 우리의 생활이 간단해진다. 노드가 존재하는지 확인할 필요가 없기 때문이다.NodeVisitor에 적절한 위치add_node()와 함수add_edge()를 추가하여 Network X 그림을 구문 분석할 때 출력합니다.
    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)
    출력

    응, 분명히 이것은 나무가 아니라 도표야.따라서 노드 간에 명확한 부자 관계가 있기 때문에 도형 유형을 유방향 그림으로 전환해야 한다.이것은 간단하게 nx.Graph()에서 nx.DiGraph()로 전환할 수 있다. 우리의 가장자리는 이미 정확한 방향을 가리키고 있다.이로 인해 우리의 도표는 가장자리에 작은 화살표가 있어 관계의 방향을 가리킨다.

    잠깐만, 이거 안 좋아. 우리 그것에 색칠을 좀 하자.

    이렇게 하는 것이 더 좋다.이것은 여전히 문제에서 제시한 예시 데이터이며, 나는 1초 안에 완전한 도표를 그릴 것이다.

    도형 분석


    이 부분의 문제는 기본적으로'한shiny gold 가방에 몇 명의 부모/조부모/조상이 있느냐?'로 귀결될 수 있다.
    이를 위해서는 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)
    출력

    자, 이제 진실한 데이터로 이 일을 하자.

    시각화는 물론이고 그레이핑len(ancestors)이 이 문제에 대한 답을 내놓았다.

    도전의 두 번째


    두 번째 부분은 또 다른 반복적인 문제지만 이번에는 다른 봉투에 넣을 수 있는 봉투의 수량을 곱해서 가능한 봉투의 수량을 효과적으로 계산해야 한다. 만약에 봉투마다 최대 수량의 어린이 봉투가 포함된다면 말이다.
    흥미로운 것은, 이것은 그림에 순환이 없다는 것을 알려준다. 왜냐하면, 이 숫자는 무한하기 때문이다.다시 말하면 이 유방향도는 비순환도이다.데이터와 CI 파이프를 처리하는 사람들이 그것에 익숙해질 수 있는 방향무환도 (DAG)
    따라서 가장자리가 있는 점수를 저장하기 위해 먼저 해상도를 업데이트해야 한다.EMC 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을 줄여야 한다. 왜냐하면 문제는 몇 개의 가방 shiny gold 을 포함해야 하기 때문이다.이것이 주는 답은 원하는 답안에 도전하는 것이다.
    예제 데이터의 모서리와 해당 번호의 시각적 표시는 다음과 같습니다.

    나도 실제 데이터를 위해 이런 가시화를 만들었지만 할 일이 너무 많고 볼 것이 많지 않았다.완전한 데이터를 실행하고 출력get_count("shiny gold") - 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)
    앞으로!
    numpy matrix 매트릭스 대상
    Next.js에서 사용자 지정 404 페이지 만들기

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage