advent_of_code_2021

day10_part2.py (2841B)

---

 #!/usr/bin/env python
 """Advent of Code 2021, day 10 (part 2): Syntax Scoring
 For part 2, we are completing the 'incomplete' lines and finding the score
 associated with their completion."""
 
 from typing import List
 from day10_part1 import (EXAMPLE_INPUT,
                          convert_input_to_list,
                          is_open_bracket,
                          match_bracket)
 from utils import get_puzzle_input
 
 def score_bracket(bracket: str) -> int:
     """Given a close bracket, return its associated score"""
     return {')': 1, ']': 2, '}': 3, '>': 4}[bracket]
 
 def score_line(line: str) -> int:
     """Return the 'score' of an incomplete line, or 0 for lines that are not
     incomplete or are corrupt"""
     # The problem description text implies that a line must be incomplete or
     # corrupt, but I don't trust that's true (it's not explicit enough for me);
     # I'm going to return a score of 0 for any line that is neither incomplete
     # nor corrupt (even though there are none in the example input and probably
     # none in my puzzle input). Just using a loop and stack again.
     bracket_stack: List[str] = []
     line_score: int = 0
     # line_score = line_score * 5 + score_bracket(bracket)
     for bracket in line:
         if is_open_bracket(bracket):
             bracket_stack.append(bracket)
         else:
             if match_bracket(bracket_stack.pop()) != bracket:
                 # This is a corrupt line, return 0
                 return 0
 
     # Figure out which brackets are necessary to clear the stack and score the
     # line. This could be implemented with a list comprehension to run more
     # quickly, but I find this conceptually simpler. Also note that this will
     # return 0 if the stack is empty, indicating a (putative) complete and
     # non-corrupt line.
     while bracket_stack:
         line_score = line_score * 5 + \
             score_bracket(match_bracket(bracket_stack.pop()))
 
     return line_score
 
 def filter_zeros(scores: List[int]) -> List[int]:
     """Remove zeros from the list of scores"""
     return [s for s in scores if s != 0]
 
 def middle_score(scores: List[int]) -> int:
     """Sort and return the middle item of the list"""
     # I could use `median` from numpy, but since the puzzle prompt promises an
     # odd number of lines, it's easy to implement ourselves
     return sorted(scores)[len(scores)//2]
 
 def solve_puzzle(input_string: str) -> int:
     """Return the numeric solution to the puzzle"""
     return middle_score(
         filter_zeros([score_line(l) for l in convert_input_to_list(input_string)])
     )
 
 def main() -> None:
     """Run when the file is called as a script"""
     assert solve_puzzle(EXAMPLE_INPUT) == 288957
     print("Middle score of incomplete lines:",
           solve_puzzle(get_puzzle_input(10)))
 
 if __name__ == "__main__":
     main()