1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167

//! # Day 9: Stream Processing
//!
//! A large stream blocks your path. According to the locals, it's not safe to cross the stream at
//! the moment because it's full of **garbage**. You look down at the stream; rather than water, you
//! discover that it's a **stream of characters**.
//!
//! You sit for a while and record part of the stream (your puzzle input). The characters represent
//! **groups** - sequences that begin with `{` and end with `}`. Within a group, there are zero or
//! more other things, separated by commas: either another **group** or **garbage**. Since groups
//! can contain other groups, a `}` only closes the **most-recently-opened unclosed group** - that
//! is, they are nestable. Your puzzle input represents a single, large group which itself contains
//! many smaller ones.
//!
//! Sometimes, instead of a group, you will find **garbage**. Garbage begins with `<` and ends with
//! `>`. Between those angle brackets, almost any character can appear, including `{` and `}`.
//! **Within** garbage, `<` has no special meaning.
//!
//! In a futile attempt to clean up the garbage, some program has **canceled** some of the
//! characters within it using `!`: inside garbage, any character that comes after `!` should be
//! ignored, including `<`, `>`, and even another `!`.
//!
//! You don't see any characters that deviate from these rules. Outside garbage, you only find
//! well-formed groups, and garbage always terminates according to the rules above.
//!
//! Here are some self-contained pieces of garbage:
//!
//! - `<>`, empty garbage.
//! - `<random characters>`, garbage containing random characters.
//! - `<<<<>`, because the extra `<` are ignored.
//! - `<{!>}>`, because the first `>` is canceled.
//! - `<!!>`, because the second `!` is canceled, allowing the `>` to terminate the garbage.
//! - `<!!!>>`, because the second `!` and the first `>` are canceled.
//! - `<{o"i!a,<{i<a>`, which ends at the first `>`.
//!
//! Here are some examples of whole streams and the number of groups they contain:
//!
//! - `{}`, `1` group.
//! - `{{{}}}`, `3` groups.
//! - `{{},{}}`, also `3` groups.
//! - `{{{},{},{{}}}}`, `6` groups.
//! - `{<{},{},{{}}>}`, `1` group (which itself contains garbage).
//! - `{<a>,<a>,<a>,<a>}`, `1` group.
//! - `{{<a>},{<a>},{<a>},{<a>}}`, `5` groups.
//! - `{{<!>},{<!>},{<!>},{<a>}}`, `2` groups (since all but the last `>` are canceled).
//!
//! Your goal is to find the total score for all groups in your input. Each group is assigned a
//! **score** which is one more than the score of the group that immediately contains it. (The
//! outermost group gets a score of `1`.)
//!
//! - `{}`, score of `1`.
//! - `{{{}}}`, score of `1 + 2 + 3 = 6`.
//! - `{{},{}}`, score of `1 + 2 + 2 = 5`.
//! - `{{{},{},{{}}}}`, score of `1 + 2 + 3 + 3 + 3 + 4 = 16`.
//! - `{<a>,<a>,<a>,<a>}`, score of `1`.
//! - `{{<ab>},{<ab>},{<ab>},{<ab>}}`, score of `1 + 2 + 2 + 2 + 2 = 9`.
//! - `{{<!!>},{<!!>},{<!!>},{<!!>}}`, score of `1 + 2 + 2 + 2 + 2 = 9`.
//! - `{{<a!>},{<a!>},{<a!>},{<ab>}}`, score of `1 + 2 = 3`.
//!
//! **What is the total score** for all groups in your input?
//!
//! ## Part Two
//!
//! Now, you're ready to remove the garbage.
//!
//! To prove you've removed it, you need to count all of the characters within the garbage. The
//! leading and trailing `<` and `>` don't count, nor do any canceled characters or the `!` doing
//! the canceling.
//!
//! - `<>`, `0` characters.
//! - `<random characters>`, `17` characters.
//! - `<<<<>`, `3` characters.
//! - `<{!>}>`, `2` characters.
//! - `<!!>`, `0` characters.
//! - `<!!!>>`, `0` characters.
//! - `<{o"i!a,<{i<a>`, `10` characters.
//!
//! **How many non-canceled characters are within the garbage** in your puzzle input?

use anyhow::{Context, Result};

pub const INPUT: &str = include_str!("d09.txt");

pub fn solve_part_one(input: &str) -> Result<i64> {
    let chars = parse_input(input)?;
    let mut level = 0;
    let mut garbage = false;
    let mut skip = false;
    let mut score = 0;

    for c in chars {
        if skip {
            skip = false;
            continue;
        }
        match c {
            '!' => skip = true,
            '<' => garbage = true,
            '>' => garbage = false,
            '{' if !garbage => {
                level += 1;
                score += level;
            }
            '}' if !garbage => level -= 1,
            _ => {}
        }
    }

    Ok(score)
}

pub fn solve_part_two(input: &str) -> Result<i64> {
    let chars = parse_input(input)?;
    let mut garbage = false;
    let mut skip = false;
    let mut count = 0;

    for c in chars {
        if skip {
            skip = false;
            continue;
        }
        match c {
            '!' => skip = true,
            '<' if !garbage => garbage = true,
            '>' => garbage = false,
            _ => {
                if garbage {
                    count += 1;
                }
            }
        }
    }

    Ok(count)
}

fn parse_input(input: &str) -> Result<impl Iterator<Item = char> + '_> {
    Ok(input.lines().next().context("excepcted exactly 1 line of input")?.chars())
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn part_one() {
        assert_eq!(1, solve_part_one("{}").unwrap());
        assert_eq!(6, solve_part_one("{{{}}}").unwrap());
        assert_eq!(5, solve_part_one("{{},{}}").unwrap());
        assert_eq!(16, solve_part_one("{{{},{},{{}}}}").unwrap());
        assert_eq!(1, solve_part_one("{<a>,<a>,<a>,<a>}").unwrap());
        assert_eq!(9, solve_part_one("{{<ab>},{<ab>},{<ab>},{<ab>}}").unwrap());
        assert_eq!(9, solve_part_one("{{<!!>},{<!!>},{<!!>},{<!!>}}").unwrap());
        assert_eq!(3, solve_part_one("{{<a!>},{<a!>},{<a!>},{<ab>}}").unwrap());
    }

    #[test]
    fn part_two() {
        assert_eq!(0, solve_part_two("<>").unwrap());
        assert_eq!(17, solve_part_two("<random characters>").unwrap());
        assert_eq!(3, solve_part_two("<<<<>").unwrap());
        assert_eq!(2, solve_part_two("<{!>}>").unwrap());
        assert_eq!(0, solve_part_two("<!!>").unwrap());
        assert_eq!(0, solve_part_two("<!!!>>").unwrap());
        assert_eq!(10, solve_part_two("<{o\"i!a,<{i<a>").unwrap());
    }
}