Космическая полиция

Адвент кода 2019 День 11

Попробуйте симулятор с вводом головоломки!

Задача: Решите задачу для X, где…

Часть 1

X = the number of panels painted at least once by the emergency hull painting robot

Часть 2

X = the eight-letter registration identifier revealed by all white-colored panels after the robot finishes painting

Пример ввода

• Пример Intcode-программы не предлагается
• Изображен пример пути с симулированными направлениями движения, как указано на выходе некоторой воображаемой Intcode-программы

.....   .....   .....   .....   .....
.....   .....   .....   .....   ..<#.
..^..   .<#..   ..#..   ..^..   ...#.
.....   .....   .v...   .##..   .##..
.....   .....   .....   .....   .....

Представляет:

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

Часть 1

1. Компьютер Intcode: Раунд 5!
2. Запуск программы, чтобы увидеть некоторые выходные данные
3. Обновление моего компьютера Intcode для управления всем этим новым состоянием
4. Запуск программы для подтверждения ожидаемых пар ключ-значение
5. Запуск программы для отображения правильного ответа
6. Визуальное представление моего алгоритма

Компьютер Intcode: Раунд 5!

• Хорошие новости: как и в четвертом раунде (он же день 9), новых функций добавлять не нужно!
• Веселая новость: похоже, что эта – и, возможно, будущие головоломки – будут использовать вывод программы, запущенной на моем компьютере Intcode, для генерации правильного ответа.

В этой головоломке

Программа использует инструкции ввода для доступа к камере робота.

Время от времени будут появляться два выходных сигнала:

1. Цвет, в который нужно покрасить панель, на которой находится робот.
2. Направление, в котором должен вращаться робот: по часовой стрелке или против часовой стрелки.

Другие важные замечания:

• После того, как робот повернется, он всегда должен двигаться вперед ровно на одну панель
• Робот начинает движение лицом вверх

Запуск программы для просмотра некоторых выходов

Начиная с 0 в качестве входных данных и никогда не обновляя их:

• На выходе получается более 19 000 0 и 1.

Начиная с 1 в качестве входных данных и никогда не обновляя их:

• Выводится около 500 0s и 1s

Потрясающе!

Обновление моего компьютера Intcode для управления всем этим новым состоянием

Мне нужно отслеживать

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

Текущее направление, в котором движется робот.

Он начинает движение с координаты up.

Таким образом, первое движение происходит по относительной координате -1,0.

А как насчет других направлений?

Up:    -1,0
Right: 0, 1
Down:  1, 0
Left:  0,-1

При сохранении в виде списка:

[[-1,0],[0,1],[1,0],[0,-1]]

Когда роботу дается команда повернуть налево:

• Переместите последний элемент в начало списка.

Когда роботу дается команда повернуть направо:

• Переместите первый элемент в конец списка.

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

Текущее местоположение робота в любой момент времени

Он начинается в точке 0,0.

После поворота переместите робота на один шаг в текущем направлении:

X,Y as current coordinates

New coordinates can be determined:
X + first value in first item
Y + second value in first item

Текущая длина списка целых чисел, выведенных на данный момент.

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

Количество панелей, которые были покрашены хотя бы один раз.

• Я буду использовать словарь/хэш/объект.
• где ключами являются строковые координаты посещенных роботом мест относительно начального положения 0,0.
• А значения – 0 или 1, означающие текущий цвет панели в этой относительной координате.

Целое число, хранящееся в качестве входных данных

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

Новый цвет текущей панели

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

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

Запуск программы для подтверждения ожидаемых пар ключ-значение

Когда вся вышеописанная работа была завершена, я был готов снова запустить свою программу Intcode.

Я увидел следующее сообщение:

'-31|4': 0
'-68|24': 1
...

Успех! Я правильно записывал закрашенные панели!

Запуск программы для отображения правильного ответа

К счастью, это было простое, однострочное дополнение:

Return the count of all keys in the painted panels dictionary

Визуальное представление моего алгоритма

Часть 2

1. Перерисовывание доски для выявления регистрационного идентификатора
2. Создание симулятора рисования робота

Рисование доски для выявления регистрационного идентификатора

Поскольку 0,0 вряд ли будет находиться в левом верхнем углу, мне нужно рассчитать размер доски:

Extract the keys from the painted panels dictionary
  Split each key at the pipe character to generate a 2-element array of strings
    Coerce each string to a number

Calculate the largest/smallest X/Y values

Generate a grid where:
  The height is the difference between max and min Y values
  The width is the difference between max and min X values
  Fill each cell with an empty space character

For each item containing three values (X, Y, panel color) in the painted panels dictionary
  Update the corresponding grid cell with either a # or a space character, depending on the panel color

Display the grid by concatenating each character in each row, then joining each row with a newline character

Write down the revealed registration identifier

При первом запуске этого алгоритма я перепутал оси.

Поменяв местами X и Y, я увидел свой восьмибуквенный идентификатор.

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

Создание симулятора рисования робота

• Я хотел отобразить каждый пиксель идентификатора так, как робот рисует его белым цветом.
• Для этого нужно было запустить программу дважды: один раз, чтобы рассчитать размер сетки, и второй – чтобы закрасить каждую панель.
• Код получился очень запутанным – с большим количеством копирования-вставки и глобальных переменных, – но я добился того, что он работает так, как ожидалось, для моей головоломки.

Попробуйте симулятор с вашей головоломкой!

У меня получилось!!!

• Я решил обе части!
• Я сделал GIF для визуализации моего алгоритма для части 1.
• Я сделал еще один симулятор, на этот раз робота-красителя.
• Теперь я решил пять головоломок Intcode – эта была неожиданной, ее не было в моем первоначальном списке зависимостей (возможно, потому что она не требовала дополнительных возможностей компьютера Intcode)