Robert Mion

Posted on

# Memory Reallocation

## 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

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
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`