Bracket matching - Advent of Code 2021 Day 10

Question

The following code solves Advent Of Code 2021 Day 10.

The goal for this time around is evaluating whether a line of brackets is complete, has a syntax error or is missing some closing brackets.

Examples of valid pairs of brackets

()
[] 
([])
{()()()}
<([{}])>
[<>({}){}[([])<>]]
(((((((((())))))))))

Example of incorrect or corrupted lines

{([(<{}[<>[]}>{[]{[(<()>   # Expected ], but found } instead.
[[<[([]))<([[{}[[()]]]     # Expected ], but found ) instead.
[{[{({}]{}}([{[{{{}}([]    # Expected ), but found ] instead.
[<(<(<(<{}))><([]([]()     # Expected >, but found ) instead.
<{([([[(<>()){}]>(<<{{     # Expected ], but found > instead.

Examples of incomplete lines

[({(<(())[]>[[{[]{<()<>>    # Complete by adding }}]])})].
[(()[<>])]({[<{<<[]>>(      # Complete by adding )}>]}).
(((({<>}<{<{<>}{[]{[]{}     # Complete by adding }}>}>)))).
{<[[]]>}<{[{[{[]{()[[[]     # Complete by adding ]]}}]}]}>.
<{([{{}}[<[[[<>{}]]]>[]]    # Complete by adding ])}>.

Problem:

Advent of code 10 was divided into two problems:

1. Find the sum of all lines that has a syntax error (corrupted), where every bracket that causes a syntax error is given a particular value.
2. Find each line that was incomplete, complete the line and find the autocomplete score of the completed portion. For every line in the test data, we were then asked to find the median of the autocomplete scores.

Code

from typing import Final

# Points for each illegal character
points: Final[dict[str, int]] = {
    ')': 3,
    ']': 57,
    '}': 1197,
    '>': 25137
}

# Bracket pairs
pairs: Final[dict[str, int]] = {
    '(': ')',
    '[': ']',
    '{': '}',
    '<': '>'
}

# Values for scoring completion characters
values: Final[dict[str, int]] = {
    ')': 1,
    ']': 2,
    '}': 3,
    '>': 4
}

def syntax_error_score_and_autocomplete_score(lines):
    scores = []
    total_score = 0

    for line in lines:
        stack = []
        corrupted = False
        corrupted_char = None
        for char in line.strip():
            if char in pairs:
                # Opening bracket
                stack.append(char)
            else:
                # Closing bracket
                if not stack:
                    # Extra closing bracket, corrupted
                    corrupted = True
                    corrupted_char = char
                    break
                top = stack.pop()
                if pairs[top] != char:
                    # Mismatched closing bracket, corrupted
                    corrupted = True
                    corrupted_char = char
                    break

        # Ignore corrupted lines
        # If the line is corrupted, add the corresponding points
        if corrupted:
            total_score += points[corrupted_char]
            continue

        # If stack is not empty, we need to complete the line
        if stack:
            completion_string = ""
            while stack:
                opening = stack.pop()
                completion_string += pairs[opening]

            # Calculate score for this completion string
            score = 0
            for ch in completion_string:
                score = score * 5 + values[ch]
            scores.append(score)

    print("part1: (syntax_error_score)", total_score)
    scores.sort()
    # Get the middle score
    print("part2: (autocomplete_score)", scores[len(scores)//2])


if __name__ == "__main__":
    with open("D:\\ExplorerDownload\\input2021_day10.txt", "r") as f:
        lines = f.readlines()
    syntax_error_score_and_autocomplete_score(lines)

Answer 1

Looks good. It is easy to read, with clear identifiers.

extra boolean

This is some nice, idiomatic code.

        corrupted_char = None

Given the type of str | None, we don't need a bool corrupted flag alongside it. Testing if the char is None does the same job as seeing if the flag is False. Fewer state variables means fewer things to keep juggling in your head. On which topic...

extract helper

We strive to write short functions which can be viewed in a single screenful, without vertical scrolling.

That for char ... loop performs a nice localized computation and is a good candidate for packaging up in a helper function. Pass in a line and a stack, side effect the stack, and get back a corrupted_char.

odd annotation

We don't tend to often see Final in annotated production code.

pairs: Final[dict[str, int]] = {

Quoting from its documentation:

A final name cannot be re-assigned or overridden in a subclass. ...

There is no runtime checking of these properties.

Consider instead using from types import MappingProxyType and assign one of those. Type checkers know all about it, plus its cousins such as frozenset. Runtime mutation attempts will produce TypeError: 'mappingproxy' object does not support item assignment

In the simpler scalar case, rather than marking it Final we typically will upcase such constants, e.g. SECONDS_PER_DAY = 86400. And yes, linters will call you out if they see you trying to increment such a quantity.

And do run pyright or mypy over your code after you've annotated it. That dict[str, int] copy-pasta mapping makes no sense. You wanted dict[str, str]. Bad annotations are noticed by type checkers, but have no effect at runtime.

extra comments

This source code is perhaps a little on the chatty side, but not overly so, not so much that it worries me. Do consider deleting the occasional comment if you feel it says nothing more than what the code already has eloquently stated. Your descriptive identifiers are a big help in that regard.

This was the only comment item that gave me pause:

            if char in pairs:
                # Opening bracket
                stack.append(char)

It makes me slightly sad, because ideally an identifier like pairs should be doing the work of explaining that. Yet I couldn't think of a better name than pairs, sorry. Maybe def is_opening_bracket(char): is the best way out of this?

median

... we were then asked to find the median of the autocomplete scores.

    print("part2: (autocomplete_score)", scores[len(scores)//2])

I didn't notice anything in your problem statement which promises there shall be an odd number of scores. In the even case I would expect a median computation to find the mean of the two central figures. Notice that if there's a bunch of repeated scores this code might "get lucky", as the mean of two equal numbers is identical to the value of either one of them. But with enough test inputs your luck will eventually run out.

Answer 2

In addition to the points raised in the previous answer, here are some other items to consider.

Naming

User @J_H makes an astute point that you only need to retain one of these variables:

corrupted
corrupted_char

However,if you do decide to keep both, I recommend renaming corrupted as is_corrupted. Adding the is_ prefix is a common practice for booleans, and it would more clearly distinguish the 2 variables by name.

Comments

My first impression while reading through the code was that the function had well-placed comments that helped me understand what was going on.

Magic number

It is not obvious to me what the significance of the 5 is in the following line:

            score = score * 5 + values[ch]

Perhaps a comment would help to clarify.

Which leads us to ...

Documentation

I understand that the focus for programming challenges is functionality, and the last thing your are thinking about is documentation, but adding some simple docstrings would help to understand the purpose of the code.