Дуэт

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

Почему не по порядку?

• День 23 ссылался на День 18
• Я не мог честно попытаться выполнить часть 1 дня 23, не построив алгоритм, который решил хотя бы часть 1 дня 18.

Неисправный — но стимулирующий — симулятор

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

Часть 1

1. Решите для X, где X =…
2. Восстановленная частота? Инструкция rcv?
3. Все это кажется очень знакомым.
4. Вот и снова: построение компьютера, обрабатывающего инструкции на основе реестра
5. Написание рабочего алгоритма

Решаем X, где X =…

Значение восстановленной частоты (значение последнего воспроизведенного звука) при первом выполнении инструкции rcv с ненулевым значением

Восстановленная частота? Инструкция rcv?

• Она восстанавливает частоту последнего воспроизведенного звука.
• Но только если значение X не равно нулю.
• К чему относится X?

Восемь инструкций следуют по схеме:

instruction X Y?

• Трехбуквенное имя инструкции
• Как минимум один операнд, обозначаемый X
• Почти всегда второй операнд, обозначаемый Y

rcv — одна из двух инструкций, работающих с одним операндом.

Все это кажется очень знакомым

• 2019 год был наполнен головоломками, в которых мне пришлось конструировать компьютер, выполняющий программы на языке Intcode.
• В тех головоломках тоже были инструкции — хотя в них в качестве обозначений для инструкций использовались целые числа 0-9, тогда как здесь инструкции имеют трехбуквенные имена.
• Эти головоломки также выполнялись до остановки, обычно при попытке адресного трекера получить доступ к инструкции, превышающей размер списка.

В общем, я уверен, что смогу решить эту головоломку…

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

Вот и снова: построение компьютера, обрабатывающего инструкции на основе реестра

Ингредиенты:

• Набор регистров, каждый из которых назван одной буквой и каждый из которых может хранить одно целое число.
• Каждый регистр должен начинаться со значения 0
• 7 инструкций: snd, set, add, mul, mod, rcv, jgz.
• Каждая инструкция ожидает один или два аргумента
• Каждая инструкция всегда обновляет адрес, по которому будет обрабатываться следующая инструкция.
• Каждая инструкция либо ничего не делает, либо устанавливает значение в регистр, либо считывает значение из регистра.
• Упорядоченный список недавно воспроизведенных звуков

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

Настройка:

Split the input at each newline character into an array of strings
For each string
  Split the string at each space character into an array of two or three strings
  Check whether there is a third value
    If there is
      Return a three-element array where the elements are:
        1. A three-letter string
        2. A single-letter string
        3. Either a single-letter string or a number
    If there is no third value
      Return a two-element array where the elements are:
        1. A three-letter string
        2. A single-letter string
Create an empty object to store each register and its current number value
Create an address tracker, starting at 0
Create an empty array to store each played sound

Далее, объект, хранящий каждую функцию инструкции.

С этим я боролся больше всего, потому что по незнанию упустил из виду кучу мелких нестандартных ситуаций, например:

• Каждая функция должна увеличивать адресный трекер на 1, или в случае jgz на определенное количество, или в случае rcv на любой адрес вне списка (в частности, -1).
• Любые функции, которые пытаются обновить значение регистра, должны сначала убедиться, что этот регистр существует и установлен в 0.
• Мне нужно проверить значение, хранящееся в ключе регистра, а не проверять сам ключ регистра (что приводит к NaN).
• Вторым аргументом большинства функций может быть одно из трех значений: 1) undefined, 2) число, 3) строка.

Шесть функций имеют такую схему:

rule(X,Y?) {
  if X is not a key in registers
    create it and set its value to 0
  update the value associated with X
    based on the proper operation and the value of Y
  increment address by 1
}

rcv и jgz имели этот код:

rule(X,Y?) {
  check registers[X] as compared to 0
 if a match
   update address appropriately
 else
   increment address by 1
}

Функция для обработки каждой последующей инструкции:

Sub-routine processor
  Expects one argument: an array

  Invoke the method in registers corresponding to the first three-letter string in the array
  Pass as arguments to that function the second and third elements in the array

Главный цикл:

Do as long as the number stored in address points to a valid location in the list of instructions
  Invoke processor, passing the array at the location stored in address as argument

В заключение:

Return the last element in the ordered list of played sounds

После некоторого поиска неисправностей, часть 1 была решена!

Часть 2

1. Решите для X, где X =…
3. Я создал монстра!
4. Решение проблемы с помощью моей головоломки
5. Ближе… ближе… недостаточно близко
6. Последняя попытка: создание симулятора

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

Количество раз, когда программа 1 посылает значение

Программа 1? Посылает значение?

• Мне нужно запустить две копии программы параллельно.

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

О, Боже. Начинается запугивание.

Каждая программа также имеет свой собственный идентификатор программы (один 0, другой 1); регистр p должен начинаться с этого значения.

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

Каждая программа имеет свою собственную очередь сообщений, поэтому программа никогда не сможет получить сообщение, которое она отправила.

Фух! Это должно сделать все менее сложным.

Хотя, это еще одна вещь, которую мне придется отслеживать.

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

Хм. Итак, правила завершения программы таковы:

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

Мой самый большой вопрос сейчас — это:

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

Я чувствую, что мне нужно тщательно проанализировать новый пример.

А потом немного подумать над всем этим.

Я создал монстра!

• Мне нужны две копии программы.
• И для каждой программы: очередь для принятых сообщений, инструкции, указатель адреса, идентификатор, словарь для регистров и подсчет количества отправленных сообщений.
• Я пошел на все и создал два почти идентичных объекта, полных свойств и методов, каждый из которых хранится в двухэлементном массиве.
• Это тонна дублирующегося кода — только индекс меняется между 0 и 1.
• Но, по крайней мере, для примера ввода, он завершается правильно и с правильным ответом

Устранение неполадок с использованием входных данных моей головоломки

• Я попробовал запустить свой алгоритм, используя входные данные головоломки.
• Я сразу же получил ошибку, потом еще одну, потом еще.
• Похоже, мне нужно сделать один шаг — и, к сожалению, сообщение об ошибке — за один раз.

Чтобы помочь отладке моего кода, я в настоящее время печатаю для каждой копии программы:

• местоположение указателя адреса
• Все поставленные в очередь принятые сообщения
• количество отправленных сообщений
• Регистры и их значения.

Возможно, мне также следует печатать инструкцию, которая будет запущена.

Ближе… ближе… недостаточно близко

Препятствия:

• Моя функция jnz работала не так, как ожидалось. После тщательного анализа я устранил проблему: ошибка копирования-вставки.
• Списки сообщений в очереди каждой программы все росли и росли. После тщательного анализа я изменил свой алгоритм, чтобы попытаться исчерпать очередь сообщений, прежде чем позволить другой программе возобновить работу. Это казалось шагом в правильном направлении, пока…
• Обе программы резко останавливаются на одной и той же строке программы, но у одной полная очередь, а у другой пустая. Я ошарашен тем, что нужно вставить в условие, чтобы мой цикл прерывался только тогда, когда обе очереди пусты и ни одна из них не сдвинула указатель адреса с последней итерации.
• Когда я вложил несколько одинаковых условий в попытках очистить обе очереди, я заметил, что оставшаяся очередь заполняется экспоненциально большим количеством одного и того же целого числа. Этого не может быть.

Я в тупике!

Последняя попытка: создание симулятора

• Я отчаянно хотел посмотреть, как изменяется список сообщений в очереди и значения регистров каждой программы в течение тысяч итераций.
• Поэтому я сделал симулятор, позволяющий делать шаги с шагом, кратным 10: 1, 10, 100, 1000, 10000.
• Это помогло нарисовать картину, доказывающую, что мой алгоритм, должно быть, глючный, поскольку каждый список сообщений в очереди, похоже, экспоненциально растет и заполняется одним и тем же целым числом: 95

Празднование моих достижений

• Я решил часть 1!
• Я написал алгоритм, который решил исходный пример для части 2.
• Я изо всех сил пытался найти и решить часть 2, используя исходные данные моей головоломки.
• Я даже построил симулятор в надежде выявить проблему, лежащую в основе моего алгоритма.
• Я думаю, что теперь у меня достаточно знаний, чтобы попытаться решить Часть 1 Дня 23 — и у меня определенно есть фундамент для создания симулятора для нее!

Бездельники:

• Я не смог определить условие победы, которое заставит мой цикл выйти из игры.
• Я даже не могу сказать вам, является ли то, что мне нужно, чтобы это сработало, другим условием! Это может быть что-то совсем другое!

Эта головоломка — как и головоломка 2018 Day 24 — скорее всего, надолго останется занозой в моем мозгу.