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.
11pub fn parse(input: &str) -> Vec<&[u8]> {
12    input.lines().map(str::as_bytes).collect()
13}
14
15pub fn part1(input: &[&[u8]]) -> u64 {
16    let mut stack = Vec::new();
17    let mut score = 0;
18
19    for line in input {
20        score += syntax_score(line, &mut stack);
21        stack.clear();
22    }
23
24    score
25}
26
27pub fn part2(input: &[&[u8]]) -> u64 {
28    let mut stack = Vec::new();
29    let mut scores = Vec::new();
30
31    for line in input {
32        if syntax_score(line, &mut stack) == 0 {
33            scores.push(autocomplete_score(&stack));
34        }
35        stack.clear();
36    }
37
38    scores.sort_unstable();
39    scores[scores.len() / 2]
40}
41
42fn syntax_score(line: &[u8], stack: &mut Vec<u8>) -> u64 {
43    for &b in line {
44        match b {
45            b'(' | b'[' | b'{' | b'<' => stack.push(b),
46            b')' => {
47                if stack.pop().unwrap() != b'(' {
48                    return 3;
49                }
50            }
51            b']' => {
52                if stack.pop().unwrap() != b'[' {
53                    return 57;
54                }
55            }
56            b'}' => {
57                if stack.pop().unwrap() != b'{' {
58                    return 1197;
59                }
60            }
61            b'>' => {
62                if stack.pop().unwrap() != b'<' {
63                    return 25137;
64                }
65            }
66            _ => unreachable!(),
67        }
68    }
69
70    0
71}
72
73fn autocomplete_score(stack: &[u8]) -> u64 {
74    fn helper(b: u8) -> u64 {
75        match b {
76            b'(' => 1,
77            b'[' => 2,
78            b'{' => 3,
79            b'<' => 4,
80            _ => unreachable!(),
81        }
82    }
83    stack.iter().rev().fold(0, |acc, &b| 5 * acc + helper(b))
84}
aoc/year2021/day10.rs

aoc/year2021/
day10.rs
