Day 9 (TV)

Okay this one looks substantially more difficult than the previous one. It seems that we have a very long string of characters. We're looking for groups which are denoted by an open and close brace ({ & }). The contents of a group are comma separated groups or garbage which is denoted by a less than and greater than sign. Anything between a < and > is treated as part of the garbage, even another brace or <. There are also cancelled characters within the garbage where a ! kills off the following character. There is a scoring system which I guess we'll get into later. For now, let's start by loading up the input and take a stab at it.

In [1]:
import pandas as pd
import numpy as np
import re

initial = open('/Users/Sven/py_files/aoc_2017/d9_input.txt')
initial = initial.read()
initial[:25]
Out[1]:
'{{{{{}},{{{{<a!!!!!>!!u!!'

So... the first thing I think we should do is just try and delete all the cancelled pieces as they will just get in the way later on. I'm not super confident in the regular expressions with python so let's just do a little test here:

In [2]:
test = 'aa!d!!!dFF!!!!d!'
print(test)
re.sub(r'!.', 'X', test)

aa!d!!!dFF!!!!d!
Out[2]:
'aaXXXFFXXd!'

Okay, that's what I was hoping would happen. So the puzzle says that htese cancelled cells should only appear within garbage and that doesn't count for the scoring so I think we should be able to just delete them all:

In [3]:
stream = re.sub(r'!.', '', initial)
initial[:50]
Out[3]:
'{{{{{}},{{{{<a!!!!!>!!u!!}!!\',eo!!u">}},{<!!!!!!!>'
In [4]:
stream[:50]
Out[4]:
'{{{{{}},{{{{<au}\',eou">}},{<},<aeui>},{{<,"},<<},<'

Seems to be working. Next I want to try and just reduce the garbage down... So I bet the second part of this day will require you to figure out something involving checksums of garbage but whatever, we can just reload it.

In [5]:
stream = re.sub(r'<[^>]*>', '', stream)
stream[:50]
Out[5]:
'{{{{{}},{{{{}},{},{{,{}},{}}},{{{{{}}},{}}},{{,{}}'

Okay so... we got this cleaned up a bit. Now I think it would be helpful to split these into fully contained groups. So I think we will have a fully contained group where the rolling count of open and close braces are equal. We can use this to chop up the string:

In [6]:
stream_chopped = stream
stream_pieces = []
while len(stream_chopped) > 0:
    # Store counts of left, right, and index for the loop
    l = r = i = 0
    for c in stream_chopped:
        # check if it matches either brace
        if c == '{':
            l += 1
        elif c == '}':
            r += 1
        i += 1    
        # if we've met equilibrium, stop
        if r == l:
            print('whipeee')
            # append list and chop
            stream_pieces.append(stream_chopped[:i])
            stream_chopped = stream_chopped[i:]
            break        
        

whipeee
whipeee

Okay I guess that was completely pointless as it's all one big bag. Now comes the hard part... this reminds me of that catalan numbers thing I vaguely learned in school but it doesn't relate to the number of possible ways to write parentheses. Maybe it's to that hard... I think I can just think of this kind of algorithm which feels like you're stepping up and down layers into a pit:

Start at level = 0

  • If we encounter a { : level += 1
  • If we encounter a , : skip to next
  • If we encounter a } : total += level, level -= 1
In [7]:
total = 0
level = 0
for c in stream:
    if c == '{':
        level += 1
    elif c == '}':
        total += level
        level -= 1
    else:
        next
total
Out[7]:
9251

Part 2

Now we're asked to count the lengths of all the non-cancelled garbage in the original. In retrospect, I didn't really need to remove the garbage from the input. I think we can just go back to here:

In [8]:
stream = re.sub(r'!.', '', initial)

Now we'll do something sorta similar... this seems a lot easier:

In [9]:
garb_tot = 0
flipper = 0
for c in stream:
    if c == '<' and flipper == 0:
        flipper = 1
    elif c == '>' and flipper == 1:
        flipper = 0
    elif flipper == 1:
        garb_tot += 1
    else:
        next
garb_tot
Out[9]:
4322

Yeah... seems like part 2 has been easier for many of these puzzles which is not what I would have expected.