DEV Community

Cover image for Memory Reallocation
Robert Mion
Robert Mion

Posted on

1

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

For the example input, that works out as:

  5
- 1
---
  4
Enter fullscreen mode Exit fullscreen mode

In JavaScript, I returned the result of this equation:

cycles - Array.from(stamps).indexOf(banks.join('|'))
Enter fullscreen mode Exit fullscreen mode
  • 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)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay