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:
[[-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 #]
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.

Heroku

Build apps, not infrastructure.

Dealing with servers, hardware, and infrastructure can take up your valuable time. Discover the benefits of Heroku, the PaaS of choice for developers since 2007.

Visit Site

Top comments (0)

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay