Day 10 Stacks all the way down

This one is about matching parenthesis, which means that anyone writing in closure is likely to be able to do this one just by instinct!

Ok, we need to match parenthesis in 4 different types.

The golden rule here is actually pretty simple, there's a kind of state machine, in which each character on a line should only be one of 4 options, (, {, [, < and then the closing parenthesis of whatever type we last opened. So when we see a (, the closing type is ).

But when we do see the closing type, we need to get the next previous one that we saw.

This is a stack, like a stack of plates in a canteen. If you put something on the top of the stack, then when you take it off, whatever was there before is revealed.

Python doesn't have a stack data type itself, what it does is provide a set of methods on a list that mean you can treat it as a stack. Generally a stack has 4 main methods, push, pop, peek, empty?. These map in pythin to append, pop, [-1] and the comparison to [].

That combined with the 3.10 match statement should make processing a line pretty simple.

Read each character, if it's an open parenthesis, push the matching close onto the stack. If it's a close, compare it to whats on the stack, if it doesn't match, stop processing and return the character that broke for scoring. If it does match, pop that item off the stack and keep going

## Import ipytest and get it setup for use in Python Notebook
import pytest
import ipytest
ipytest.autoconfig()

(2024 update) - pushing this to a static file generator, all the curly parenthesis break the liquid pre-processing of markdown, so we're putting this block here to tell it to stop processesing...

legal_chunks = ["([])", "{()()()}", "<([{}])>", "[<>({}){}[([])<>]]", "(((((((((())))))))))"]
corrupted_chunks = [
    ("(]","]"), 
    ("{()()()>", ">"), 
    ("(((()))}","}"), 
    ("<([]){()}[{}])",")")]

def process_chunks(line):
    stack = []
    for c in line:
        match c:
            case "(": 
                stack.append(")")
            case "[":
                stack.append("]")
            case "{":
                stack.append("}")
            case "<":
                stack.append(">")
            case m:
                if stack == []:
                    return False,m
                elif stack[-1] != m:
                    return False,m
                else:
                    assert m == stack.pop()
    return True,""

for chunk in legal_chunks:
    assert (True,"") == process_chunks(chunk)
for chunk,expected in corrupted_chunks:
    assert (False,expected) == process_chunks(chunk)

So that works... let's try it on some of the example lines

test_lines = """[({(<(())[]>[[{[]{<()<>>
[(()[<>])]({[<{<<[]>>(
{([(<{}[<>[]}>{[]{[(<()>
(((({<>}<{<{<>}{[]{[]{}
[[<[([]))<([[{}[[()]]]
[{[{({}]{}}([{[{{{}}([]
{<[[]]>}<{[{[{[]{()[[[]
[<(<(<(<{}))><([]([]()
<{([([[(<>()){}]>(<<{{
<{([{{}}[<[[[<>{}]]]>[]]""".split("\n")

results = [process_chunks(line) for line in test_lines]
scores = {')':3, ']':57, '}':1197, '>': 25137}
total = sum(map(lambda c: scores[c], [result[1] for result in results if not result[0]]))
assert total == 26397

The total there is calculated by looking through the results, getting all the corrupted lines and then finding the error, and mapping that to a score.

lines = [line.strip() for line in open('day10.txt').readlines()]
results = [process_chunks(line) for line in lines]
scores = {')':3, ']':57, '}':1197, '>': 25137}
total = sum(map(lambda c: scores[c], [result[1] for result in results if not result[0]]))
print(total)

344193

Part 2

Ok, unusually for us, part 2 has itself two main parts. The first is that we need to essentially return the stack. Those are the letters, in order, that can close all of the open lines. In our case that part is pretty simple.

The second issue however is the unneccesarily complex scoring mechanism. We'll write a function to take a stack and turn it into a score, and the change in our main code is simply to return the stack when we get to the end of teh line.

Note: the stack is a list, in reverse order. Since we want to process each item, isntead of popping them, we cna simply reverse the list and then iterate over them.

def score_autocomplete(completion):
    scoretable = {')':1, ']':2, '}':3, '>':4}
    score = 0
    for letter in completion:
        score = score * 5
        score += scoretable[letter]
    return score

assert 288957 == score_autocomplete("}}]])})]")
assert 5566 == score_autocomplete(")}>]})")
assert 1480781 == score_autocomplete("}}>}>))))")
assert 995444 == score_autocomplete("]]}}]}]}>")
assert 294 == score_autocomplete("])}>")

Let's confirm that the changes to the process_chunks can return teh right stacks

def process_chunks(line):
    stack = []
    for c in line:
        match c:
            case "(": 
                stack.append(")")
            case "[":
                stack.append("]")
            case "{":
                stack.append("}")
            case "<":
                stack.append(">")
            case m:
                if stack == []:
                    return False,m
                elif stack[-1] != m:
                    return False,m
                else:
                    assert m == stack.pop()
    return True,"".join(reversed(stack))

results = [process_chunks(line) for line in test_lines]
expected = ["}}]])})]", ")}>]})", "}}>}>))))", "]]}}]}]}>", "])}>"]
assert expected == [result[1] for result in results if result[0]]

Ok, final thing, we don't want the actual score, we want the middle number from the scores once sorted. With a given list of scores, given the constraint that there will always be an odd number of items, the midpoint should be at (len(list)-1)//2.

scores = sorted(map(score_autocomplete, [result[1] for result in results if result[0]]))
assert 288957 == scores[(len(scores)-1)//2]

Let's try that on prod data then

lines = [line.strip() for line in open('day10.txt').readlines()]
results = [process_chunks(line) for line in lines]
scores = sorted(map(score_autocomplete, [result[1] for result in results if result[0]]))
print(scores[(len(scores)-1)//2])

3241238967

(2024 update)