aoc/year2021/
day10.rs

1//! # Syntax Scoring
2//!
3//! This day is a variation of the classic parentheses balancing problem. To solve we use a `vec`
4//! as a stack, pushing opening delimiters onto the stack, then popping the top of the stack
5//! whenever we encounter a closing delimiter. If there is a mismatch between opening and closing
6//! delimiters then we return the specified error value immediately.
7//!
8//! For part 2 the completion score is the remaining items on the stack, reversed and converted from
9//! corresponding closing delimiters. For example the completion string `])}>` would have a stack
10//! that looks like `<{([`, where the right hand side is the top of the stack.
11type Input = (u64, u64);
12
13pub fn parse(input: &str) -> Input {
14    let mut stack = Vec::new();
15    let mut scores = Vec::new();
16    let mut part_one = 0;
17
18    for line in input.lines() {
19        let score = syntax_score(line, &mut stack);
20
21        if score == 0 {
22            scores.push(autocomplete_score(&stack));
23        } else {
24            part_one += score;
25        }
26
27        stack.clear();
28    }
29
30    scores.sort_unstable();
31    let part_two = scores[scores.len() / 2];
32
33    (part_one, part_two)
34}
35
36pub fn part1(input: &Input) -> u64 {
37    input.0
38}
39
40pub fn part2(input: &Input) -> u64 {
41    input.1
42}
43
44fn syntax_score(line: &str, stack: &mut Vec<u8>) -> u64 {
45    for b in line.bytes() {
46        match b {
47            b'(' | b'[' | b'{' | b'<' => stack.push(b),
48            b')' => {
49                if stack.pop().unwrap() != b'(' {
50                    return 3;
51                }
52            }
53            b']' => {
54                if stack.pop().unwrap() != b'[' {
55                    return 57;
56                }
57            }
58            b'}' => {
59                if stack.pop().unwrap() != b'{' {
60                    return 1197;
61                }
62            }
63            b'>' => {
64                if stack.pop().unwrap() != b'<' {
65                    return 25137;
66                }
67            }
68            _ => unreachable!(),
69        }
70    }
71
72    0
73}
74
75fn autocomplete_score(stack: &[u8]) -> u64 {
76    fn helper(b: u8) -> u64 {
77        match b {
78            b'(' => 1,
79            b'[' => 2,
80            b'{' => 3,
81            b'<' => 4,
82            _ => unreachable!(),
83        }
84    }
85    stack.iter().rev().fold(0, |acc, &b| 5 * acc + helper(b))
86}
aoc/year2021/day10.rs

aoc/year2021/
day10.rs
