<jupyter_start><jupyter_text>Bracket matching* This is a fairly common and standard task in programming puzzles. All you need is a [stack](https://en.wikipedia.org/wiki/Stack_%28abstract_data_type%29) to track what brackets have been opened, and match any closing character against the top of the stack. If the top of the stack doesn't match up, you have a syntax error. If you reach the end of the line without mis-matched brackets, there were no syntax errors.My implementation uses a dictionary to match opening pairs to closing pairs; either a character is a key in this dictionary (an opening character) and goes to the top of the stack, or the top of the stack, used as a key into the dictionary gives us the matching paired closing bracket. If it doesn't match, we now to return a score.My implementation also returns the stack, as I suspect we'll need that for part two.<jupyter_code>from __future__ import annotations
from collections import deque
from typing import Final


PAIRED: Final[dict[str, int]] = {"(": ")", "[": "]", "{": "}", "<": ">"}
SYNTAX_ERROR_SCORES: Final[dict[str, int]] = {")": 3, "]": 57, "}": 1197, ">": 25137}


def match_brackets(line: str) -> tuple[int, deque[str]]:
    stack = deque()
    for char in line:
        if char in PAIRED:
            stack.append(char)
        elif PAIRED[stack.pop()] != char:
            return SYNTAX_ERROR_SCORES[char], stack
    return 0, stack


test_nav_subsystem = """\
[({(<(())[]>[[{[]{<()<>>
[(()[<>])]({[<{<<[]>>(
{([(<{}[<>[]}>{[]{[(<()>
(((({<>}<{<{<>}{[]{[]{}
[[<[([]))<([[{}[[()]]]
[{[{({}]{}}([{[{{{}}([]
{<[[]]>}<{[{[{[]{()[[[]
[<(<(<(<{}))><([]([]()
<{([([[(<>()){}]>(<<{{
<{([{{}}[<[[[<>{}]]]>[]]
""".splitlines()

assert sum(match_brackets(line)[0] for line in test_nav_subsystem) == 26397

import aocd

nav_subsystem = aocd.get_data(day=10, year=2021).splitlines()
print("Part 1:", sum(match_brackets(line)[0] for line in nav_subsystem))<jupyter_output>Part 1: 462693<jupyter_text>Part 2, completing the lineWhen there are no mismatched pairs, but there are still items left on the stack, we know that there are closing brackets missing. Just continue to pop elements from the stack, they are the opening brackets for incomplete pairs, and these can be mapped straight onto the base-5 scoring system.We've seen the 'middle value' before, on [day 7], when in part 1 we had to optimise the crab fuel expenditure. It's called the [median](https://en.wikipedia.org/wiki/Median), and the [Python `statistics` module](https://docs.python.org/3/library/statistics.htmlstatistics.median) has us covered (the module even includes `median_low()` and `median_high()` functions for when there isn't a convenient odd number of values).Just make sure to filter out the syntax-error lines first.<jupyter_code>from statistics import median


AUTOCOMPLETION_SCORES: Final[dict[str, int]] = {"(": 1, "[": 2, "{": 3, "<": 4}


def autocompletion_score(line: str) -> int:
    syntax_error, stack = match_brackets(line)
    if syntax_error:
        return 0
    score = 0
    while stack:
        score *= 5
        score += AUTOCOMPLETION_SCORES[stack.pop()]
    return score


def median_score(lines: list[str]) -> int:
    return median(filter(None, map(autocompletion_score, lines)))


assert list(filter(None, map(autocompletion_score, test_nav_subsystem))) == [
    288957,
    5566,
    1480781,
    995444,
    294,
]
assert median_score(test_nav_subsystem) == 288957

print("Part 2:", median_score(nav_subsystem))<jupyter_output>Part 2: 3094671161
{'fraction_non_alphanumeric': 0.1629293216009083, 'fraction_numerical': 0.026681805279591256, 'mean_word_length': 4.786535303776683, 'pattern_counts': {'":': 12, '<': 39, '<?xml version=': 0, '>': 29, 'https://': 3, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '452331', 'license': 'MIT', 'n_tokens_mistral': 1233, 'n_tokens_neox': 1114, 'n_words': 379, 'path': '2021/Day 10.ipynb', 'repo_name': 'AwesomeGitHubRepos/adventofcode', 'size': '3523'}