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 two 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        let (open, score) = match b {
47            b'(' | b'[' | b'{' | b'<' => {
48                stack.push(b);
49                continue;
50            }
51            b')' => (b'(', 3),
52            b']' => (b'[', 57),
53            b'}' => (b'{', 1197),
54            b'>' => (b'<', 25137),
55            _ => unreachable!(),
56        };
57        if stack.pop().unwrap() != open {
58            return score;
59        }
60    }
61
62    0
63}
64
65fn autocomplete_score(stack: &[u8]) -> u64 {
66    stack.iter().rev().fold(0, |acc, &b| {
67        let score = match b {
68            b'(' => 1,
69            b'[' => 2,
70            b'{' => 3,
71            b'<' => 4,
72            _ => unreachable!(),
73        };
74        5 * acc + score
75    })
76}
aoc/year2021/day10.rs

aoc/year2021/
day10.rs
