Advent of Code 2016 Day 10
Part 1
- Passing the buck
- Building a bots dictionary
- Confirming there's one bot with two values
- Transferring microchips to other bots
- Confirming successful transfers with the example input
- I assumed wrong, but the fix was easy
- 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 upcomingbot
- 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 becoming1
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 bothbots
andoutputs
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])
Top comments (0)