DEV Community

Cover image for A Series of Tubes
Robert Mion
Robert Mion

Posted on

A Series of Tubes

Advent of Code 2017 Day 19

Part 1

  1. This seems familiar...
  2. Could I just eyeball it?
  3. How many letters are in my puzzle input?
  4. Deciding not to solve it manually
  5. Solving it algorithmically

This seems familiar...

  • I'm reminded of 2020 Day 13 - Mine Cart Madness
  • Surprisingly - thankfully? - this puzzle has just one moving object: a packet
  • Also different: the corner markers - + instead of / and \

Could I just eyeball it?

  • My puzzle input is large, yes
  • But it doesn't look like there are many letters
  • And with careful study and patience, I could probably follow the tubes with my eyes, recording the letters as I see them

Before I do that, a few exercises.

How many letters are in my puzzle input?

I could do this one of two ways:

  1. Use the Find... web browser feature when viewing the raw puzzle input, searching for and recording each capitalized letter of the alphabet, tallying them as I go
  2. Write an algorithm

Option two seems far more exciting.

My algorithm works like this:

Generate a 2D array representing the tubes:
  Split the input at each newline character into an array of strings
    Split each string at each character into an array of characters

Identify the letters:
  For each row, accumulate an array of characters
    For each columns, accumulate an array of characters
      If the character is not one of these: `-,|,+, `
        Insert the character into the array
Enter fullscreen mode Exit fullscreen mode

It works on the example input: ACFEDB

It works on my puzzle input: DRSFXNPJLZ

Wow! Only 11 letters!

I could probably solve this part manually!

If I do, I would want to make a GIF.

Deciding not to solve it manually

  • I'd have to work on a very small, rotated copy of my puzzle input
  • Drawing lines carefully and continually over more and more of the tube tracks
  • My mouse is kind of finicky, so that would probably be a frustrating process
  • I'm not feeling great about this

I'd much rather solve it algorithmically.

Then, build a simulator that showed the packet moving through the tubes.

Solving it algorithmically

Ingredients for my algorithm recipe:

  • Each tile in the grid: that will be a 2D array of characters
  • The number of letters to collect: that will be the length of the list of letters found in the grid
  • The current location and direction of the packet: that will be a 3-element array where the first two elements are the row and column and the third element is one of four characters: v^<>
  • The relative coordinates of each next location based on the direction: that will be a dictionary where the keys are the four characters above and the values are 2-element arrays with 0, 1 or -1 for the relative row and column
  • An initially empty unique set that will eventually store all the collected letters

The main loop:

Do as long as the size of the set of collected letters is not equal to the number of letters in the tubes
  Check the character in the next tube
    If it's a letter:
      Add that letter to the set and continue in the current direction
    Else, if it's a +:
      Determine which of the four tiles adjacent to the + must be the next tube
      If the character at that tile is a letter, add the letter to the set
      Update the direction to account for turning a corner
    Else (meaning it's a - or |):
      Continue in the current direction
Enter fullscreen mode Exit fullscreen mode

That all seems straightforward.

But a few details required more code than I was expecting.

Determine which of the four tiles adjacent to the + must be the next tube

This animation depicts how my algorithm works:
Image description

In more written detail:

Start with a list of the four relative adjacent coordinates:

Filter that list to exclude the pair that corresponds to the current location of the packet

Change each coordinate into a 3-element array with this blueprint:
['character', row #, column #]

Filter that list to exclude the two items where 'character' is a space

Alas, we now have a 1-item array! Flatten it, resulting in:
['character', row #, column #]
Enter fullscreen mode Exit fullscreen mode

Update the direction to account for turning a corner

Now that I know the location and character of the next tube that the packet should occupy, I need to:

  • Move the packet there
  • Update the packet's direction
  • Record the letter at that spot if there is one

I used a switch statement to update the packet's direction.

Depending on the packet's direction, and either the row or column of the next tube, update the direction according to the following diagram:
Legend for directional change

Testing my algorithm

There was quite a bit of troubleshooting:

  • I incorrectly referred to rows instead of columns in one place
  • I incorrectly referenced an index in some places
  • I collected each number twice

Eventually, my algorithm finished, having collected each letter using the example input and my puzzle input.

I'm debating whether it would be fun to watch in a simulator.

Before I do, I'm anxious to see how much more difficult Part 2 is...

Part 2

  1. Woah! That's it??!!

Woah! That's it??!!

  • Add a variable to track the number of steps
  • Increment that variable in three places throughout my loop
  • Run it on the example: success!
  • Run it on my input: success!

I did it!!

  • I solved both parts!
  • I made a GIF to describe one of my smaller algorithms
  • I've now bested my star count by this point for any year!

I opted not to make a simulator.

I'm more excited to attempt the next puzzle than I am to spend even an hour making one for this puzzle.

Top comments (0)