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

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

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:

In more written detail:

Start with a list of the four relative adjacent coordinates:
[[-1,0],[0,1],[1,0],[0,-1]]

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 #]

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:

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.