Memory Reallocation

Advent of Code 2017 Day 6

Part 1

1. Circles, largest numbers, and cycles
2. 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