A Series of Tubes
Tags: adventofcode, algorithms, computerscience, programming
Published: 2022-07-25 17:05:11

## [Advent of Code 2017 Day 19](https://adventofcode.com/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](https://adventofcode.com/2018/day/13)
- 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:
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7dgehdqyvu425wpfuomq.gif)

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:
![Legend for directional change](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/twgndwdthglocuo8s2cl.jpg)

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