day10_part2.py (2841B)

1 #!/usr/bin/env python 2 """Advent of Code 2021, day 10 (part 2): Syntax Scoring 3 For part 2, we are completing the 'incomplete' lines and finding the score 4 associated with their completion.""" 5 6 from typing import List 7 from day10_part1 import (EXAMPLE_INPUT, 8 convert_input_to_list, 9 is_open_bracket, 10 match_bracket) 11 from utils import get_puzzle_input 12 13 def score_bracket(bracket: str) -> int: 14 """Given a close bracket, return its associated score""" 15 return {')': 1, ']': 2, '}': 3, '>': 4}[bracket] 16 17 def score_line(line: str) -> int: 18 """Return the 'score' of an incomplete line, or 0 for lines that are not 19 incomplete or are corrupt""" 20 # The problem description text implies that a line must be incomplete or 21 # corrupt, but I don't trust that's true (it's not explicit enough for me); 22 # I'm going to return a score of 0 for any line that is neither incomplete 23 # nor corrupt (even though there are none in the example input and probably 24 # none in my puzzle input). Just using a loop and stack again. 25 bracket_stack: List[str] = [] 26 line_score: int = 0 27 # line_score = line_score * 5 + score_bracket(bracket) 28 for bracket in line: 29 if is_open_bracket(bracket): 30 bracket_stack.append(bracket) 31 else: 32 if match_bracket(bracket_stack.pop()) != bracket: 33 # This is a corrupt line, return 0 34 return 0 35 36 # Figure out which brackets are necessary to clear the stack and score the 37 # line. This could be implemented with a list comprehension to run more 38 # quickly, but I find this conceptually simpler. Also note that this will 39 # return 0 if the stack is empty, indicating a (putative) complete and 40 # non-corrupt line. 41 while bracket_stack: 42 line_score = line_score * 5 + \ 43 score_bracket(match_bracket(bracket_stack.pop())) 44 45 return line_score 46 47 def filter_zeros(scores: List[int]) -> List[int]: 48 """Remove zeros from the list of scores""" 49 return [s for s in scores if s != 0] 50 51 def middle_score(scores: List[int]) -> int: 52 """Sort and return the middle item of the list""" 53 # I could use `median` from numpy, but since the puzzle prompt promises an 54 # odd number of lines, it's easy to implement ourselves 55 return sorted(scores)[len(scores)//2] 56 57 def solve_puzzle(input_string: str) -> int: 58 """Return the numeric solution to the puzzle""" 59 return middle_score( 60 filter_zeros([score_line(l) for l in convert_input_to_list(input_string)]) 61 ) 62 63 def main() -> None: 64 """Run when the file is called as a script""" 65 assert solve_puzzle(EXAMPLE_INPUT) == 288957 66 print("Middle score of incomplete lines:", 67 solve_puzzle(get_puzzle_input(10))) 68 69 if __name__ == "__main__": 70 main()