Memory Reallocation
Tags: adventofcode, algorithms, javascript, programming
Published: 2022-08-06 19:40:21

## [Advent of Code 2017 Day 6](https://adventofcode.com/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:
```js
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`