Advent of Code 2019 D07

Чуть раньше я уже писал про Advent of Code — веселый конкурс для программистов, в котором нужно решать задачки и вытаскивать Санту из затруднительных ситуаций.

В задачке седьмого дня я столкнулся с тем, что называется «неполнота документации».

В шестом дне определялись орбиты объектов, но чтобы между этими орбитами переходить, нужно манипулировать ускорителями ракеты.

Первая половина задачи

На корабле Санты пять ускорителей, соединенных последовательно. На каждом ускорителе независимо от остальных исполняется программа (исходные данные задачи). Программа исполняется на интерпретаторе, который разрабатывался в дне №2 и дне №5. Каждый из ускорителей принимает одно значение фазового сдвига из списка от 0 до 4, и входное значение от предыдущего ускорителя (первый ускоритель принимает 0). Значение фазового сдвига должно передаваться только один раз, после чего должно идти значение от предыдущего ускорителя. Даны тестовые программы и данные. Необходимо найти максимальное значение, которое могут выдать ускорители в такой конфигурации.

F# сразу подсказывает, что эти ускорители в функциональном стиле выглядят как AMP |> AMP |> AMP. Одновременно понятно, что эта цепочка должна запускаться ровно столько раз, сколько существует вариантов комбинаций фазовых сдвигов, то есть перестановок, то есть должен быть враппер («обёртка»), в который передается как список значений фазового сдвига, так и исходная программа для всех ускорителей.

Для выдачи всех вариантов перестановок написана функция, которая выдаёт список этих перестановок, которых ожидаемо n!. Потом этот список нужно подать в List.collect — функцию, которая собирает результаты обработки каждой из перестановок функцией AmpChain, и собирает их в список результирующих значений.

Понятно, что тут вместо List.collect можно было бы использовать List.map: в первой лямбда может отображать входное значение на список выходных значений, и List.collect все эти выходные списки соберёт в единый, а List.map отображает одно входное значение на одно выходное (что и происходит в этой ситуации). Но почему-то я в начале выбрал первое и не стал переделывать. Потом результирующий список сортируется и выводится максимальное значение.

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

Объект эмиттера инициализируется значением списка фазовых сдвигов. В нём также есть функция вставки, возвращающая новый эмиттер, в котором вставленное значение находится на втором месте. При считывании значения оно из эмиттера пропадает. Передавая такой объект между ускорителями, каждый ускоритель при необходимости считывает следующее значение, выдаваемое эмиттером. Есть функции возврата списка оставшихся значений, и определен оператор сложения эмиттеров (++).

Функция запуска программы на ускорителе принимает эмиттер, в который при первом запуске вставляется инициализирущий ноль. Эта функция возвращает эмиттер с неиспользованными значениями.

Самое важное, что я усвоил из этих усилителей — С++ нас не покидает, и всегда нужно помнить о передаче объекта по ссылке. Несмотря на то, что типы в F# иммутабельны, элементы массива иммутабельностью не обладают. Более того, передаваемый в функцию массив (а программа для ускорителя — именно массив целых чисел) передаётся по ссылке, а значит любое изменение значения, попавшего в функцию, на самом деле меняет состояние исходной программы, и в итоге все пять экземпляров ускорителя исполняют одну и ту же программу.

После решения этой неочевидной без отладочных сообщений проблемы (внутри экземпляра ускорителя создаём внутреннюю переменную, в которую копируем программу через Array.copy) первую часть задачи я решил.

Вторая половина задачи

Поскольку последовательное подключение выдало Санте явно недостаточную мощность, эльфы научили Санту подсоединить ускорители петлёй обратной связи. Результаты с последнего ускорителя поступают обратно на первый ускоритель, пока все программы на ускорителях не будут приведены в положение остановки. Перезапуск программ не допускается. Значения фазовых сдвигов принимаются от 5 до 9. Необходимо найти максимальное значение вывода.

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

В частности, не ясно поведение программы при выдаче данных (операнд 04). Куда они выдаются? Более того, в предыдущих днях неявно подразумевалось, что выдача данных продолжает выполнение программы в нормальном режиме. Я могу помещать эти значения в эмиттер до востребования их последующими циклами программы, либо могу прерывать программу на этом моменте.

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

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

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