Перераспределение памяти


Адвент кода 2017 День 6

Часть 1

  1. Круги, наибольшие числа и циклы
  2. Написание моего рабочего алгоритма

Круги, наибольшие числа и циклы

Алгоритм, который я представляю, работает следующим образом:

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
Войти в полноэкранный режим Выход из полноэкранного режима

В JavaScript я предполагаю использовать эти встроенные механизмы:

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
Вход в полноэкранный режим Выход из полноэкранного режима

Пора попробовать построить рабочий алгоритм!

Написание моего рабочего алгоритма

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
Вход в полноэкранный режим Выход из полноэкранного режима

Часть 2

Вау, проще, чем я ожидал!

  • Я знаю первое состояние банков, которое нужно повторить.
  • Теперь я должен определить, сколько циклов прошло между первым появлением этого состояния и вторым.
  • Мне совсем не нужно менять алгоритм части 1!

Мне просто нужно вычислить разницу:

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
Войти в полноэкранный режим Выход из полноэкранного режима

Для приведенного примера это выглядит так:

  5
- 1
---
  4
Войти в полноэкранный режим Выход из полноэкранного режима

В JavaScript я вернул результат этого уравнения:

cycles - Array.from(stamps).indexOf(banks.join('|'))
Ввести полноэкранный режим Выход из полноэкранного режима
  • Чтобы выполнить поиск, мне пришлось превратить набор марок в массив.

Я сделал это!!!

  • Я решил обе части!
  • Довольно быстро… особенно часть 2!
  • Я думаю, что вся практика в начале (конце?) этого года сделала меня намного лучше в работе с круговыми списками.
  • Теперь я побил свой второй худший результат по количеству звезд! По порядку, вот они: 34, 35, *36, 40.

Оцените статью
devanswers.ru
Добавить комментарий