День 6 — Перераспределение памяти
Это довольно простая задача, но нам нужно создать несколько вспомогательных функций…

Предыдущие части:
День 1
День 2
День 3
День 4
День 5

Проблема первая:

У программы-отладчика здесь возникла проблема: она пытается исправить процедуру перераспределения памяти, но продолжает застревать в бесконечном цикле.

В этой области имеется шестнадцать банков памяти; каждый банк памяти может содержать любое количество блоков. Целью процедуры перераспределения является балансировка блоков между банками памяти.

Процедура перераспределения работает в циклах. В каждом цикле он находит банк памяти с наибольшим количеством блоков (ничью выигрывает банк памяти с наименьшим номером) и перераспределяет эти блоки между банками. Для этого он удаляет все блоки из выбранного банка, затем переходит к следующему (по индексу) банку памяти и вставляет один из блоков. Это продолжается до тех пор, пока не закончатся блоки; если он достигает последнего банка памяти, он переходит к первому.

Отладчик хотел бы знать, сколько перераспределений может быть выполнено, прежде чем будет создана конфигурация блоков в банках, которая была замечена ранее.

Например, представьте себе сценарий только с четырьмя банками памяти:

Банки начинаются с блоков 0, 2, 7 и 0. В третьем банке больше всего блоков, поэтому он выбирается для перераспределения.

Начиная со следующего банка (четвертого банка), а затем переходя к первому банку, второму банку и т. д., блоки 7 распределяются по банкам памяти. Четвертый, первый и второй банки получают по два блока каждый, а третий банк возвращает один блок. Окончательный результат выглядит так: 2 4 1 2.

Затем выбирается второй банк, поскольку он содержит наибольшее количество блоков (четыре). Поскольку имеется четыре банка памяти, каждый получает по одному блоку. Результат: 3 1 2 3.

Теперь есть связь между первым и четвертым банками памяти, каждый из которых имеет три блока. Первый банк побеждает в ничьей, и три его блока равномерно распределяются по трем другим банкам, не оставляя ни одного: 0 2 3 4.

Выбирается четвертый банк, и его четыре блока распределяются таким образом, что каждый из четырех банков получает по одному блоку: 1 3 4 1.

Выбирается третий банк, и происходит то же самое: 2 4 1 2.

В этот момент мы достигли состояния, которое видели раньше: 2 4 1 2 уже видели. Бесконечный цикл обнаруживается после пятого цикла перераспределения блоков, поэтому ответ в этом примере — 5.

Учитывая начальное количество блоков во входных данных вашей головоломки, сколько циклов перераспределения должно быть завершено, прежде чем будет создана конфигурация, которая была замечена ранее?

Проблема вторая:

Из любопытства отладчик также хотел бы знать размер цикла: начиная с состояния, которое уже было замечено, сколько циклов перераспределения блоков должно быть выполнено, прежде чем то же самое состояние будет замечено снова?

В приведенном выше примере 2 4 1 2 снова появляется после четырех циклов, поэтому ответ в этом примере будет 4.

Сколько циклов содержится в бесконечном цикле, возникающем из-за конфигурации входных данных вашей головоломки?

Решение:

Примечания:

  • Мне было немного лень, поэтому я создал входной массив вручную (см. строку 30)
    Но вы также можете прочитать файл (всего одну строку) и построить массив, используя
    for i := range string.Fields(строка){ … }
  • Пришлось встроить вспомогательные функции «FindPosMax» и «IntToStr», потому что в go нет этой встроенной функции. (строка 9 + 25)
  • В карте «hist», где «перераспределения блоков» будут сохранены в качестве ключа, я использовал счетчик в качестве значения — так что проблема номер два была легко решена; просто вычтите сохраненное значение из фактического счетчика. (см. строки 48 и 45)

Спасибо за чтение и, возможно, комментарии!

SR.