advent_of_code_2021

My attempts to work through the 2021 Advent of Code problems.
git clone https://git.eamoncaddigan.net/advent_of_code_2021.git
Log | Files | Refs | README | LICENSE

commit 6d614d6d159f60c4698556c9f413e417973c07a1
parent 605b631b1e31767e3772224d11f14bb18c91aedd
Author: Eamon Caddigan <eamon.caddigan@gmail.com>
Date:   Fri, 10 Dec 2021 11:00:44 -0500

Soution to day 10, part 2

Diffstat:
Aday10_part2.py | 69+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 69 insertions(+), 0 deletions(-)

diff --git a/day10_part2.py b/day10_part2.py @@ -0,0 +1,69 @@ +#!/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 day10_part1 import (EXAMPLE_INPUT, + convert_input_to_list, + is_open_bracket, + match_bracket) +from utils import get_puzzle_input + +def score_bracket(bracket): + """Given a close bracket, return its associated score""" + return {')': 1, ']': 2, '}': 3, '>': 4}[bracket] + +def score_line(line): + """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 = [] + line_score = 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): + """Remove zeros from the list of scores""" + return [s for s in scores if s != 0] + +def middle_score(scores): + """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): + """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(): + """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()