Конфлаграция сопроцессоров

День 23 Advent of Code 2017

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

• Я создал симулятор.
• Он не генерирует правильный ответ для части 2.
• Но он показывает, как работает правильная программа

Часть 1

1. Решите X, где X =…
3. Обратитесь к дню 18 для обеспечения полного понимания
4. Copy-paste-refactor
5. После устранения неуклюжих ошибок, успех!

Решите X, где X =…

количество раз, когда вызывается инструкция mul.

mul инструкция?

• В качестве входных данных используется программа, содержащая инструкции
• Существует четыре типа инструкций: set, sub, mul и jnz.
• Каждая инструкция работает с двумя операндами: регистр и значение.
• Шаблон каждой инструкции выглядит следующим образом: instruction X Y.
• Регистры являются одной из 8 переменных, обозначенных a-h.
• Все восемь регистров изначально хранят значение 0.

Работа над Advent of Code в обратном направлении, похоже, дает мне преимущество, поскольку эта задача очень похожа на все головоломки Intcode более поздних лет.

По этой причине я уверен, что смогу решить по крайней мере первую часть.

Однако я чувствую, что мне нужно обратиться к головоломке 18-го дня. В инструкции она упоминается как первая головоломка этого типа.

Обращение к Дню 18 для обеспечения полного понимания

• Перенесемся вперед: Я решил часть 1 за день 18.
• Отсутствие контекста было ожидаемым: программа выполняется до тех пор, пока указатель адреса не выйдет за пределы списка инструкций.
• Хорошие новости: я написал алгоритм, который учитывает восемь инструкций… и теперь могу просто скопировать его, удалить некоторые инструкции и обновить там, где это необходимо!

Copy-paste-refactor

• Я начну с повторного использования моего алгоритма из Дня 18, часть 1.
• Затем я удалю несколько неиспользуемых инструкций
• И, наконец, скорректирую инструкцию прыжка, основываясь на определении сегодняшней головоломки.

После устранения неуклюжих ошибок — успех!

• В моем коде из Части 1 Дня 18 отсутствовали некоторые важные возможности, которые были реализованы в коде из Части 2.

Логика, например:

• Учет строк или чисел в качестве операндов X или Y.
• Случай, когда ключ может не находиться в регистрах в момент выполнения инструкции jnz.
• Больше нет случая, когда инструкция может получить только один операнд.

Увы, после решения этих проблем…

…мой алгоритм выдал правильный ответ!

Часть 2

1. Решим X, где X =…
2. Что такого уникального в a и h?
3. Запуск программы с a, установленным на 1
4. Построение симулятора, который можно пройти в своем собственном темпе.

Решите задачу X, где X =…

значение, оставшееся в регистре h, если бы программа выполнялась до конца после установки регистра a в значение 1.

Что уникального в a и h?

• И a, и h присутствуют только в одной инструкции.

Запуск программы с a, установленным на 1

Наблюдения:

• Установка a в 1 первоначально заставляет программу обработать четыре важные инструкции, которые устанавливают регистры b и f.
• Программа проходит через подмножество инструкций, пока g не поднимется обратно до 0.
• Только для того, чтобы через несколько инструкций вернуться к шестизначному отрицательному целому числу путем прыжка назад.
• Но g никогда не будет 0, пока b заставляет g сброситься на какое-то число, отличное от 0, в инструкции, предшествующей прыжку.

Построение симулятора, чтобы пройти его в своем собственном темпе

• Я повторно использовал код из симулятора «День 18, часть 2».
• После множества удалений, я настроил его на выполнение Дня 23, часть 2, с a, начинающимся как 1.

Я быстро увидел части, которые бесконечно зацикливались:

1. jnz g -8
2. jnz g -13

Из-за этой предыдущей инструкции:

И несколько случаев этой инструкции:

Обе инструкции jnz инициализировали циклы, которые сотни тысяч раз приводили g к 0.

Однако я по-прежнему озадачен.

Почему ответ не 1?

Последние несколько инструкций в моей головоломке следующие:

jnz g -13
jnz f 2
sub h -1
set g b
sub g c
jnz g 2
jnz 1 3
sub b -17
jnz 1 -23

• Если g равно 0, то происходит переход к следующей строке.
• Если f равно 0, то происходит переход к следующей строке.
• Я не вижу другого способа получить инструкцию, которая вычитает -1 из h.
• Поскольку никакая другая строка не sets h, она должна начинаться и быть 0, когда выполняется эта инструкция.
• Это приводит к сохранению значения 1.
• Предположим, что следующие две инструкции выполняются
• Чтобы перейти к следующей инструкции, нужно пропустить следующий jnz.
• Потому что jnz 1 3 кажется единственным способом заставить эту программу остановиться.

И как только она остановится, h будет иметь значение 1.

К сожалению, это не правильный ответ.

Итак, как и в Дне 18, часть 2:

• Я в тупике

Празднуем мои достижения

• Я решил часть 1!
• Я построил симулятор, чтобы посмотреть, как работает программа… специально для того, чтобы понять Часть 2!

Обломов:

• Я не понял, что означала инструкция оптимизировать программу: означало ли это изменить входные данные?
• Я ошибался в том, что считал единственным возможным значением, которое h может хранить после завершения программы.
• Таким образом, я не решил часть 2

Я чувствую, что для части 2 дней 18 и 23 мне не хватает какого-то скрытого трюка, чтобы заставить программу прийти к определенной инструкции с нужным значением, сохраненным в регистре.

Возможно, мегатред Reddit’s Solution Megathread сможет раскрыть ответ.