Сигнал часов

Адвент кода 2016 День 25

Мое путешествие на сегодняшний день

• Начал 25-й день… только для того, чтобы понять…
• Решение этой задачи зависит от того, что я написал алгоритмы в рамках нескольких предыдущих дней, а именно: 11, 12, 23
• Перешел к дню 11.
• Завершение этой головоломки, к счастью, не потребовалось — так как я не смог.
• Успешно решил обе части Дня 12, что позволило мне попытаться решить День 23
• Решил часть 1 Дня 23 и, сдавшись, нашел короткий путь к решению части 2
• Вернулся к Дню 25 и обнаружил, что День 12 был единственным необходимым условием: в моей головоломке нет опкода tgl.

Часть 1

1. Грубый процесс исключения, вот и я!
2. Два наблюдения
3. Делаю больше анализа программы
4. Чувствую себя измотанным
5. Reddit, к разоблачению!

Грубый процесс исключения, вот и я!

Мне нужно найти:

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

Думаю, я начну с 0.

Set output as an empty array
Set value as 0

Do until output contains the numbers - in order - 0,1,0,1
  Create a copy of the program
  Set register a to value

  Do as long as output's length is less than four
    Run the next instruction in the program
      If the instruction uses the out opcode, add the appropriate integer to output

  Check whether output contains the numbers - in order - 0,1,0,1

  If it is, escape the loop
  Else, increment value by 1 and reset output to an empty array

Return value

Я предполагаю, что ответ будет где-то в миллионах или миллиардах.

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

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

Два наблюдения

1. Похоже, что выход всегда 0s для четных начальных чисел и 1s для нечетных начальных чисел.
2. Программа работает тем медленнее, чем больше начальное число.

Интересно, что является причиной всего этого?

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

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

• Я добавляю счетчик
• Я увеличиваю счетчик в цикле while.
• Вывожу счетчик на экран при выходе из цикла while.

Я вижу следующее:

0 [ 0, 0 ] 21623
1 [ 1, 1 ] 21623
2 [ 0, 0 ] 21634
3 [ 1, 1 ] 21634
4 [ 0, 0 ] 21645
5 [ 1, 1 ] 21645

Хм:

• Каждая четная пара выполняет одинаковое количество шагов
• Каждая последующая пара выполняет на 11 шагов больше

Также, это тонна операций!

Теперь интересно:

• Как часто меняется регистр b?

Потому что моя головоломка содержит единственную инструкцию out, с b в качестве аргумента.

Ответ?

• Очень много!
• Оно регулярно сбрасывается до 282
• Затем отсчитывает до 0
• Иногда он поднимается выше 2000

Чувствую себя измотанным

• Я действительно ненавижу эти opcode головоломки.
• Они просто слишком утомительны для меня, чтобы их анализировать.
• У меня болит мозг, когда я прохожу их строка за строкой.
• И каждый раз, когда я пытаюсь, я не получаю полезного ответа.

Так что я сдаюсь.

Reddit, для раскрытия!

О, Боже! Тонны кроличьих — нет, кроличьих! — дыр для раскрытия!

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

Как и в случае с Днем 23, начало ответа находилось в двух ключевых утверждениях: пара cpy, которые устанавливали регистры c и b.

Для моей головоломки эти утверждения следующие:

cpy 9 c
cpy 282 b

Умножив их вместе, получаем:

9 * 282 = 2538

Затем мне нужен алгоритм, который определит ближайшее число, большее 2538, среди списка целых чисел, известных как «последовательность Лихтенберга»:

1, 2, 5, 10, 21, 42, 85, 170, 341, 682, 1365, 2730, 5461...

Алгоритм, предложенный решателем, выглядит следующим образом:

Set target as the product of both numbers
Set n to 1
Do as long as n is less than target
  If n is even
    Set n to itself doubled, plus 1
  Else
    Set n to itself doubled
Return n - target

Какой простой, красноречивый алгоритм для генерации списка чисел, показанного выше!

При запуске с использованием моего числа я получаю:

2730 - 2538 = 192

Следовательно, правильный ответ с использованием моей головоломки должен быть 192.

• Я ввожу 192 в качестве первого значения для моего алгоритма.
• Я запускаю его
• На выходе я вижу [0,0,0,0].
• Что происходит?

О боже, опять!?

• Я забыл увеличить pointer на 1 в моем методе out!
• Вы, наверное, шутите!

Исправив это, я решаю запустить программу с 0, ожидая, что она закончится на 192:

• Она заканчивается на 0.
• Что происходит сейчас?

Ну, 0 — это наименьшее целое неотрицательное число, которое подходит.

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

Значит, мне нужно начать с 1, а не с 0.

• Теперь он заканчивается на 34.
• Что происходит сейчас?

Ну, я завершаю цикл, как только output содержит четыре числа: 0, 1, 0, 1.

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

Я расширяю его до 8 чисел.

Теперь он заканчивается на 62.

Я расширяю его до 24 чисел.

Наконец, она заканчивается на 192!

Размышляя над сегодняшней головоломкой

Я просто не смог взломать код!

К счастью, Reddit помог мне выявить всевозможные ошибки в моем алгоритме и анализе:

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

Оглядываясь назад, я очень жалею, что не сделал все три шага правильно.

Потому что мой алгоритм вернул бы 192 почти мгновенно.

Но опять же, если бы это было так, я бы никогда не потратил столько времени на постижение тонких секретов этой программы.

В любом случае, переходим к тому, что, как я надеюсь, не является сборкой, не является поиском пути, сложной, но доступной головоломкой в 24-й день!