## DEV Community is a community of 601,801 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Discussion on: Advent of Code 2020 Solution Megathread - Day 7: Handy Haversacks

Yuan Gao • Edited

I pull out that PEG parser again to handle my input, I feel it's more readable than a full regex solution, since you define the entire syntax of the input file up-front for everyone to see. But it's not as compact as a pure regex solution, and there's a lot of extra nodes (could probably golf it, but it would be less readable). One benefit is the NodeVisitor is already doing a depth-first visit of the generated AST, so you can piggy back the graph generation in there to save a loop or two.

I used the NetworkX graph library in Python to get the `ancestors` for free, but unfortunately still had to write a recursive traversal of the DAG to get the sums for Part 2.

Made some nice graphs while I was at it too, more on my post

``````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:

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):
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