This is a fairly common and standard task in programming puzzles. All you need is a stack 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.
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))
Part 1: 462693
When 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, and the Python statistics module 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.
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))
Part 2: 3094671161