Advent of Code 2017 Day 12
Part 1
- One to many...again
- Building the dictionary
- Writing and testing my working algorithm
One to many...again
- I'm reminded of those Handy Haversacks
- And another puzzle, but I can't recall the name or day
- Regardless, this should be another fun exercise in building a dictionary and re-iterating until I've caught 'em all!
Building the dictionary
The pattern is one-to-many:
2 <-> 0, 3, 4
3 <-> 2, 4
5 <-> 6
The parts I need to extract are digits only. That makes for a simple regular expression:
/\d+/g
That will get me each digit in a line.
Per the instructions, a line like this:
2 <-> 0, 3, 4
Seems like it means:
- 2 can communicate with 0, 3, 4
- 0 can communicate with 2, 3, 4
- 3 can communicate with 0, 2, 4
- 4 can communicate with 0, 2, 3
Thus:
For each number in the line
Create or add to a set of unique values it can communicate with each of the other numbers
How would that look for the example input?
0 <-> 2
1 <-> 1
2 <-> 0, 3, 4
3 <-> 2, 4
4 <-> 2, 3, 6
5 <-> 6
6 <-> 4, 5
Like this?
0: 2, 3, 4
2: 0, 3, 4, 6
1: 1
3: 0, 2, 4, 6
4: 0, 2, 3, 6, 5
6: 2, 3, 4, 5
5: 6, 4
I need another iteration to fill out 0 where I attempt to add each number found in each of the sets associated with each number in 0:
0: 2 (+6), 3, 4 (+5)
Perhaps my algorithm could look back to 0 for all numbers, and if 0 has them, also add the numbers stored in that number and in the current line?
That gets tricky because many numbers will not have been added to the dictionary at the time of look-up.
I think I have enough understanding to attempt writing an algorithm that implements this regular expression and dictionary data structure.
Writing and testing my working algorithm
Split the input at each newline character into an array of strings
For each string, populate a dictionary
Use the regular expression to extract all the digits
For each digit as i
For each digit as j
As long as i is not j
If the digit is not yet a key in the dictionary
Create a key for it and set the value to a unique Set
Add the digit j to the unique set if not already part of the Set
Create a counter to track the size of the Set associated with the key, 0
Initialize it to the current size, after the dictionary is done being constructed
Do at least once, and as long as counter is less than the new size of the Set associated with the key, 0
For each number in the Set associated with 0
Attempt to add each number in the Sets associated with the current number to the Set associated with 0
Testing the results:
- It worked on the example input!
- It worked on my puzzle input!
Part 2
- One to many...again?!
- Writing and testing my working algorithm
One to many...again?!
This should be a fun process of elimination: of keys, literally.
My plan:
Run the algorithm from Part 1 to identify all members in a group shared by `0`
Delete each of those keys from the dictionary
Run the algorithm from Part 1 on the next key in the dictionary
Delete each of the keys identified as part of that dictionary
Go until there are no other keys to evaluate
Count the number of keys remaining in the dictionary
Writing and testing my working algorithm
My planned algorithm had me doing an important part too soon, and missed another important part.
This is the algorithm that worked:
Split the input at each newline character into an array of strings
For each string, populate a dictionary
Use the regular expression to extract all the digits
For each digit as i
For each digit as j
As long as i is not j
If the digit is not yet a key in the dictionary
Create a key for it and set the value to a unique Set
Add the digit j to the unique set if not already part of the Set
Create a counter to track the number of groups identified
For each key in the dictionary
Create a counter to track the size of the Set associated with the key
Initialize it to the current size
Do at least once, and as long as counter is less than the new size of the Set associated with the key
For each number in the Set associated with the key
Attempt to add each number in the Sets associated with the current number to the Set associated with the key
Remove the number in its Set that is equal to the key
Delete each key in the dictionary bearing the same alias as each number in this key's set of values
Increment the group counter by 1
Return the group counter's value
This GIF shows how my algorithm for Parts 1 and 2 work:
Testing the results:
- It worked on the example input!
- It worked on my puzzle input!
I did it!!
- I solved both parts!
- I made a GIF that shows how my algorithm solves both parts!
- After making the GIF, I removed a few redundant loops in my Part 2 algorithm, so it runs much faster!
Top comments (2)
Some comments may only be visible to logged-in visitors. Sign in to view all comments.