Advent of Code 2017 Day 19
Part 1
- This seems familiar...
- Could I just eyeball it?
- How many letters are in my puzzle input?
- Deciding not to solve it manually
- 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:
- 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 - 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
- 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)