Advent of Code 2017, Day 9: Stream Processing

Part A

On Day 9 we parsing streams of characters wrapped in brackets. There are two types of brackets. `{` and `}` represent groups while `<` and `>` represent garbage. There is also escape character `!` that ignores the following characters. Groups can be nested.

Here are some examples of groups:

• `{}`, 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).

The goal is find the total score for all groups. The first groups gets the score of 1 and the next nested groups get score one higher than the more outer group. Again some examples:

• `{}`, 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.

Here is the solution:

``````def score(stream)
score = 0
total = 0
garbage = false
escape = false

stream.each_char do |char|
if garbage
if escape
escape = false
next
end

if char == ">"
garbage = false
elsif char == "!"
escape = true
end
else
if char == "{"
score += 1
total += score
elsif char == "}"
score -= 1
elsif char == "<"
garbage = true
end
end
end

total
end

``````

Here we are just reading consecutive characters and respond to certain characters and skip the rest. We also maintain two flags describing the current state of the parser. `garbage` flag tells us if parser is in garbage mode or not. We can enter garbage mode when we read `<` character and go back to normal mode when we read `>` character.

Another flag is `escape` that is activated when we read escape character `!` and it is cleared after next character.

We use `score` variable to track the score of the current group. It starts with one and whenever we read `{` character in normal mode we increase this score by one. And we also add it to our total score. If we read `}` character it means we are leaving the group so we need to decrease the score of current group by 1.

Part B

The goal in the second part is to tell how many non-canceled characters are within the garbage.

Here is the solution:

``````def score(stream)
counter = 0
garbage = false
escape = false

stream.each_char do |char|
if garbage
if escape
escape = false
next
end

if char == ">"
garbage = false
elsif char == "!"
escape = true
else
counter += 1
end
else
if char == "<"
garbage = true
end
end
end

counter
end

We are using the solution from the first part. This time we are interested only in the garbage part of the stream and we need to count non-canceled characters. In the first part when in garbage mode we were responding to `>` and `!` characters and adjusting the flags. Now we need to respond to any other character in garbage mode and just increase our counter.