Содержание
Адвент кода 2017 День 6
Часть 1
- Круги, наибольшие числа и циклы
- Написание моего рабочего алгоритма
Круги, наибольшие числа и циклы
Алгоритм, который я представляю, работает следующим образом:
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
.