DEV Community

loading...

Discussion on: Advent of Code 2020 Solution Megathread - Day 18: Operation Order

Collapse
meseta profile image
Yuan Gao

It's a syntax parsing problem, right? So we just use PEG to parse it like we would any programming language. This takes away the heavy lifting of implementing parsing of individual characters, and let the library deal with all the recursion and traversal, leaving us to just provide methods which get called to evaluate the nodes of the AST as it traverses. The result is some clean and compact high-level code:

from parsimonious.grammar import Grammar, NodeVisitor
import math

grammar = Grammar(r"""
    OPERATION = EXPR (OP EXPR)+
    EXPR = (NUMBER / BRACKETS)
    BRACKETS = "(" OPERATION ")"
    OP = " " ("+" / "*") " "
    NUMBER    = ~r"\d"
""")

class ExprVisitor(NodeVisitor):
    def visit_OPERATION(self, node, visited_children):
        parts = [visited_children[0]]
        for op, value in visited_children[1]:
            if op == "+":
                parts[-1] += value
            if op == "*":
                parts.append(value)
        return math.prod(parts)

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

    def visit_BRACKETS(self, node, visited_children):
        return visited_children[1]

    def visit_OP(self, node, visited_children):
        return visited_children[1][0].text

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

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

ev = ExprVisitor()
ev.grammar = grammar
print("sum", sum(ev.parse(line.strip()) for line in open("input.txt").readlines()))
Enter fullscreen mode Exit fullscreen mode