Balance Bots

Advent of Code 2016 Day 10

Part 1

1. Passing the buck
2. Building a bots dictionary
3. Confirming there's one bot with two values
4. Transferring microchips to other bots
5. Confirming successful transfers with the example input
6. I assumed wrong, but the fix was easy
7. Confirming successful transfers with my puzzle input

Passing the buck

• A dictionary of bots
• Each one has an id, a queue of microchip values - max of 2
• and a pair of rules
• I presume only one bot will start with two values
• From there, it seems like an iterative process of value-passing

Building a bots dictionary

My input has lines like these:

bot 125 gives low to output 4 and high to bot 29
value 41 goes to bot 204
bot 69 gives low to bot 197 and high to bot 15
bot 0 gives low to bot 207 and high to bot 110

The important bits:

• Whether its a value assignment or a bot rule
• bot id
• each of the bot's recipient types
• ids of the bot's recipients

An overly prescriptive approach:

Set bots as a dictionary
Split each line at the space character into an array of words
  If the array's length is 6 - its a value
    Create or update a key in bots associated with the second number in the array, and set as a key in its dictionary value the first number
  Else - its a bot rule
    Store the id, low recipient and id, high recipient and id
    Create or update a key in bots associated with the id, and set as key-value pairs in its dictionary the mapping of recipient types and ids for each direction

Using the example input:

value 5 goes to bot 2
bot 2 gives low to bot 1 and high to bot 0
value 3 goes to bot 1
bot 1 gives low to output 1 and high to bot 0
bot 0 gives low to output 2 and high to output 0
value 2 goes to bot 2

The resulting bots dictionary should be this:

{
  0: {
    values: [],
    recipients: [ 
      { type: 'output', id: 2 },
      { type: 'output', id: 0 } 
    ]
  },
  1: {
    values: [3],
    recipients: [
      { type: 'output', id: 1 },
      { type: 'bot', id: 0 }
    ]
  },
  2: {
    values: [5, 2],
    recipients: [
      { type: 'bot', id: 1 },
      { type: 'bot', id: 0 }
    ]
  }
}

I can't forget the outputs dictionary:
Any time the recipient is an output, I create a key for it in a dictionary and set its value to 0

{ 0: 0, 1: 0, 2: 0 }

Confirming there's one bot with two values

Iterate through all keys in the bots dictionary
  If there's a bot with a values array with length 2
    Display that bot's dictionary

What I saw using the example input:

{
  values: [ 5, 2 ],
  recipients: [ 
    { type: 'bot', id: 1 }, 
    { type: 'bot', id: 0 } 
  ]
}

What I saw using my puzzle input:

{
  values: [ 17, 5 ],
  recipients: [ 
    { type: 'bot', id: 50 }, 
    { type: 'bot', id: 53 } 
  ]
}

Great! But does this require iterating?

Couldn't I do this check each time a value-assigning line is encountered?

Set next to null

After adding a value to a bot's values array
  If values has a length of 2
    Set next to the id of this bot

Display the dictionary associated with the bot id stored in next

That worked! No need for the iterator!

Transferring microchips to other bots

Once the input is done processing, and I've got my bots and outputs, it's time to transfer microchips.

The loop that will keep this process going is:

Do as long as the values array of the bot id stored in next has a length of 2
  Transfer both microchips elsewhere!

Now, what has to happen?

Sort the values array in ascending order, since that's how I stored each bot's rules
Determine each recipient, to know which dictionary and key to reference
Remove each item from the bot's values array, sending the removed item to the correct recipient
After sending, check whether the recipient is a bot, and whether it's values array now has two items
  If it has two items now, set that bot id as next

In simpler terms:

• Sort
• Check recipient type
• Remove and send
• Update next
• Repeat

Time to write it with code!

Confirming successful transfers with the example input

Using the example as my unit test:

• Start with bot 2: check
• bot 2 values removed after transfer: check
• Next is bot 1: check
• bot 1 has anticipated values: check
• bot 1 values removed after transfer: check
• Program terminates?
• Outputs are { 0: 0, 1: 2, 2: 0 }?

What is happening? It should go:

• ...
• bot 1 values removed after transfer
• Next is bot 0
• bot 0 has anticipated values
• bot 0 values removed after transfer
• Next is unchanged, terminating program
• Outputs are { 0: 5, 1: 2, 2: 3 }

Diagnoses complete:
My condition for updating next had a glaring coercion error.

• I use a temporary variable, queuedBot, to track the upcoming bot
• It starts as null
• It becomes a number when a bot that just received a value now has two values

Original code:

next = queuedBot ? queuedBot : next

• Set next depending on queuedBot
• If queuedBot's value is truthy, set next to its value
• Otherwise, leave next unchanged
• Unfortunately, 0 is a falsy value
• So, next never changed after becoming 1

Updated code:

next = queuedBot !== null ? queuedBot : next

Testing again on the example input:

• All bots are processed, and in the expected order!
• The expected outputs are generated!

Time to test on my puzzle input!

I assumed wrong, but the fix was easy

• I assumed there would only be one bot with two values at any given time
• I found out I was wrong when I ran my program on my puzzle input and noticed it only processed three bots!
• When processing the second bot, both recipient bots now had two values
• My algorithm picked the second one as next
• But in the next iteration, that same bot would have no values
• So the program terminated early

The fix: a queue instead of a number

Instead of:

let next = null
// ...process puzzle input
// ......set next to id of only bot with two values

I needed:

let queue = []
// ...process puzzle input
// ......add to queue id of only bot with two values

Then, in my loop, I needed a few changes:

• The condition for running the loop should be whether there are any more items in queue
• The next bot is the one who's id is the first in the queue
• In the check for whether the recipient bot now had two values, I added that bot's id to the queue
• At the end, I removed the first id from the queue

Confirming successful transfers with my puzzle input

• My code was already set up to display the dictionary of outputs
• Prior to the fixes, all outputs were 0 as initially registered
• After the fixes, all outputs were non-0 numbers, seemingly confirming my algorithm was working correctly

I added a condition after sorting the values in the current bot's values array:

If joining the values with a | creates the string '17|61'
  Print the id of the current bot

Running my program again displayed the id.

It was the correct answer!

Part 2

Did I assume wrong again?!

Per the instructions:

Multiply together the values of one chip in each of outputs 0, 1, and 2

• Yikes! I assumed each output would only ever be written to once!
• Were they being written to multiple times?
• Wait. Even if they were, Advent of Code puzzles never succumb to randomness.
• Therefore, it must be that even if outputs are being written to multiple times, at least the ones at 0,1,2 are being written with the same values.

Foolishly, I decided to refactor my code to accommodate arrays as each output key's value.

After doing this and running the program again, my hunch was confirmed:

• Each output was a 1-item array

I probably should have just tried multiplying the numbers I had originally and not updated my code.

Regardless, multiplying my three values generated the correct answer!

I did it!!

• I solved both parts!
• I used one big reduce() to generate both bots and outputs dictionaries!
• I made some incorrect assumptions which I later had to account for!
• I used a simple queue as my next-bot-tracker!
• I had already solved Part 2 by the time I completed Part 1!

This is the core loop of my algorithm, which returns an array where each item is each part's correct answer:

let answers = []
while (queue.length > 0) {
  let bot = bots[queue[0]]
  bot.values.sort((a, b) => a - b)
  if (bot.values.join('|') == '17|61') {
    answers.push(queue[0])
  }
  bot.recipients.forEach((r, i) => {
    switch (r.type) {
      case "bot":
        bots[r.id].values.push(bot.values[i])
        if (bots[r.id].values.length == 2) {
          queue.push(r.id)
        }
        break;
      case "output":
        outputs[r.id] = bot.values[i]
        break;
    }
  })
  bot.values = []
  queue.shift()
}
return answers.concat(outputs[0] * outputs[1] * outputs[2])