commit fe3669a04ddea58eaef3c57e676126c0f314561e parent 6625751d3b1f1d8952e8028d19c689bcff96748c Author: Shimmy Xu <shimmy.xu@shimmy1996.com> Date: Fri, 10 Dec 2021 22:49:47 -0600 Add 2021 day 10 Diffstat:
| A | 2021/day10/input.txt | | | 94 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2021/day10/main.rs | | | 90 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
2 files changed, 184 insertions(+), 0 deletions(-)
diff --git a/2021/day10/input.txt b/2021/day10/input.txt
@@ -0,0 +1,94 @@
+{[<<([{((((<[<[]{}><[]{}>]<<{}{}><[]<>>>><<([]<>)>[({}[])({}[])]>))([[({[]{}})<{{}{}}(())>][[{
+({[{({[<<<<<<(()())>>{{([]{}){{}[]}}{<(){}><<>[]>}}>{(<[[][]]{<><>}><<{}<>>{<>{}}>)}>>>]<[{<{<{[(){}]<()()>
+[{[{{{[<({<((<()()>[{}()])({<>[]}{[]()}))>[{{[[]()]<{}()>}[<[]<>>{<>{}}]}{[<{}<>>{<>()}][(()<>)[
+{([<(<{{([[{(((){})[<>[]])<[[]{}][{}<>]>}{[{<>{}}]{<[]()><()[]>}}]])}({[<{(<()<>>)({{}()}[
+<[{({{(({<[{{(<>()){[]{}}}[{[]{}}]}<{{{}{}}<{}()>}{<<><>>({}())}>](<{{[]()}[{}[]]}((()<>>([]<>)
+({[{[[[{{{{[<({}())[[]()]>({<><>}(<>()))]<((()())<{}<>>){{<><>}(()())}>}{<({[][]}<[]()>){{{}()}
+{((<<<<(([(((({}()))[[()()]{{}{}}])(<{{}}{()<>}>((<>[]){{}<>})))({<({}())[<>[]]>[{[]<>}]}[<[{}{}]<
+(({([{{{{([<{<{}[]>({}{})}[{<>{}>([]{})]>][(((()())<()[]>)(<(){}>[{}{}]))(({{}{}}({}()))({{}(
+{([<{{{{({{{([(){}])}[<<[]<>>([][])>({[]<>}{[]()})]}}{{[{(<>[]){(){}}}({[]()}{{}{}})]{{{{}()}([]<>)}}}{{
+(<<(<<{[<{((({[])<[]{}>){[[][]]}))[[<<<>{}>>][({{}()})([()[]]<[]<>>)]]}(({<[()()]{()[]}>([<>{
+({<[({[<{[{(<<()[]>(<><>)>{([][]){()<>}})[(<(){}><{}[]>)(<[]{}>[<>[]])]}]<(<[(()[])[{}[]]]>{[[(){}]([]
+<<<{{<([([<(<<{}{}>[<>[]]>(<{}()>[[][]])){<<<>{}>([]())>(([]{}){[]})}><{{{{}[]}<()()>}(<{}<>>{[]<>}
+<[[{{<(<[{[{{({}[]){()()}}((()())<()<>>)}][[{(<>[])(<><>)}(<()[]>{{}<>})]]}[{<<<{}<>>><{{}<>}[{}{}]>><
+[<{([<[<<<<[({<>[]}{()}){[(){}]{()[]}}]><[[[[][]]{<><>}]]<<{()<>}{<>{}}>(<()()>[{}()])>>)<<{{<<>
+[([(({([({{<<{<><>}>({{}{}}{(){}}))<[<{}{}>(()<>)]<<[]>>>}}{({<<{}<>>{[]()}>{[{}[]]{()[]}}
+{{<<(({{[[<({{(){}}}[<<>{}>{[][]}])<{<{}<>><{}{}>}{(<><>)((){})}>>{[{(<>[])([]{})}{<{}[]>}]}]<<[<((){})(<
+<{(<<([<[{<{{{()[]}<<>{}>}(({}<>)(<>()))}{{((){})([]<>)}<{()<>}[<>[]]>}>{[<{{}<>}>(<<>[]>[{}
+<{({(<{<<{(([(<>[]){<><>}]({[]{}}(()[]))))([[{{}()}{{}<>}][[[]()]{()}]])}(<[<<[]()>(<>{})){{{}()}<<>()>}
+<<([{((<({<[<({}[])({}[])>]<{[[]<>]<()[]>}[<{}<>>(()<>)]>>[[<[<>()]<()>>{(<><>]{[]<>}}][{<()<>>{[]<>}}
+[{<[<(<[(<{<({{}{}}[{}[]])><{(()<>){[]()}}{{[]()}[()()]}>}>[[[<({}[])>{<()<>>[<><>>}]]])]>(<{<<[<(
+[[(<<<{{[[<<<[[]<>][[]<>]>{{<>{}}}><<{[][]}{()}>>>]]}[([{<<[{}{}]<{}<>>>>[(<()[]>{()()})]}]([[(<
+<<<[<<[<[{<(({{}{}}<[]{}>){[{}{}]{{}{}}}}{<(<><>)[{}{}]>{[(){}][()<>]}}><(<{<>{}}(<>{})>{<{}<
+[({<[<(((<({[[{}{}](()[])]<<[][]}>}<{{[]{}}([]())}{(<>())<{}[]>}>)>))({<[<{(<>{})[<><>]}(<(){}
+<(({[<[<{{{<[[<>{}]]{((){}){<>[]}}>(([{}<>][{}<>])[[[]()]<()()>])}(<[<[]{}>{<>{}}]><<(<>()){<>()}>([()[]]{<>(
+<<<([(<(<(<[<{<><>}<()[]>>(((){})((){}))]<({()[]}({}<>)){<[]<>><<>()>>>>[<[[<><>]([]<>)]>[(({}{})<()
+(([[(<{[([({[[{}()]{[]{}}][{{}<>}<{}<>>]})([[[<><>]<<>>]][([[][]])])][<<[[()<>]{<>{}}]<[{}()](()())>>{[(
+[{{<<{<({({[(<<><>><<>[]>){[[]{}](()())}][((<><>){<>[]})(({}<>){[]()})]}<(({[]()})(<[]()><{}[]>))(<
+{(<{<[<[<[<[[<()[]>(<>{})]{(<>{})<<><>>}]>[({[<><>]})[<<{}<>>{<>{}}>]]]<[[<{{}()}(<>[])>]]<{{<()[]
+{[{((<<<<[<{({()<>})}>{<(({}<>)){{()()}{{}{}}}>[<[{}()][<>()]>[[<>{}]{[]()}]]}]({{[<<>{}>(<>[])
+(([[<<({{{[<<([]{}){(){}}>[({}<>)<{}<>>])(({[][]}){{<>{}}[[]()]})]}}})([((((({[]()}[()<>]))
+<<<{<<[[{({([{()()}(())])<<{[]<>}<()[]>><<()[]>[{}<>]>>})}<[[{([<>[]>(()())){([]{})<()[]>}}<[<(){
+{<{{{<[([[{[<(<>)<<><>>>{<<>{}>({}[])}](({()<>}({}))[(<>[])])}]<{[[<{}>(<>[])]{[[][]][<>[]]]]{((<><>)[(){
+<({({<<(({([[[()[]]{<><>}]{[[]<>]}]{[<<><>>[(){}]]({()[]){{}{}})})}<{<[[[][]]<<>{}>](({}<>)(()<>))>
+{{{[(((<{{(<({{}[]})><([{}{}])<([][])[<>[]]>>)<{[(()<>)[<>[]]]{[{}[]]<[]()>}}>)}{<<[<<[]{}>[{
+[({<{(([<<([([[]()]<{}[]>)<{{}()}<<>[]>>]{[{{}}<[]>]{{[][]}(<>())}})[[{<[]{}>{()<>}}<(<>{})(<>{})>][
+{<(<{[{[{(((<{{}[]}{[]()}>)[{{<>[]}{<>[]}}((()[])<<>()>)]))(({[{<><>}<[]{}>][{[]()}]}<<{<>}[<>()]>(<[][]>{[]{
+{{{([[{<<[{[{[[]()]{{}{}}}([{}]{()[]})][<<[][]>(<>{})>]}]{[<<[<>())(<><>)>[{<>{}}{[]<>}]>]
+{[<{{<[[<[[(<([][]){()}>[{{}<>}[[]<>]])<((<><>){<>{}})([<>{}]{{}[]})>](<[{()<>}[<>{}]]>{<<[]
+[<(((({[{((<{<{}{}><(){}>}][<(()<>)<[]{}>>(<()[]>[{}{}])]){[[[[]()]([]<>)]][<(()[])<<><>>><{[]<>}>]}
+({(<<(({{[{<<{{}()}{()<>}>({[][]}{<>{}})>}]([{{{[]{}}<{}()>}[(()[])({}())]><{[{}<>]<()<>>}[
+({(<<[({({<[<[()()]>{({}()){{}{}}}]>[<{(()<>)<{}{}>}{<{}{}>[<>[]]}]((<[]<>>)[[[]()]<<>[]>])]})[[[[[[
+{<(<<[[[<{({{{[][]}{()}}[{{}<>}{[]<>}]}<([[]{}]{[]()})[(()<>)([][])]>)}>]]]>>[<{[<{[<[([{}{}]([]<>))[[
+{<({{<{<(<[{[[{}()](<>{})]<{<>()}{<>[]}>}{{[{}{}]}<<{}{}>({}[])>}]({[{()()}[()[]]]}[<{()()}{{}{}}>[<()[]
+{[[{(([({([([{<>()}[<>{}]])]<<[((){})({}<>)]><[[[]<>](<>[])][<()>[[]()]]>>)})])<[{<[<<<[[]]>{<<><
+{<[[<[<<{[{<({[][]}[(){}]){<()<>>[{}<>]}><([[]{}][()[]])[<()()><()[]>]>}({[{[][]}][[{}{}]]}[[{(){}}<<>[]>
+({(<{[[{<<<(([{}()]<(){}>)[[{}<>]<<>[]>]){<{[]<>}(()<>)>}><{({[][]}(())){<()()>(<><>)}}>>([<([{}[]][<>()
+<{<(([(<({[<{((){})<{}()>}[[[]<>]{[]()}]>({({}[])<(){}>})]{[{[()]{{}[]}}<[{}()][[]{}]>]}})>)[<<([({<
+[(({{{(<{{{[<<[]()><[]<>>>{((){})}]}{{{<()<>><[][]>}}}}{[<(<[]<>>[{}[]])[{()()]]><[([]())[{}[]]]({{}[]}(()[
+[[(<<<{{<{<<([<>()]{{}{}})[[<><>][<>[]]]>>[[([<>[]][[]{}])({[]{}})]<[<{}{}>[()<>]]>]}{(<[{{}[]}{
+{{{(<[(<{(<[{{<>()}{[]<>}}]>)<[{([[]()]<{}<>>)[{<><>}([]<>)])(<{()}(()<>)>([{}<>](<>[])))]<[<<<>><<><>
+<[[(([(<<[{[<<()[]><<>()>>{[{}[]][()[]]}]{[<()[]>{()<>}](<()()><{}[]>)}}{({[[]](()<>]}({[][
+<[<{{<([<{<{[{[]}({}<>)][(<>())]}<<[()[]](()[])>{<{}()>[()[]]}>>(<{((){})[{}()]}>((((){})((){
+([<{<{[<[[<<{(<>[])}[<<>[]>{[][]}]>>]<({<(()())([]())>(({}<>)<[]()>)}{({(){}}([]{}))[{<><>}<<><
+{{(([({({{<(({{}()}{[]{}})<([]{})>)>[[[[{}<>]](((){})[()<>])][(({}{})({}[]))<[[][]]<<>{}>>]]}))}){{<
+[{{<{{<<{({{<[{}[]][[]()]>[<<><>><{}{}>]}{[<()[]><[][]>]({{}()}(<>{}))}}<<([<><>][[]<>]){(<>}(<>())}
+{[<({<[[[[{<{<<>{}><<><>>}{[<><>]({}<>)}>((((){})[{}<>])[{()<>}{{}[]}])}({(<[]()><{}()>)}{(
+[((((({{<[{({[{}[]]{{}()}}{(<>())[[]<>]})}(<{<()[]><[]{}>}>{<[[]()]<(){}>><{[]}{[][]}>})][<{((
+{[(((([[[([{<{()[]}(()[])>((()<>)[<><>])}]([([{}()][[]()])[{{}<>}{(){}}]]({({}{})<{}{}>}<{{}[]}<{}<>>>)
+[(<([{{[(<({{[<>]<()<>>}{[[]{}][[]{}]}}]>)]}}<{(([[{({[]()}({}[]))<[()<>]{(){}}>}]{({(<>[]
+(<([([<([<{{{{<><>}<()()>}{({}()]<[]<>>}}}>]([({<((){}){{}[]}>}([{()()}{<>{}}]<{[]<>}{(){}}>)){{[<[](
+[{<({{([(<[(<{{}()}{<>()}>((<>())<<>()>))<<[{}[]]><({}())[<><>]>>]<{{[{}{}]{[]()}}<(()<>}<()[]>>}<<({}()
+[<<(([<{<{[[{{[]<>}{{}()}}<[<>()]<<><>>>]({({}())(())}([{}{}]<{}()>))]{<((<><>){<><>}){(()())}>}}({{([
+{{{([{{[<{(<{<<>{}><<>()>}<{()<>}{<>[]}>>)[[<[<>{}]<{}{}>><{()[]}>][(({}())([]{}))[[{}[]][{}()>]]]}[
+({<(({<<(<<[{<<>{}>{<><>}}((())<{}[]>)]><{((<>{})<<>()>)}>))>(<[<[{[<>{}][[]()]}[({}{}){<>()
+[{{<[<<({([{{{()[]}(<><>)}([<><>]<<><>>)}[({<>{}}((){}))]][[(<<>{}>[{}()])<([]())([]()>>]{
+({([<[((([{([<()()>[()<>]])(<{[][]}<{}[]>><[()<>]{<>[]}>)}({[{<>{}}{[]{}}][([][])]}[{{<><>}}<[{}{
+{[{(<[[[{<([({{}()}(<>[]))<[[]<>][[]<>]>][<(<><>)<<>{}>><[[]{}]{<>{}}>])(([<[][]>{{}()}]<{
+{<<(<<{<<([{[<{}[]><{}[]>]{{{}{}}{[]()}}}(<[[]{}][[]<>]><[()()]>)]){(([(<><>)([][])](<{}()>)){([<>{}](<>
+(([[{{[[{{{<{{<>[]}{()[]}}(<()<>})>({[[]()]{[]()}}<(<>())>)}[[([{}](()[]))<<<>{}>{<>{}}>]{{({}<>
+[<([(<<{({<[<[(){}]{(){}}><<{}[]>(<>())>]>({([<><>]({}<>)){([])[{}[]]}}[[<[]><{}>]])}){<{<<{[]<>}[{}[]]>>}{((
+((<<({({({[[[<{}[]>{[][]}]<{[][]}[<>{}]>]{[([]{}><[]{}>]}]((<{()[]}[<>[]]>{(<>[]){()<>}}))}[[[
+(((<<{{([{{(([[]<>]<[][]>)({[]{}}[()<>]))[<({}{})<[]{}>>{{{}()}[()<>)}]}}[{<{<(){}>[()]}{(<>{}){()[]}}>
+([([<<<[[[[<{{[]()}}[[<>()][[]()]]>{({{}{}}<[]()>)}]]][({([({}{})[{}<>]])[{<[]>{()()}}{(()[])
+{[<(({((<{([{(<>[])}]{{{<>}[[][]]}((())<[]{}>)})}>[{([[<{}<>>([]{})]))[{<{{}<>}[()[]]><{[][]}
+<[[<{[<[{{{[<(()())}([[][]]<<>{}>)]{<{[]}<{}[]>><[{}{}](<>{})>}}}}({(<(([]()){[]()})><{({}<
+[(({({[(<({(((()[])))})>[[{(([[]()](()<>)){{{}<>}<{}()>}){[<(){}><[]()>]<({}<>)[()()>>}}[[<<()()>{()[]}>
+{<[({([[(({[{[<>{}]{<>{}}}{[<>()]}][<[{}[]]<()<>>>{<{}()><{}{}>})}(<{[<><>][<><>]}>([(<>{})<{}()>
+[{<{<{{([[[[[([])({})](([]()){<>{}})]<[{{}{}}[{}{}]][<()()>(<>{})]>]]]([([<[{}[]]<()>>[({}[])(<>())]](
+<(<{({{((<<[({[][]}[<><>])]><<{[{}]<[]<>>}[<[]<>>]>([{{}[]}({}<>)][[[][]]{[]()}])>>((([{(){}}[(){}]])({<()<>
+<{(<<(<({[<{([{}]{[]{}})[<()[]><{}[]>]}>(([({}[])]<(()<>)[()()]>)<[{[]()}<<>()>](<(){}>[{}{}])>)]}<{({[{[]<>}
+[(({([({[<[{({[][]}<()()>)<(<>{})[{}()]>}{<{{}<>}<{}[]>>([<>()](<>))}]>[[((<[]>[[]<>]){({}())((){})})][([[(
+({[[(<<{{{<[[[()<>]{{}<>}]{<()[]>({}())}]<[[{}[]]{<>{}}][[<>{}]{[][]}]>>}}}]>[<{{<{[[<<>[]>({}{
+((<[{[{{[<<{<{{}<>}<()<>>>[<{}<>>(()())]}(<<{}()><[]()>>(<{}{}>{(){}}))>([({<><>}<{}()))[{[
+([{{[{[{[(([[(()[])[<><>]](<{}()>([]<>))]))(({[{()}]<(<>[]){()<>]>}[({()[]}[{}()])]))]}][<(<{<<[[]<>]<(){}
+{{<{([{<[([<{(<>[])<{}{}>}[{(){}}(<>())]>[(<{}<>>[{}<>])((<><>)[()[]])]]<(({{}{}}<{}[]>)<[{}
+{{{{({<[{({{[[<>{}][[][]]]<<()<>>{[]}>}})]]>}){[<[<({((<{}[]>({}()))((()<>)))((<[]<>>))})>[([{[<{}()>(<>{})]<
+{(((((({((([{((){})([]<>)}(<{}{}>(<>()))]<<{<>[]}<<>()>>>){{<([]())[{}{}]>[(()())<(){}>]}<<{{
+{[[{<{(([{[[{(()[]){[][]}}(<()<>){{}()})]]}<(<([(){}])[[{}[]]{<>()}]>){{<[[]()]>(([]<>)[[]<>])}{(<{}<>>[(){}
+<<[<{<[[({(<<(()()){{}{}}>>[{<(){}>({}())}{<{}()>[[]<>]}])[{{({}<>)<<>()>}<{{}()}<{}<>>>}[{[{}{}]
+([([{{[[([<[[<<>{}>[[]()]]{[[]<>]<[]<>>}]({[<><>][<>{}]}{[[]()]{<><>}})}<(<<<>[]>{{}()}>{<()[]>
+[[[[([<<{[{({[{}<>][{}<>]}([()[]]<[][]>))(<([])>)}{{({<><>}[{}()])(<<>()><[]()>)}{((<>[])<
+[(<[([<<({[<<({}[])(()[])><{<>()}{{}<>}>>(<{[]<>}{{}[]}>{[()()]<[][]>})][[{<{}[]>(()[]>}<<{}[]
+[{[<<({([{<[({[][]})]>{({{()<>}{{}[]}}[(<><>){[][]}])}>]<[<<<<[]()>(()[])>{[[]()]([]<>)}>>(<
+<[(({<[({<[{{{()()}<<>[]}}({<>[]}<[]<>>)}]{[<<[]()><()()>>[({}<>){[]{}}]][<<()()>[<>]>{{()<>}}]}>})]>}))({
diff --git a/2021/day10/main.rs b/2021/day10/main.rs
@@ -0,0 +1,90 @@
+fn main() {
+ let input = std::fs::read_to_string("input.txt")
+ .unwrap()
+ .trim()
+ .split('\n')
+ .map(|s| s.to_string())
+ .collect::<Vec<_>>();
+ // 311895
+ println!("Part 1: {}", part_1(&input));
+ // 2904180541
+ println!("Part 2: {}", part_2(&input));
+}
+
+enum MatchResult {
+ Pair,
+ Stack,
+ Illegal(u64),
+}
+
+fn check_match(a: Option<&char>, b: char) -> MatchResult {
+ match (a, b) {
+ (Some('('), ')') | (Some('['), ']') | (Some('{'), '}') | (Some('<'), '>') => {
+ MatchResult::Pair
+ }
+ (None | Some('(' | '[' | '{' | '<'), '(' | '[' | '{' | '<') => MatchResult::Stack,
+ _ => MatchResult::Illegal(match b {
+ ')' => 3,
+ ']' => 57,
+ '}' => 1197,
+ '>' => 25137,
+ _ => unreachable!(),
+ }),
+ }
+}
+
+fn part_1(input: &Vec<String>) -> u64 {
+ let mut tot_score = 0;
+ for line in input {
+ let mut stack = std::collections::VecDeque::<char>::new();
+ for ch in line.chars() {
+ match check_match(stack.back(), ch) {
+ MatchResult::Pair => {
+ stack.pop_back();
+ }
+ MatchResult::Stack => {
+ stack.push_back(ch);
+ }
+ MatchResult::Illegal(score) => {
+ tot_score += score;
+ break;
+ }
+ }
+ }
+ }
+ tot_score
+}
+
+fn part_2(input: &Vec<String>) -> u64 {
+ let mut scores = Vec::<u64>::new();
+ 'next_line: for line in input {
+ let mut stack = std::collections::VecDeque::<char>::new();
+ for ch in line.chars() {
+ match check_match(stack.back(), ch) {
+ MatchResult::Pair => {
+ stack.pop_back();
+ }
+ MatchResult::Stack => {
+ stack.push_back(ch);
+ }
+ MatchResult::Illegal(_) => {
+ continue 'next_line;
+ }
+ }
+ }
+ let mut score = 0;
+ for ch in stack.iter().rev() {
+ score = score * 5
+ + match ch {
+ '(' => 1,
+ '[' => 2,
+ '{' => 3,
+ '<' => 4,
+ _ => unreachable!(),
+ };
+ }
+ scores.push(score);
+ }
+ scores.sort();
+ scores[scores.len() / 2]
+}