Вирус Sporifica

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

Попробуйте симулятор, используя входные данные головоломки!

Часть 1

1. Еще одна головоломка с бесконечной двухмерной сеткой!
2. Описываем составляющие надеющегося на работу алгоритма
3. Шаг за шагом
4. Тестирование на входном примере
5. Маленькое, но важное забытое условие
6. Прежде чем раскрыть ответ, я хочу его смоделировать!

Еще одна головоломка с бесконечной двухмерной сеткой!

Как обычно:

• Каждая плитка меняется в зависимости от некоторого условия
• Ориентация имеет значение
• Мне нужно отследить определенный тип изменения плитки.

Описываю составляющие, надеюсь, работающего алгоритма

• Счетчик вспышек инфекции
• Двумерный массив, сгенерированный из входных данных
• Устройство отслеживания местоположения носителя вируса (он же текущий узел)
• Устройство отслеживания направления
• Обозначение чистого и зараженного узла (например, . vs. #).
• Способ расширить определенную сторону массива на одну плитку, если текущий узел находится рядом или на краю
• Способ корректировки местоположения текущего узла при расширении 2D массива с верхнего или левого края
• Способ определения узлов слева и справа, независимо от того, куда обращен текущий узел
• Способ определения, произошел ли всплеск на зараженном узле
• Способ определить, вызвал ли всплеск заражение чистого узла.

Это кажется пугающим, но я уже делал многое из этого в подобных головоломках.

Хотя, кажется, что это сложная комбинация множества методов.

Давайте посмотрим, смогу ли я это сделать!

Шаг за шагом

Сгенерируйте сетку

Split the input at each newline character
  Split each string at each character

Установите начальное местоположение текущего узла

Create a 2-element array where:
  1. Half of the length of the grid, rounded down
  2. Half of the length of any array in the grid, rounded down

Для сетки длиной 3: [1,1]
Для сетки длиной 25: [12,12]

Отобразите сетку с выделенным местоположением текущего узла в соответствии с иллюстрациями в инструкции

For each row in the grid
  For each cell in the row
    Unless the cell is the current node
      Pad the cell with a space character on each side
    Otherwise
      Pad the cell with square brackets on each side
  Concatenate the modified cell values into one string
Join each line into one string, separated by newline characters

Успех для примера ввода:

 .  .  # 
 # [.] . 
 .  .  . 

И успех для моего ввода головоломки:

Направления и вращение

Список относительных координат, основанный на направлении текущего узла:

Корректировка списка направлений так, чтобы первый элемент отражал ориентацию недавно повернутого текущего узла:

Краткое изложение моих подпрограмм на данный момент

• Повернуть список направлений так, чтобы направление текущего узла находилось в первом элементе
• Изменить направление текущего узла на основе его состояния
• Изменить содержимое текущего узла в зависимости от его состояния, увеличивая счетчик вспышек заражения, если состояние меняется с clean на infected
• Переместить текущий узел на один вперед в направлении его движения
• Рендерить сетку, обращая внимание на текущий узел

Разворачивать сетку всякий раз, когда текущий узел находится на границе

Если текущий узел находится в любом месте, помеченном *:

***
*.*
***

Разверните сетку так, чтобы она выглядела следующим образом:

.....
.***.
.*.*.
.***.
.....

Мой алгоритм работает следующим образом…

1. Существующие ряды сетки расширяются
2. Создается новая сетка с новым рядом на каждом конце с тем же количеством ячеек, что и в существующих рядах сетки.

Визуальное изображение, для наглядности:

Тестирование на входном примере

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

Результаты теста:

• После 7 всплесков: успех!
• После 70 всплесков: успех!
• После 10000 всплесков: ОШИБКА!
• После 1000 всплесков: ОШИБКА!

О-о-о, что происходило?

Маленькое, но важное забытое условие.

Через несколько минут головной боли я нашел ошибку:

• При расширении сетки я проверял только то, была ли строка или столбец текущего узла первым.
• Мне также нужно было проверить, является ли строка или столбец текущего узла последним.

Тестирую снова:

• После 1000 всплесков: ошибки нет!
• После 10000 всплесков: успех!

Прежде чем раскрыть ответ, я хочу смоделировать его!

• Я действительно хочу увидеть, как ответ появляется после просмотра примера ввода и моего ввода головоломки в симуляторе.
• Итак, теперь я должен создать его

…

Симулятор: создан!

Что я увидел, запустив его на вводе примера:

Что я увидел, запустив его на входе моей головоломки:

И, как и ожидалось, я сгенерировал правильное количество всплесков инфекции!

Часть 2

1. Новые правила и тест производительности?!
2. Шаг за шагом… снова
3. Тестирование на входном примере

Новые правила и тест на производительность?!

• Четыре состояния вместо двух!
• Правило переориентации для каждого состояния!
• Моделирование 10M всплесков (в 1000 раз больше, чем в части 1)

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

Трюк будет заключаться в определении числа всплесков и длины цикла, чтобы я мог извлечь из него 10M.

Но сначала, смогу ли я успешно рефакторить свой алгоритм, чтобы он работал правильно по новым правилам?

Шаг за шагом… снова

Переориентация текущего узла

Новые правила таковы:

[.] => Turn left
[W] => No change
[#] => Turn right
[F] => Turn left or right twice

К счастью, это простой оператор switch с четырьмя случаями.

Переключение состояния текущего узла

Теперь правила и их однобуквенные символы:

Clean nodes become weakened    [.] => [W]
Weakened nodes become infected [W] => [#]
Infected nodes become flagged  [#] => [F]
Flagged nodes become clean     [F] => [.]

К счастью, это тоже простой оператор switch с четырьмя случаями.

Наконец, я обновил условие увеличения количества всплесков заражения, чтобы учесть, что ослабленный узел предшествует узлу заражения.

Тестирование на исходном примере

Запуск моего нового алгоритма для 100 всплесков на входном примере успешно генерирует 26 всплесков инфекции!

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

Обновление моего симулятора

• Поскольку часть 2 требует в 1000k раз больше итераций, я решил не моделировать каждый запуск, а отобразить сетку и всплески инфекции после завершения всех итераций.
• Я ожидал, что симулятор зависнет на неопределенное время, учитывая 10M итераций.
• К моему удивлению, он завершил работу в течение секунды как для примера, так и для моей головоломки!

Что я увидел после 10M итераций для примера:

Что я увидел после 10M итераций для моей головоломки:

Увы, это был правильный ответ!

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

• Я решил обе части!
• Я сделал несколько GIF, чтобы описать несколько моих подпрограмм.
• Я построил симулятор для обеих частей!

Я благодарен за эту визуальную головоломку, которая не была испытанием на производительность, как я ожидал.

Просто хорошая, чистая алгоритмическая забава!