The following code solves day 10 in the advent of code challenge.
The goal for this time around is evaluating whether a line of brackets is complete, has a syntax error or is missing some closing brackets.
Examples of valid pair of brackets
() [] ([]) {()()()} <([{}])> [<>({}){}[([])<>]] (((((((((()))))))))) Example of incorrect or corrupted lines
{([(<{}[<>[]}>{[]{[(<()> - Expected ], but found } instead. [[<[([]))<([[{}[[()]]] - Expected ], but found ) instead. [{[{({}]{}}([{[{{{}}([] - Expected ), but found ] instead. [<(<(<(<{}))><([]([]() - Expected >, but found ) instead. <{([([[(<>()){}]>(<<{{ - Expected ], but found > instead. Examples of incomplete lines
[({(<(())[]>[[{[]{<()<>> - Complete by adding }}]])})]. [(()[<>])]({[<{<<[]>>( - Complete by adding )}>]}). (((({<>}<{<{<>}{[]{[]{} - Complete by adding }}>}>)))). {<[[]]>}<{[{[{[]{()[[[] - Complete by adding ]]}}]}]}>. <{([{{}}[<[[[<>{}]]]>[]] - Complete by adding ])}>. Problem:
Advent of code 10 was divided into two problems
- Find the sum of all lines that has a syntax error (
corruped), where every bracket that causes a syntax error is given a particular value - Here we had to find each line that was
incomplete, complete the line, find the autocomplete score of the completed portion. For every line in the testdata we were then asked to find the median of the autocomplete scores.
Code
AOC_10_brackets.txt The testdata can be found here, but if the link is dead the data has been included below
{[[<{(<{[{{[{[[]{}]{<>{}}}({<>()}{{}{}})]}{({[<>{}]({}[])})[{[{}[]](()<>)}<[{}{}]{()<>}>]}}]<(({{{(){}}{[][] <<<({((<{<([([<>{}]<{}<>>]{<{}<>>({}<>)}])>}{({(([()[]]{[]()})({{}<>}<(){}>))[(<<><>>[()[]]){{()[]}< <<<[(({{(([[[[<><>][<><>]]]([[{}{}](<><>)][(<>[]){[]()}])])([[(<{}<>>(()[]))(<[][]>)]]{{<[[]{}]{< ({({([{{[[[{(<(){}><[]{}>)}]]][(<<([()[]](()[]))>[[[{}[]]{[]<>}](<()>[()<>]]]>(<(({}<>){<>[]}){<[]()>}>{[{( [([{(<[<<[({<[()<>][{}]>({{}{}})}({[<>{}][()()]}[([][]){()[]}]))]>>]>)<<[((([[{{()()}(<>{})}[(<>( {[[{<[[[[([[{[()[]]<[]()>}<({}())<[]<>>>]({<{}[]>}<<{}<>>>)](([(<>{}){[][]}]<[(){}]({}{})>)[((()){[]})<{{} {{<<((({(<[({<<>[]><{}{}>}((<>[])([]())))[((()[]){[]{}})]]{<([{}[]]<<>[]>)(({}[]}{[][]})><<([][])([][])>>} ([[(<({[[{[{<[<><>]({}())>}](<[[{}[]](<><>)]{{()<>}[{}]}>{((<><>]<()()>)([(){}]<()>)})}{[<{({}())<<><>>}[(() (<((([[<<[<[{[()[]][[]{}]}{([]<>){[]{}}}]>]>>{{([[({<>()}(<>{}))]<{(()<>)([])}([<>{}}{{}()})> (<({{<(<{[{<{[(){}][<>{}]}{[[][]]{<>{}}}>}<(([[][]][<>()])[[{}{}][{}()]])>]}>{{{([<(()())> (<[{<<(<<<((<[<>[]]>)({[[]<>]}<({}<>)([][])>))[{<[[]()](<>())>{<[]<>><{}()>}}(<<{}<>>(<>[] <[[(((([[(<[{((){})<{}<>>}{({}<>><{}<>>}]([{<>()}([]<>)]<{()()}({}[])>)>)]{{({([{}<>])(<<>() <({<(<{[{<<[[[{}[]][()[]]](<()()><()>)]>>[(((([]<>){(){}})<{{}()}({}())>)[<[[]()]{<>[]}><[()[]][<>()]>])[(<<< ([[[{(<<<([[[<<>[]>]]{<([]<>){[]{}}><<[]>({}<>)>}]<(<<{}<>>([])><{<>[]}<{}<>>>)([{[]()}<<> <({<<(<{(<<(({[]<>}{{}{}})(<<>[]><<>[]>))(<<<><>><[]{}>>{[()[]][()[]]})>>){{<{([{}()]{<>()}){<[][]>({}<>)}} (([{{(<[([([([[]()]({}))<<[][]><{}()>>][[[{}<>][<>{}]]]){[{[[][]]<{}{}>}<<()<>>(<>())>]}])<{{[(({})<[]()>){[< {(<<[<{<<{(([[()<>]{<>[]}]{[{}{}]{<>()}})<([[][]]{[]<>}){(()<>)<[]<>>}>)[[{{[]}}]]}<{{((<>)<{}>){ <{<{<{{[<{{<<<<>[]>{()[]}>><[<<>()>{{}[]}]<[{}]{[]()}>>}}>[[{(((<>{}]({}()))<<{}()>[[]()]>)}]{{({[<>() <[[<<([{([{{[[()()]<{}<>>][{{}()}<()()>]}({([]<>)<<>[]>}{[[][]][()[]]})}[((<{}{}><()[]>){<<>()>((){} <<{([[{[<{[<([()()]{()<>}>[<[]<>>[[]<>]]>{{[{}{}][()<>]}<[[]{}][{}{}]>}]<((({}<>)<<><>>){{<><>}[()<>]})> [[[[[{({((([<[<>{}]<{}()>>[<{}[]>[[]{}]]]{{{()<>}<{}[]>>([()()]{{}()})})))}[{{[({<{}[]>}<[[]()]>)( {[[<[([{((<[<[{}[]][<><>]>({{}{}}[{}{}])]{{({}{}){{}[]}><[{}[]]([]())>}>[{<{()<>}([]())>}]))(<[([[()][[][]] [(({[((<{<{<<[[]<>]<{}[]>>>{[<[]{}>[[]{}]]{((){})<[]>}}}<<<{{}{}}<<>()>>{<<>[]>([]{})}>>>}{[{{{<[]()>(()<>)}< {[[[{<([{[<{([<>()]{<>[])){<<><>>([]<>)}}<{[(){}]<()<>>}>>([[<()<>>((){})]][<<[]{}><()()>>(<[ [{(<{[({[{[{{(<>{})({}{})}<(<>[])>}([<()<>>[()<>]]{(()<>)<{}()>})]{([{{}{}}(()<>)][{()()>])[<<[][]>(<>[])> [[{[{([<<<<([{[][]}{<>()}]([[]<>]<<>[]>))<{[<>()][<>{}]}[((){})]>><[[<{}<>>([]())]]>><<{{(() <{[<<[[[<{{[<<[]{}>[()<>]><{()()}<()[]>>][[[<>{}][[]()]][<<>>{{}[]}]]}{<<<[]()>({}<>)>>(<[[]()]{<>[]} {(([({{<(<<[(({}{})[()[]])<<{}{}>(()[])>](([()[]]<{}()>){{<><>}<[][]>})>((<{()()}[{}()]>[{<>()} <(({(([[<[{[{<{}>(())}{<{}[]>[<>[]]}]{<{()}><<()()>[{}{}]>}}]({<<<()[]>{()<>}>>}[[{(<>){[]}}((()) {{<{<<(([[[{{[{}{}]{<>[]}}}{[<{}<>>[{}<>]]{{[][]}{[]]}}]({<([][])[<>]>{(()())<<><>>}}([([][]){{}()}]<{()[]}{[ [<<<<<[{<{{({[[]()](<>())}{{[]{}}([][])})}(<<[{}{}]({}<>)>[<<>>{()}]>)>({[(<[][]>{{}[]})][[(()())<(){}>]{<()< {({<<([[(<(([(()[])]{{{}<>)((){})}))[([<(){}>[<>()]]{{<><>}})<({<>{}}(<>[]))>]>({[{([]()){(){ <{[<(<{[(<<{(({}[])(<>()))}[{<[]<>><()[]>}<<{}{}>(<>{})>]>{{{<{}<>>[{}()]}}[<<()()}>(([]{})([] {<[(([{{{[(<<[{}()]>{(<>())[[]{}]}>){{[{{}[]}{()<>}]{(()<>)<<><>>}}}]}{(<[([[]][{}[]])]>)[[((<{}[]})[ ([[[({({{[<<[<[]<>><()>]>{([<><>])(<<><>><<>()>)}>[(([[][]]{()<>}>)([{(){}}({}<>)])]][(<<{{}{}}{() {([({[{{{[(<<<<><>>([][])>[<[]<>>[()<>]]>)[[(<()[]>)(<<>()>[()<>])]({<[][]>{[][]}}[<()()>[<>[]]])]](<<{<<><> <((({{<[[({[(([]<>)[[]<>])]{{<{}>{[]<>}}(([][])[()[]])}}{[{<()<>>[()[]]}{{[]<>}{[]()}}]}){([{{{}{}}[( {<<[[{[<(([[{([][])[<>()]}<{<><>}>](<<[][]>[[]{}]>[{<>}{{}<>}])]{<([()<>]<()[]>)(<[][]>(<>[]))>[{[[]< ([{((<[<<([[[{<>()}(<>())]([(){}](<>[]))][[<[]>]]]<{<[{}[]][[][]]>}([<[]()><<>{}>]<{(){}}[{}{}]>)>)>({([ ([{(<<[<{<[[(<[][]>{<><>}){<<>()>}]{({()[]}<<>()>)}][{({(){}}[()()])<[<><>]<<>[]>>}]>}<<[({< {<({[({{<[[({{(){}}<<>[]>}<({}[]){()())>)<{([]{})([]())}>]]>(<{[((<>[]){[]()})<<()<>>({}<>)>]{{{()[]}}} {({[[<(<{[[{<<[]()>[()()]>([<>{}]{<>[]))}<{([]())(()<>)}<<[]><[][]>>>][({<{}><[]()>})[<[()[]][()()]>{<{}<>> {({(((<{<[<(<({}<>)[()()]>{<[]{}><()<>>})[<({}<>)><(<>)<()()>>]>(<(([][])<()<>>)<<<><>>([])>>{(<[]{}> [{{[([<<(<[<({<><>}{[]()})[{<><>}]>{<(()[])><[<><>]>}][<{[{}<>][[]<>]}(([]{}))>[[([])<{}[]>]{<(){}>({}())}]] {[<<((<<[([[([()[]]({}()))(<{}()>{(){}})][((<>[]]{{}{}})((()<>)<<><>>)]]{[<(<>[])<[]>>([<>()]{[] ((({({{<[(((<[<>[]]([]<>)>[<[]{}>{<><>}])<{[<>()][()<>]}{<{}<>>[[]()]}>))<[<{(<><>)<()<>>}>[<[[]<>]<[]{ {<<<{<({([({((<><>)[[][]]){[()<>]{<><>}}}<[{[]<>}[<>[]]][[()<>]{(){}}]>)<[[[[]<>]]((<><>))}(<<()<>><<><>>><[[ (({{[({<{<{[[<<>[]>([][])]{<<>()>{{}()>}]{[<<>[]>[{}{}]][{()()}{[]<>}]}}([({{}[]}{{}()}){(()<>){()<>}} (<([({{{{<[<{{<>[]}{{}}}<[{}{}]<{}{}>>><{{(){}}([]{})}>](<[([]())[()]]>[(<[]<>>[[]{}])])>[{(<[[][]]<{} ((({[{{{([<{{<<><>><[][]>}{({}())<<>{}>}}[{([]())}[<<>()>({}[])]]>{<[<<>[]]<()<>>][[()[]][<>[]]]>[{[[] <(<<[[<{({{[(([][]))([<><>][{}{}])]}})}>]](<([{{[{<{[][]}[{}<>]>([{}()])}]}([{{(())}{{{}{}}<[]{} <([<[{{({[(({({}{})<{}()>}))[[((<><>)<{}>)[[[][]]((){})]]<<<[]()>{()[]}>>]]{<<(<[]<>>[<>{}]){({}())}>>}}{[[ [<<[(({<({{{[{[][]}{(){}}][<()()>]}((<{}{}>>[{{}[]}])}{<[(<>[])[(){}]](<<><>>({}<>))><(({}()) [([{<{(([[[([{{}[]}<(){}>])]<{([[]()][[]<>])([{}{}]([][]))}>]({<<([][]){()<>}>>{([()<>]([])){{{}()}{[][]} {<({[<[(({{({<(){}><[][]>}[{<>()}({})])<[[{}]{<><>}]<<[]{}>([]{})>>}[(({[]<>})([(){}]<()[]>))]}))]><<( {<<[[<[[[((<[<{}<>><<><>>]<({}[])([]{})>>{<{()<>}>{([]{})[()[]]}}>[[<({}<>)([]{})>(<{}()>[[]()])][[<()<>><[] {((({(<{[[[({<<>[]><{}<>>}[{[][]}[<>()]]){([<>()][[]()])({[]<>}{{}<>})}]<<{[{}<>]<{}()>}<(()){(){}}>>{ <[[{<<([<[{{(({}()){[]{}}){{{}[]}{<>()}}}}{<{[<><>]<{}{}>}(({}()){()<>})>(<(<>{})[<>()]>{<<><>>{[][]}} {{([{(((({<{[({}{}){{}{}}]{(<>{})[{}{}]}}[{[()[]][{}()]}{(()[])(()())}]><({(<>[])}((())<[]>))>}<{{{{{}<> ({(([({(<<<((({}[])((){}))((<><>)[[][]]))((<()<>><(){}>){{{}()}(()[])})><([[{}<>][()[]]])(([<> <<<<<{({{([(([{}{}]<{}()>))][<<{<>[]}{<>}>({()<>}{{}()})>[([<><>]{{}()})([[]{}])}]){({[([]<>)<[][]>][{<><> ((<[<<{{<([{{[{}<>]{{}<>}}([[][]]<<>{}>)}{[[[]{}]])]{[<<{}<>>{{}{}}><({}<>)>]([(<><>)[{}()]])})(< <(((<[(((<([[{(){}}<<>()>]]<{<<>{}><(){}>}<{[][]}{[]{}}>>)>{<<{{<><>}{[]<>}}{{<>[]}<[]()>}>[{{{}()}{[]<> {[<{((<<[<<([(()()){{}()}](([]{}){<>()>))>{({((){})({}())}[[()][<><>]])<([{}[]][[]{}])(([]{}){()<>} (<[({[(([[{[[<{}{}><<>{}>][<<>{}>]]([{<>()}<<>{}>]{{[]{}}({}())})}([({{}()}{{}()})][[<<>[]>[<>{}]]{<<>[])}]) {<{(((<([[[<[(<>())[()[]]]<<()[]><{}<>>>>]<{({<>()}(()<>)){<<><>>{{}[]}}}{(<()<>><<>[]>){{[]()}[[]()]}}>][(<[ <<[[<(({{{{<{{[]()}({}<>)}[(<>{}){[]{}}]>[<{[][]}{{}{}}>]}{{(<<>()><{}{}>)[{{}[])[(){}]]}(([()[]][{}[]]){< (<(<<<([{((<[[{}[]]{{}}]<({}<>)<()<>>>})<(<[<>{}]<{}<>>><([]<>)([]<>)>)[{<{}<>>[()()]}[(<>[])] <{(([([[<<([{{<><>}[<><>}}{[{}<>]{{}<>}}]{([[]()]<()[]>)[({}<>){[][]}]})({[((){})<<>[]>][{<>()}[[]<>] <<<{{<{[({<<[[[]][[][]]]({[]()}{{}[]})>>{[({{}<>}{[][]})[[{}()]{[]}]]}}([[[[<>[]]<{}[]>]{[{}{ {<{{([([<{[[{([]<>)[()<>]}][{<()()>}<{{}<>}([]{})>]]{{[{[][]}<{}[]>]([<>()]{{}{}})}{(({}{})(( <{<((<{<{([<((()<>){()[]}){[[]<>](()[])}><(([]()])<[[]()]{{}<>}>>]{({<()><()()>}[[()<>]<<>[]>] [<[{[(<<[(<<<(<>[])[[]]>{<(){}>}><([<>[]]{<>{}})[{<><>}{[]()}]>>{[(<[]<>>)<[{}<>]{<>()}>]{<(()())[[][]]>[ [<<<{[(<<[({{{<>[]}<[]()>}{<<>[]>(<>[]]}})]>>{[[<({([][]){{}()}}[{<>()}({}())])({(()[])(<> [<[[<{<{{{{{<([]())[<>()]><{()<>}[<><>]>}}}}}><<{(([{<[][]>{[]()}}[{[][]}{{}<>}>][(({}())({}()) <[[{{[<{<<[<(<<>[]>)<<()()>{{}[]}>>{<{()<>}[<><>]>[{{}{}}{()}]}]{(<([]<>)({}())>{<[]{}>}){[({}())]{( ({{[(([(<{[[{(()<>)({}())}<({}{}){{}}>](((()())<{}()>)[<{}<>><{}()>])]({{([][])({}<>)}<({}())<[] {[(<[<{[(([<(<[]()><{}()>)<<[][]><()>>>][<<[{}[]]<{}{}>](<<>>{<>[]})>[{(<>())[<>]}<{[]<>}(( [{{(<{{[{<<<<(<><>)>(({}[]))><<[[]{}][<>()]>>>({[({}{}){<>{}}]<[<><>]>})>}<[<{{<{}{}>{<><>}}}>]<( {<{<<{[{<[[[<<{}[]>{()<>}>(<()[]>({}<>))]{<((){})[<><>]><{<>{}}{<>()}>}]({([()[]]{[]()})}([{()()}}<(<>() [<<([(<[<[[([(<>{}){()<>}][<{}()><{}()>])]((([()<>]{()<>})[[<><>]]))][{([{{}{}}]<{<>}[{}()]>)[[{ <[[{([({<<<(<([]<>)<<><>>>[{[]()}<(){}>])>>>({(([[<>{}]([]<>)]{[(){}](()())})([{<>()}([]<>)]))<[{[{}()]{<>[]} <(([{<{[[<({[({}()){{}[]}]{<{}[]>[{}<>]}}[[[{}<>](<><>)][<()()>({}<>)]])<{{[{}<>]{<>[]}}}([[{}[]]<<>{}>])>> {(<[([[[{[<[[<[]()>[{}{}]][<()[]>{[]()}]]>[[[(<>[]){<>[]}][{<>{}}<()[]>]]]](<{{([]())[()()]]<[{}[]][[]( [([[[<<<{({[[{[][]}<()[]>]][{{[]()}([]<>)}({()<>})]))[<{<[<>{}]{[]{}}>({<>{}}[()()])}><<([<>[]]{{}[]})[<[][] {(({({<{([[[[<[]{}>(<>{})]{({}())(()<>)}]]<{{<[]()>(()())}{([][])}}<{[[][]]<()<>>}{(<>{})({} [{{<[{(<{({<[{[]<>}[[]()]][[{}<>]{{}()}]>(<[()()]>([{}[]]{(){}}))}{{{({}<>)<<><>>}({[]<>)<{}>)}})([<({ (<[{{{{<(<[<{{()()}{[]{}}}<([]{}){<>()}>>[({{}<>}{{}[]})]][[({{}()}(<>[])){<[][]>[<>()]}]]>]>{[( [{<(<<{[<(<[<({}[])({}{})>]{<{{}()}<<><>>>{<{}{}>(()())}}>)>][({<[[<(){}>(<>())](({}{}){{}()} {([[{<{<{(([<([]<>)[<>]>{(<>[]){<>[]}}][<[(){}]{{}()}>((<>[]))])<({[()<>](()[])}){<[()<>]{<>{}}>{([])<() <[{[{(<<({[((<[]{}>{[]{}})([()[]]<(){}>))<{<<>[]>[{}]}{<{}<>>{()}}>]{{{(<>())}(({}<>))}<<{()<>}({}())>([{}< <(<[{{<{{[([{{(){}}<<>{}>}(<(){}>)][[{{}<>}(()<>)]]){([<<>{}>[()()]][{[]()}<{}()>])}]<{([{[]}([][] <[[{<{[<{([<[<[]<>][{}]]<({}{})([])>>]({{(<><>)[[]<>]}<<{}[]>[[]<>]>}))}([<(({()()}{[]<>}))<{<()[]><[]()>}((( ({{{<{([{<[{{[{}<>](<><>)}[[<>()]({}[])]}[[<(){}>({}<>)]<(()())({}())>])>[<<<[[][]][(){}]><([ ((<{[<[[(((<[<<>()>([]())]<(()<>){()[]}>>[<{(){}}{{}}>[[(){}}<[]{}>]])<[[[[][]][{}()]]{[{}()][ (({[[<{({[[[[[<><>]<[]{}>]<(<>{}){[]()}>][(([]<>){()[]})([<>{}]<()<>>)]]]}[[<{<(<><>)<{}[]>>}<<{<> <{({[{(([[{(<(()[])<(){}>>{<{}{}>{<><>}})[<(()())<[]{}>>]}[{{{[]}[()[]]}[<()[]><<>{}>]}{<[<><>]{[] [<[<<{<{{<[(<{(){}}[<>()]><({}<>)<<>{}>))<<<()<>>({}<>)><[<><>][()]>>](({({}()){()()}}<[[]<>]<<>{}>>)<[[[] {<{(<(<[<([{<{{}[]}(()[])>[({}())<[][]>]}<<{()()}[<><>]>>]<{{[[]{}]{<><>}}(({}{})[[]])}({(<>[])<<>{}> {{{[[((<[(<<[[{}()]<[]<>>]{<()[]>}>[<<()()>>([<><>]((){}))]>{<<[{}{}][{}()]>[(()())[<>[]]]>{{ <({<{[{<[<({{[<><>]{<>[]}}<{[]<>}<<><>>]}{{[{}{}]{{}{}}}{<[]<>>{[][]}}})(<({()<>}<{}[]>){([]{}) {<(<<[<{([{[({{}<>}[()()]){(()<>)[{}<>]}]}])}>]{{(<[<<((()())<<>()>)>{([[]{}]((){}))<({}<>)({}< [<(<[[{{[([[<<[]{}>{[]<>}>{(<>[])[{}{}]>]([[[]<>](()())])])([[<{<>{}}(<><>)><({}<>)<()>>][({[]<>} [<{({{[<([{<{[()[]][(){}]}>[([<>[]]{{}})]}<<((()<>}(()()))<[(){}]>>((({}())[{}<>]){({}<>)<<>[]>})>]{<<{<{}[] [[<{<{({(<{<{({}())[{}]}([()[]]{{}()})>}((([{}{}]{()<>})<[<>()]{<>[]}>)[([()<>]<<><>>)[[()[]]{[]}]]]>){([[[ {<(([<<[<{(((<()<>>{{}()})({[]{}}[[]{}]))(([{}[]]{[]<>})<<[]>(<>{})>))}[{{<(<><>]<<>>>}}({[({}[]) [[{{[([<[({[{(<>()}[<>[]]}{{<>{}}<[]{}>}]{{{()[]}([]{})}([()<>]{()<>})}}[<{(<>)<<><>>}{{<>[]}<<>[]>}>({< {{[{{{<([<{<{<{}<>>}{[(){}]{{}()}}><{{[]()}<{}>}>)[[{[{}{}]{()<>}}<(<>{}){[]{}}>][[(()<>)(<>())]({[]<>}[()[] ((<({<{[(<[{[<<>><{}()>][[{}[]>]}{({()<>}[{}[]])[(()())]}][<<{<>{}}<<><>>>[{[][]}{<>()}]>]>[<({({}()){{ [([<<({({[<{(((){}){<>{}})(({}<>))}{<[[]()][{}{}]>{([][])<[][]>}}>]<<(<{<>()}[()[]]>[<(){}>[<>()>])<<[{}( AOC_10_brackets.py
from __future__ import annotations from dataclasses import dataclass from pathlib import Path from typing import Annotated, Generator, Iterable, TypeVar, Union Score = Annotated[ Union[int, float], "A value representing the score of a line according to some restriction", ] BRACKET_PARTNERS = { "(": ")", "{": "}", "[": "]", "<": ">", ")": "(", "}": "{", "]": "[", ">": "<", } @dataclass class Bracket: name: str is_open: bool syntax_error_score: Score = 0 autocomplete_score: Score = 0 def __post_init__(self): self.is_closed = not self.is_open def __repr__(self): return f"'{self.name}'" def __str__(self): return self.name @property def partner(self): partner = BRACKET_PARTNERS[self.name] return BRACKET_TYPES[partner] BRACKET_TYPES = { "(": Bracket("(", True), "[": Bracket("[", True), "{": Bracket("{", True), "<": Bracket("<", True), ")": Bracket(")", False, syntax_error_score=3, autocomplete_score=1), "]": Bracket("]", False, syntax_error_score=57, autocomplete_score=2), "}": Bracket("}", False, syntax_error_score=1197, autocomplete_score=3), ">": Bracket(">", False, syntax_error_score=25137, autocomplete_score=4), } @dataclass class Brackets: """Takes in a list of brackets and checks if the brackets are incomplete or corrupted If a closing bracket appears before the matching opening bracket, the line is marked as corrupted. If the number of opening brackets is greater than the number of closing brackets, and the line is not corrupted the line is marked as incomplete Example: # Legal brackets >>> Brackets.from_string('') Brackets('') >>> Brackets.from_string('()') Brackets('()') >>> Brackets.from_string('{()()()}') Brackets('{()()()}') >>> Brackets.from_string('<([{}])>') Brackets('<([{}])>') >>> Brackets.from_string('[<>({}){}[([])<>]]') Brackets('[<>({}){}[([])<>]]') >>> Brackets.from_string('(((((((((())))))))))') Brackets('(((((((((())))))))))') # Corruped brackets >>> Brackets.from_string('(]') Brackets('(]', corrupted) >>> Brackets.from_string('{()()()>') Brackets('{()()()>', corrupted) >>> Brackets.from_string('(((()))}') Brackets('(((()))}', corrupted) >>> Brackets.from_string('{([(<{}[<>[]}>{[]{[(<()>') Brackets('{([(<{}[<>[]}>{[]{[(<()>', corrupted) # Incomplete brackets >>> Brackets.from_string('(') Brackets('(', incomplete) >>> Brackets.from_string('([{<') Brackets('([{<', incomplete) >>> Brackets.from_string('<{([{{}}[<[[[<>{}]]]>[]]') Brackets('<{([{{}}[<[[[<>{}]]]>[]]', incomplete) >>> Brackets.from_string('[({(<(())[]>[[{[]{<()<>>') Brackets('[({(<(())[]>[[{[]{<()<>>', incomplete) """ brackets: list[Bracket] incomplete: bool = False corrupted: bool = False syntax_error_score: Score = 0 autocomplete_score: Score = 0 def __post_init__(self): self.incorrect_bracket = None self.opened_brackets = [] self.check_bracket_balance() self.autocomplete = self.get_closing_brackets() self.calculate_score() def __repr__(self): return ( f"Brackets('{''.join(map(str, self.brackets))}'" f"{', incomplete' if self.incomplete else ''}" f"{', corrupted' if self.corrupted else ''}" ")" ) def __str__(self): return "".join(map(str, self.brackets)) def check_bracket_balance(self): """Checks if the line number of opening brackets and closing brackets match""" for bracket in self.brackets: if bracket.is_open: self.opened_brackets.append(bracket) continue if (last_opened_bracket := self.pop_open_bracket()) is not None: brackets_match = last_opened_bracket.partner == bracket else: # This triggers when the number of opened brackets is empty # E.g a closing bracket appears before an opening bracket brackets_match = False if not brackets_match: self.incorrect_bracket = bracket self.corrupted = True return # If there are un-closed brackets after reading the entire line mark it as incomplete if self.opened_brackets: self.incomplete = True def pop_open_bracket(self): try: return self.opened_brackets.pop() except IndexError: return None def get_closing_brackets(self): """Returns the neccecary brackets to match every open bracket with a closing bracket Example: >>> Brackets.from_string(')').get_closing_brackets() [] >>> Brackets.from_string('(').get_closing_brackets() [')'] >>> Brackets.from_string('([{').get_closing_brackets() ['}', ']', ')'] >>> Brackets.from_string('<{([{{}}[<[[[<>{}]]]>[]]').get_closing_brackets() [']', ')', '}', '>'] """ if not self.opened_brackets: return [] return [bracket.partner for bracket in self.opened_brackets[::-1]] def calculate_score(self): """Calculates the syntax error score and the autocomplete score of the line""" if self.incorrect_bracket is not None: self.syntax_error_score = self.incorrect_bracket.syntax_error_score return # If a line has a syntax error, it it not possible to autocomplete it for bracket in self.autocomplete: self.autocomplete_score *= 5 self.autocomplete_score += bracket.autocomplete_score @classmethod def from_string(cls, string: str) -> Brackets: brackets = [] for char in string: if (bracket := BRACKET_TYPES.get(char, None)) is not None: brackets.append(bracket) return cls(brackets) T = TypeVar("T") V = TypeVar("V") def with_attributes( lines: Iterable[T], attributes: Union[str, list[str]], values: Union[V, list[V]] ) -> Generator[T, None, None]: """Yields lines where every attribute matches every value""" list_of_attributes = attributes if isinstance(attributes, list) else [attributes] list_of_values = values if isinstance(values, list) else [values] for line in lines: for attribute, value in zip(list_of_attributes, list_of_values): if not getattr(line, attribute) == value: break else: yield line def median(numbers: list[Union[float, int]]) -> Union[float, int]: """Calculates the median from a list of numbers The indices in the middle are (len(nums) - 1) // 2 and len(nums) // 2. If the length is odd, then these indices are equal, so adding the values and dividing by 2 has no effect. Example: >>> median([]) Traceback (most recent call last): IndexError: list index out of range >>> median([2]) 2 >>> median([0, 1]) 0.5 >>> median([0, 100, 1]) 1 """ numbers.sort() middle1 = ((length := len(numbers)) - 1) // 2 middle2 = length // 2 if middle1 == middle2: return numbers[middle1] return (numbers[middle1] + numbers[middle2]) / 2 def read_brackets_from(path: Path) -> Generator[str, None, None]: with open(path, "r") as f: for line in f: if brackets_as_string := line.strip(): yield brackets_as_string if __name__ == "__main__": import doctest doctest.testmod( extraglobs={ "Brackets": Brackets, } ) # PATH_2_BRACKETS = Path("AOC_10_brackets_test_01.txt") PATH_2_BRACKETS = Path("AOC_10_brackets.txt") bracket_strings = read_brackets_from(PATH_2_BRACKETS) brackets = [Brackets.from_string(string) for string in bracket_strings] # Part 1 corrupted_brackets = with_attributes(brackets, "corrupted", True) print(sum(x.syntax_error_score for x in corrupted_brackets)) # Part 2 incomplete_lines = with_attributes(brackets, "incomplete", True) autocomplete_scores = [x.autocomplete_score for x in incomplete_lines] print(median(autocomplete_scores)) 
