Syntax Scoring - Advent of Code 2021 Day 10

 

Meiji Jingu

Today's coding problem is based in part on a common coding problem that requires us to determine if there are syntactic errors. Here is a link to the full problem - https://adventofcode.com/2021/day/10

Understanding the problem

The input to the problem consists of several lines of curly , curved and angle brackets. Each corresponding open bracket requires a corresponding close bracket or else it is considered a syntactic error. The first step of the problem involves discovering all these incorrect brackets and submitting a total score based on a value assigned to each of these brackets.

Not all lines of the input are considered errors and there are some lines that are incomplete and don't have enough closing brackets. For the second part of the problem we are supposed to derive the closing brackets and then use a scoring system to determine another total score. The is the solution to the second part of the problem

Solving it

The entire source code of the solution can be found here - 

https://github.com/jasoncoelho/adventOfCode2021/blob/main/10/run.py

First Part

For the first part of the problem, I used a stack to store all the open brackets encountered. When a closed bracket was encountered, it was compared against the top of the stack. If they formed the correct pair they could be discarded. If they did not form the correct pair, the incorrect bracket was factored into the score

The relevant part of the code is shown below

    for closingChunkChar in list(line):

        if closingChunkChar in closingChunkChars:
            stackTop = stack.pop()
            expectedStartingChunkChar = closingChunkChars[closingChunkChar]
            if stackTop != expectedStartingChunkChar:
                # print("Found ",closingChunkChar, "Expected closing char for ",stackTop)
                syntaxErrorScore += closingChunkCharPoints[closingChunkChar]
                syntaxErrorLine = True
                break
        else:
            stack.append(closingChunkChar)

Second Part

Since we already have a stack containing all the open brackets and have ascertained that the line is syntactically incomplete (and not an error), we can now derive all the closing brackets by going through the remaining elements in the stack. We can then use the scoring system to calculate a score which is the solution to the second part of the problem -

    if len(stack) > 0 and not syntaxErrorLine :
        totalScore = 0
        while len(stack) > 0:
            stackTop = stack.pop()
            closingChunkChar = closingChunkCharsInverse[stackTop]
            totalScore = (totalScore * 5) + incompleteLinePoints[closingChunkChar]    
        totalScores.append(totalScore)