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
fromparsimonious.grammarimportGrammar,NodeVisitorimportnetworkxasnxgrammar=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"(, |(?=\.))"
""")classBagVisitor(NodeVisitor):defparse(self,*args,**kwargs):self.graph=nx.DiGraph()super().parse(*args,**kwargs)returnself.graphdefvisit_ENTRY(self,node,visited_children):parent,children,*_=visited_childrenforcount,childinchildren:self.graph.add_edge(parent,child,count=count)defvisit_PARENT(self,node,visited_children):returnvisited_children[0]defvisit_CHILD(self,node,visited_children):return(visited_children[0],visited_children[2])defvisit_COLOR(self,node,visited_children):self.graph.add_node(node.text)returnnode.textdefvisit_NUMBER(self,node,visited_children):returnint(node.text)defgeneric_visit(self,node,visited_children):returnvisited_childrenornodebv=BagVisitor()bv.grammar=grammargraph=bv.parse(open("input.txt").read())# Part 1
print("ancestor bags",len(nx.ancestors(graph,"shiny gold")))# Part 2
defget_count(parent):return1+sum(get_count(child)*graph.edges[parent,child]["count"]forchildingraph.neighbors(parent))print("total bags",get_count("shiny gold")-1)
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
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