AoC 2017 Day 9: Garbage Gobbler

Source: Stream Processing

Part 1: An input stream can contain:

  • groups are delimited by { and }, groups are nestable and may contain garbage or data (objects within a group are comma delimited)
  • garbage is delimited by < and >, groups cannot be nested within garbage, a ! within garbage is an escape character: !> does not end a garbage segment

The score of a single group is equal to how many times it is nested (the innermost group of {{{}}} has score 3).

The score of a stream is the sum of the scores of all groups in that stream.

What is the total score of your input?

Since the groups can be nested, they can’t1 be parsed with regular expressions. The language is relatively simple enough that we could directly write a text=&ldquo;parser&rdquo; page=&ldquo;Parsing#Computer_languages&rdquo; (keeping a stack of how deep we are currently nested in groups), but this sounds like a wonderful excuse to use the PyParsing module:

First, we want to define garbage, since it cannot have anything nested in it. Garbage works essentially like a string:

garbage = pp.Suppress(pp.QuotedString('<', escChar = '!', endQuoteChar='>'))

And then groups can contain either nested groups, garbage, or data:

group = pp.Forward()
data = pp.Regex(r'[^}]+')

group << pp.Group(
    pp.Suppress('{')
    + pp.Optional(pp.delimitedList(group | garbage | data))
    + pp.Suppress('}')
)

We have to use Forward since groups can be nested within themselves.

With those definitions, we can put together a parsing function:

def parse(stream):
    '''Implement a pyparsing parser for the stream format.'''

    group = pp.Forward()
    garbage = pp.Suppress(pp.QuotedString('<', escChar = '!', endQuoteChar='>'))
    data = pp.Regex(r'[^}]+')

    group << pp.Group(
        pp.Suppress('{')
        + pp.Optional(pp.delimitedList(group | garbage | data))
        + pp.Suppress('}')
    )

    parser = (group | garbage)

    data = parser.parseString(stream)
    if data:
        return data[0]

Now that we can parse the data, we can score it recursively:

def score_groups(data, depth = 1):
    '''
    The score of a group is equal to its depth.
    The score of data is equal to the sum of its groups.
    '''

    if isinstance(data, pp.ParseResults):
        data = data.asList()

    if isinstance(data, list):
        return depth + sum(score_groups(el, depth + 1) for el in data)
    else:
        return 0

total_score = 0

for line in lib.input():
    data = parse(line)
    total_score += score_groups(data)

print(total_score)

It’s a bit complicated since PyParsing returns a custom object from the parser, but we can turn it to a list with asList.

Part 2: How many non-escaped garbage characters are there in your input?

This got more exciting than I expected since PyParsing.QuotedString doesn’t contain the escape characters, so we don’t actually know how many characters were escaped. That’s not at all what we want. So we have to write a custom parsing function. Since garbage cannot be nested, we can use regular expressions. To keep a count, I’m just going to use a global variable. So sue me. 😄

_last_garbage_count = 0

def parse(stream):
    '''Implement a pyparsing parser for the stream format.'''

    global _last_garbage_count
    _last_garbage_count = 0

    group = pp.Forward()
    garbage = pp.Suppress(pp.Regex(r'<([^!>]|!.)*>').setParseAction(count_garbage))
    data = pp.Regex(r'[^}]+')

    group << pp.Group(
        pp.Suppress('{')
        + pp.Optional(pp.delimitedList(group | garbage | data))
        + pp.Suppress('}')
    )

    parser = (group | garbage)
    data = parser.parseString(stream)
    if data:
        return data[0]

total_score = 0
total_garbage = 0

for line in lib.input():
    data = parse(line)

    count = count_groups(data)
    score = score_groups(data)
    total_score += score

    total_garbage += _last_garbage_count

print('score: {}, garbage: {}'.format(total_score, total_garbage))

It’s a big ugly (with the global variable), but so it goes.

$ python3 run-all.py day-09

day-09  python3 garbage-gobbler.py input.txt    0.5247189998626709      score: 16021, garbage: 7685

  1. Well… shouldn’t. If you know ahead of time how deep the groups are going to be nested in practice, it’s possible. Ugly. But possible. ↩︎