Digital Plumber

Advent of Code 2017 Day 12

Part 1

1. One to many...again
2. Building the dictionary
3. 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

1. One to many...again?!
2. 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!

Comments

[Carl Eliezer]

Unquestionably a wonderful effort! It is uplifting to read such well-reasoned and articulate ideas. It was masterfully written and entertaining. For more information and expert assistance, go to SEO Services in Riverside.

[lastreaction]

Thank you for this APi. It is very helpful for my Sell Game Console business

[Carl]

You're doing some really great stuff here. It's been a long time since I've read an article so masterfully written. You have my gratitude for creating this! Please also take some time to look into Security Guard Services in Riverside.