Advent of Code 2017 Day 6
Part 1
- Circles, largest numbers, and cycles
- Writing my working algorithm
Circles, largest numbers, and cycles
The algorithm I envision works like this:
16 memory banks: a list with 16 items
Each can hold any number of blocks: each item stores an integer
Each cycle, the bank with the most blocks (if more than one, the first) empties its blocks and spreads them among several others: largest stored integer, at the first known location, save it's block count as n before making it 0, then increment the next n blocks by one
Track each cycle with a counter
After each cycle, store a stringified stamp of the bank's block counts
As soon as a stamp is repeated, return the counter
In JavaScript, I expect to use these built-in mechanisms:
new RegExp(/\d+/g)
Extract each digit from the puzzle input
new Set()
Create a unique set of values
Set.add()
Attempt to add a unique value to a Set
Set.has()
Check whether a Set contains some unique value
Math.max()
Determine the largest number among the banks
Array.indexOf(max)
Determine the location of the first or only largest number
Array.join('|')
Create a stringified stamp of the bank counts
for (let i = 1; i <= count; i++) {}
Reallocate one bank's blocks to several other banks
Array[(location + i) % Array.length]++
Increment the next bank's block count by one, wrapping from last to first bank where necessary
Time to try and build a working algorithm!
Writing my working algorithm
Extract each digit from the puzzle input and coerce to a number
Set cycles at 0
Set stamps as an empty set
Sub-routine: cycle
Concatenate each number with a | character into a string
Add that string to stamps
Determine the largest number among the banks' blocks
Determine the location of the first - or only - occurrence of that number
Set count to the number
Update the first - or only - occurrence of the largest number to 0
For i from 0 up to and including count
Increment by 1 the number in banks at the location resulting from the remainder after following operation:
The sum of the location of the first - or only - occurrence of the most recent largest number, and i
Divided by the length of the list of banks (16)
Increment cycles by 1
Main loop:
Do as long as stamps does not have the stringified version of the latest state of each banks' blocks
Perform a cycle
Return cycles
Part 2
Wow, easier than I anticipated!
- I know the first state of banks to repeat
- Now I must determine how many cycles were between the first occurrence of that state and the second
- I don't have to change my Part 1 algorithm at all!
I just have to calculate a difference:
The difference between:
- The number stored in cycles (Part 1's answer)
- The only location in stamps of the stringified version of the first repeating state of banks
For the example input, that works out as:
5
- 1
---
4
In JavaScript, I returned the result of this equation:
cycles - Array.from(stamps).indexOf(banks.join('|'))
- I had to turn my set of stamps into an Array in order to perform my look-up
I did it!!
- I solved both parts!
- Rather quickly...especially Part 2!
- I think all the practice earlier (later?) this year made me much better at working with circular lists
- I've now beat my second-worst score for stars count! In order, they are:
34,35,*36,40
Top comments (0)