DEV Community

Cover image for Stream Processing
Robert Mion
Robert Mion

Posted on

Stream Processing

#adventofcode #algorithms #computerscience #programming

Advent of Code 2017 Day 9

Try the simulator using your puzzle input!

Final moments of simulator

Part 1

  1. Walking the line...again
  2. A for loop and a flag
  3. Writing and testing my algorithm

Walking the line...again

I'm reminded of 2021 Day 10: Syntax Scoring

A few differences:

  • Syntax Scoring was a list of strings; this puzzle features one long string
  • Syntax Scoring started with identifying corrupted strings: where an opening symbol was properly closed; this puzzle features a correct string...filled with garbage!
  • Syntax Scoring was a challenge of tracking and matching opening and closing symbols of the same type; this puzzle is similar, but with more to track given the inclusion of garbage data
  • Syntax Scoring algorithm walked the string; I anticipate doing the same in this puzzle

A for loop and a flag

I think those will be the core aspects of my algorithm:

Initialize a flag for garbage mode to false For each character in the string If in garbage mode Check for exclamation marks If one is encountered, skip a character Keep walking If not in garbage mode If next character is < Enter garbage mode Else, if next character is { Account for another group, possibly at the same or next level Else if next character is } Update the accumulating score to account for the group that just closed Else if next character is anything else Keep walking
Enter fullscreen mode Exit fullscreen mode

There's probably some finer details in the conditions that I'm missing, but that's an outline of the algorithm I intend to write.

Let's see how far off I was...assuming I can write a working algorithm!

Writing and testing my algorithm

Thankfully, the instructions offer plenty of unit tests.

I'm going to write this algorithm piece by piece, condition by condition, ensuring I pass some simpler tests, then the more complicated ones...then hopefully my puzzle input.

Getting examples 1-4 to work 

{} = 1 {{{}}} = 6 {{},{}} = 5 {{{},{},{{}}}} = 16
Enter fullscreen mode Exit fullscreen mode

My working algorithm:

Setup: Split the input at each character into an array of characters Create score, starting at 0 Create level, starting at 1 Loop: For each character in the stream except the last Depending on what the next character is: If it is a { Increment level by 1 Else, if it is a } Increment score by level Decrement level Return score
Enter fullscreen mode Exit fullscreen mode

Now, to start accounting for garbage.

Getting example 6, 7 and 9 to work 

{<a>,<a>,<a>,<a>} = 1 {{<a>},{<a>},{<a>},{<a>}} = 9 {{<ab>},{<ab>},{<ab>},{<ab>}} = 9
Enter fullscreen mode Exit fullscreen mode

My working algorithm:

Setup: Split the input at each character into an array of characters Create score, starting at 0 Create level, starting at 1 Create flag for garbage mode, starting at false Loop: For each character in the stream except the last Depending on what the next character is: If garbage mode is on If it is a > Turn garbage mode off Else, garbage mode is off If it is a { Increment level by 1 Else, if it is a } Increment score by level Decrement level Else, if it is a < Turn garbage mode on Return score
Enter fullscreen mode Exit fullscreen mode

Getting examples 8, 10 and 11 to work 

{{<!>},{<!>},{<!>},{<a>}} = 3 {{<!!>},{<!!>},{<!!>},{<!!>}} = 9 {{<a!>},{<a!>},{<a!>},{<ab>}} = 3
Enter fullscreen mode Exit fullscreen mode

My working algorithm:

Setup: Split the input at each character into an array of characters Create score, starting at 0 Create level, starting at 1 Create flag for garbage mode, starting at false Loop: For each character in the stream except the last Depending on what the next character is: If garbage mode is on If it is a > Turn garbage mode off If it is a ! Increment the character location tracker by 1 to skip a character in the stream Else, garbage mode is off If it is a { Increment level by 1 Else, if it is a } Increment score by level Decrement level Else, if it is a < Turn garbage mode on Return score
Enter fullscreen mode Exit fullscreen mode

Testing on my puzzle input

  • It finished!
  • It generated the correct answer!

Part 2

  1. Garbage collection, of course!

Garbage collection, of course!

I'm hopeful I just need to add a tracking counter, and a statement that increments it by one in the proper case in one of my switch statements.

My working algorithm:

Setup: Split the input at each character into an array of characters Create score, starting at 0 Create level, starting at 1 Create flag for garbage mode, starting at false Create garbage, starting at 0 Loop: For each character in the stream except the last Depending on what the next character is: If garbage mode is on If it is a > Turn garbage mode off If it is a ! Increment the character location tracker by 1 to skip a character in the stream Otherwise Increment garbage by 1 Else, garbage mode is off If it is a { Increment level by 1 Else, if it is a } Increment score by level Decrement level Else, if it is a < Turn garbage mode on Return garbage
Enter fullscreen mode Exit fullscreen mode

That's all it took to generate the correct answer for Part 2!

I did it!!

  • I solved both parts!
  • I did so by writing my algorithm piece by piece, solving only a few examples at a time
  • I used a few switch statements, which I don't use too often throughout these puzzles; I often opt for dictionaries so I can leverage key-value look-ups
  • I built a simulator to watch the stream get processed in front of my eyes!

I'm glad I didn't try solving this puzzle all at once, or I may have struggled more than necessary.

Top comments (0)