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

puts score(File.read("9.txt"))

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

puts score(File.read("9.txt"))

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.