Recursive Circus

Advent of Code 2017 Day 7

Part 1

1. Finding a needle in a haystack...with brute-force
2. My terribly-performing, working algorithm

Finding a needle in a haystack...with brute-force

• I need to find the name of the bottom program
• That is the only program with no parent
• Do I need to build a tree data structure to find it?
• I don't think so
• I don't even need any regular expressions!
• Instead, I think I can use nested loops to compare each tower string to all the others...in search of the matching tower!

My terribly-performing, working algorithm

Split the input at each newline character into an array of strings

Set bottom as empty

For each string
  Split the string at each space character into an array of strings
    Store the first element in the array of strings as the current tower name
  For each string, again
    Check whether the string either starts with the current tower name, or contains the current tower name
    Filter the resulting list of booleans to only include false: meaning the string either started with the current tower name or it contains the current tower name
    Return true if the length of the list is 1: a single false matches the string where the current tower is referenced as the first tower name
  If the above operations returned true, update bottom to the name of the current tower

Return the string stored in bottom

My puzzle input contains roughly 1500 towers.

So, this algorithm's worst case was to run 2.25M times!

Terrible, I know.

But...it generated the correct answer!

Part 2

1. Now for the real challenge!
2. Solving Part 1 faster in preparation for solving Part 2
3. Attempt #1: Solving Part 2 top-down
4. Attempt #2: Solving Part 2 bottom-up

Now for the real challenge!

• Regular expressions? Likely.
• Recursion? Probably.
• Arithmetic? Definitely.
• Some sort of object mimicking a tree data structure? Most certainly.

Solving Part 1 faster in preparation for solving Part 2

I intend to build a data structure like this:

{
  tknk: {
    weight: 41,
    parent: null,
    children: [ugml, padx, fwft]
  },
  // ...
}

After parsing the full input string:

• It will have as many keys as lines in my puzzle input
• Only one key will have parent: null
• Finding that key should take no time at all...compared to my Part 1 algorithm
• Best of all, I'll have a flat data structure to perform look-ups in the algorithm I intend to write for Part 2!

Here I go!

...

After the following troubleshooting:

• Being careful when initializing the object - I should not void any existing key-value pairs
• Being sure to check in all conditions for an existing object, and create one if none exists
• Setting each property individually and under the proper condition - even if being redundant

I had a dependable quasi-database of each tower with these as the patterns of objects:

{
  'tower': {
     parent: 'tower',
     children: ['tower','tower','tower']
     weight: number
  },
  'tower': {
     children: ['tower','tower','tower']
     weight: number
  },
  'tower': {
     parent: 'tower',
     weight: number
  },
}

Now, searching for the bottom tower took barely a millisecond, since it was only ~1500 operations...as compared to my original 2.5M operations in the worst-case scenario

Here's how my faster Part 1 algorithm works on the example input:

Fail: Solving Part 2 top-down

I wrongly presumed the following about the towers:

• That the tree is perfectly balanced in relation to the number of branches and the number of nodes in each branch

How'd I determine this? Well, it took about an hour.

This is my algorithm:

Generate a list of all towers with no children: the `leaf` nodes, or `tops` in this context

For each of those towers
  Add a key, total_weight, whose value is the same as the weight

For each of those towers, again
  Store a reference to the parent tower
  For each tower in the parent tower's list of child towers
    Update the tower name to the tower's weight
  Create a unique set of values from each weight
  If that set's size is 1
    All weights are identical and the sub-tower is balanced
  Else
    I found the unbalanced tower!

When running it and displaying messages for balanced or unbalanced:

• I unexpectedly saw many unbalanced messages

What was going on?

• I added print statements to see the weights of each child tower
• Many were undefined

How could that be?

• I added print statements to see the names of one parent's child towers
• Some of them had children!

All of this revealed to me:

• I can't solve this puzzle top-down (meaning from the leaf nodes toward the root node)
• Instead, I'll have to start from the children of the root node and work recursively down through the towers...
• ...as the puzzle's name and instructions suggest

Attempt #2: Solving Part 2 bottom-up

• This was a real struggle
• I kept confusing myself about what to return in each recursion
• Then, I feel like I overcomplicated the process of identifying the wrong number and determining what it should be

After a few hours, I wrote a working algorithm, which is mostly animated below:

An outline of how it works:

The recursive function:
  Expect one parameter: an array of child tower names
  The base case:
    An empty array as argument
      Return 0
  Otherwise:
    For each child tower name
      Change the name to a number that is the sum of:
        1. That tower's weight
        2. Calling the recursive function with that tower's children, or an empty array if it has no children
    Create a set of unique values from the updated array
    If the set has more than one unique value, I found the wrong number!
      Create an object that will tally each number in the updated array
      Set wrong to the key who's tally is 1
      Set right to the key who's tally is not 1
      Get the location of the wrong number in the updated array, and use it to get the tower in the same location in the original input array, then get that tower's weight
      Determine whether the wrong number is larger or smaller than the right number
      Set as answer the tower's weight changed by the difference between the wrong and right numbers...using the correct sign (positive/negative)

Call the recursive function
  Pass as argument the bottom tower's children

Since I don't break out the function the moment it finds a wrong number, it finds a few wrong numbers.

That's because the first wrong number is in a sub-tower, which causes a few lower towers to contain a wrong number as well.

My algorithm prints out each answer.

I used the first instance, since that is the number that, when corrected, fixes the other lower ones.

I did it!!

• I solved both parts!
• I solved Part 1 two ways, one way faster than the other!
• I made GIFs of both my working, well-performing algorithms!
• I discovered why I couldn't solve Part 2 the way I wanted...only to come away triumphant at solving it the way the author seemed to intend!

Recursion remains rather intimidating to me.

Thankfully, I bested it again this round.

Even better:

• As I exit Day 7, I have 34 stars!
• That's my lowest score, shared by two other years!
• That means that if I score another star, I'll tie my second lowest score!
• And if I score 6 more stars, I'll tie my best score!
• And if I score at least 7 stars, I'll achieve a new personal best score!

I'm very motivated to finish the year with more than 40 stars!