Advent of Code 2021 - Day 10: Syntax Scoring

This year’s Advent of Code has some very nice puzzles so far and brings some joy into this somehow dark Covid-Prechristmas time.

Day 10: Syntax Scoring

Link: Day 10

Our input contains of lines containing numerous chunks, which consist of an opening bracket ((,[,{,<) and the matching closing bracket (),],},>). While a valid chunck may contain other chunks (or none), chunks are not allowed to overlap. (()), ([]) and (<><>[()]) are examples for valid chunks, ([)] or ((([)))]] are considered illegal.

Part 1

For the first star we have detect the lines which are corrupted. The score for each illegal line is determined by the first illegal character: ) scores 3 points, ] 57 points, }: 1197 points and a > is worth 25137 points.

Solution

The problem becomes easy when using a stack to keep track of the chunks. Since a stack is LIFO, the first chunk to close is always on top. The algorithm simply parses the input and puts an opening symbol on top the stack. If a closing character is read, it has to match the symbol on top of the stack, otherwise the line is illegal. Example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

Input: [[(])]


|
v
[[(])] => [ is put on stack: [

 |
 v
[[(])] => [ is put on stack: [[

  |
  v
[[(])] => ( is put on stack: [[(

   | 
   v
[[(])] => ] a closing symbol 
            => get top element of stack 
            => ( and ] are not a matching pair, the line is ILLEGAL

Part 2

1
2
3
4
5
6
7
8

Now, given the same instructions, find the position of the first character that causes him to enter the basement (floor -1). 
The first character in the instructions has position 1, the second character has position 2, and so on.

For example:

) causes him to enter the basement at character position 1.
()()) causes him to enter the basement at character position 5.
What is the position of the character that causes Santa to first enter the basement?

Now we have to find the first time Santa reaches the basement (level -1) . Using the list of part 1, we can compute the floor Santa reaches at each step using the partial sums, which itertools.accumulate accomplishes.

1
2
3
4
5

 # part1 & 2
    nP = [1 if c=="(" else -1 for c in lines[0]]
    aP = list(accumulate(nP))
    part1 = aP[-1]
    part2 = aP.index(-1)+1

As the last entry of the accumulated sums equals the total sum of the list, the sum(np) can be omitted.