Тракторная балка

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

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

Часть 1

X = the number of points affected by the tractor beam in the 50x50 area closest to the emitter

Часть 2

X = the sum of (the product of a point's X coordinate and 10000) and (a point's Y coordinate) where that point is the top-left-most point among a 100x100 area of points closest to the emitter where all points are affected by the tractor beam

Пример ввода не приводится

Вместо этого, как и в последних головоломках Intcode, предлагается пример вывода:

       X
  0->      9
 0#.........
 |.#........
 v..##......
  ...###....
  ....###...
Y .....####.
  ......####
  ......####
  .......###
 9........##

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

• Визуализация тяги тягового луча вдоль двумерной области, определяемой беспилотным летательным аппаратом.

Часть 1

1. Генерация списка координат
2. Предполагая, что программа запустится один раз на всех координатах
3. Ошибка: программа запускается на одной координате
4. Генерация изображения тяги тягового луча
5. Подсчет точек

Генерация списка координат

• Мне нужно, чтобы робот посетил X от 0-49 и Y от 0-49.

Другими словами:

[0,0]
[0,1]
...
[0,49]
[1,0]
...
[1,49]
...
[49,49]

Я использовал два цикла для генерации такого списка:

Create coords, an empty list
For row from 0 to 49
  For col from 0 to 49
    Add to coords [row, col]

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

• Потому что именно так работала последняя программа Intcode.
• Мне нужно было отслеживать два числа: 1) вложенный список, и 2) местоположение в этом списке.
• Каждый раз, когда местоположение достигало значения, эквивалентного длине списка, я должен был увеличить местоположение отслеживающего вложенного списка и сбросить другое значение на 0, чтобы все началось снова с начала следующего списка.

Я заставил его работать, только чтобы обнаружить…

Ошибка: программа работает по одной координате

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

For each set of coordinates in coords
  Parse the input string of comma-separated integers into a list of numbers
  Do as long as the value in the list at the current memory address is not 99
    Parse the opcode and parameter mode and perform the instruction
      When the opcode is 3, update input to reflect the correct coordinate
      When the opcode is 4, add to output the new value

Генерирование изображения притяжения тягового луча

• Я подтвердил, что вывод содержит 1s и 0s
• Далее мне нужно сгенерировать двумерный массив, в котором значения будут либо #s, либо .s.
• К счастью, несколько предыдущих головоломок помогли мне натренироваться в решении этой задачи

Create an array with 50 nested arrays, each with 50 items initialized to the space character

For each set of coordinates (and their location) in coords
  Update the value corresponding to the nested array and item in that array as signified by the coordinate's values at locations 2 and 1 (Y,X or Row,Col) based on the following condition:
    If the value at the same location of the coordinate array in coords as in output is 1
      Set the value to #
    Else, if the value in output at the same location is 0
      Set the value to .

Print the grid's values as a square area by concatenating each character in the nested arrays, then joining each string with a newline character

В результате получилось вот такое изображение тягового луча

Подсчет точек

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

К счастью, это был правильный ответ!

Часть 2

1. Сколько времени потребуется для удвоения площади?
2. Заметив рисунок луча
3. Стараюсь изо всех сил вывести ответ
4. Возвращение к задаче пять «дней» спустя
5. Описываю свою новую стратегию

Сколько времени потребуется, чтобы удвоить площадь?

• Я изменил 50 и 100 и снова запустил свою программу.
• Я подождал около 10 секунд, прежде чем увидел, что тяговый луч отрисовался.
• Наибольшее количество смежных точек, затронутых лучом, было около 10.
• Очевидно, что мне пришлось бы отрисовать область размером 1000×1000, чтобы достичь первых смежных точек с общим числом 100 вдоль одной оси.
• Это кажется невыполнимым, поэтому должен быть другой способ.

Заметить узор луча

• Далее я изучил пораженные точки луча.

изо всех сил пытаясь найти ответ.

Я был в восторге, пока не увидел последнюю длину луча: 9.

Он пропустил 8!

И, похоже, это единственное число, которое он пропустил. Почему?

Какова крайняя левая верхняя координата области NxN, где N — от 2 до 8?

• 2×2 — [14,20]
• 3×3 — [26,37]
• 4×4 — [37,53]
• 5×5 — [49,70]
• 6×6 — [60,86]
• 7×7 — [72,103]
• 8×8 — [83,119]

2 [14,20] 
3 [26,37]   +12,+17
4 [37,53]  +11,+16
5 [49,70]   +12,+17
6 [60,86]  +11,+16
7 [72,103]  +12,+17
8 [83,119] +11,+16

Я нашел закономерность!

Теперь воспроизведем арифметические действия.

Start points at [14,20]
For i from 3 thru 100
  Update the values in points such that
    If i is odd, increment each value by 12, 17
    Else, if if i is even, increment each value by 11, 16

Когда цикл завершится, точки содержит:

[ 1141, 1637 ]

Головоломка требует, чтобы я умножил первое значение на 10000 и прибавил второе, которое, по случайному совпадению, просто объединяет оба значения вместе, чтобы сформировать:

11411637

К сожалению, этот ответ слишком высок.

Хорошая новость: ответ с использованием points после 99 итераций слишком мал.

Я близок.

Возможно, я ошибаюсь на один.

Или на 10 000.

Но я не хочу тратить больше попыток.

Возвращаясь к задаче пять «дней» спустя

• В день 24 я решил часть 1, но бросил дело на половине второй.
• Мне было стыдно, что я не нашел правильный ответ на часть 2 сегодняшней головоломки.
• У меня в голове была стратегия, осталось только методом проб и ошибок написать ее и запустить.
• Я знал, что должен попробовать еще раз.

Описание моей новой стратегии

• Несколько решателей на Reddit упоминали, что нужно следовать за крайним левым краем тягового луча.
• Как бы выглядел этот алгоритм?

Ну, луч от Y координат 40-50 выглядит следующим образом, используя мой вариант головоломки:

..........................####....................
...........................####...................
...........................#####..................
............................####..................
.............................####.................
.............................#####................
..............................#####...............
...............................####...............
...............................#####..............
................................#####.............
.................................#####............

Кажется, что левый край всегда увеличивается на одну координату Y и увеличивается либо на ноль, либо на одну координату X.

С чего бы мне начать? Ну, (33,50) — это самый нижний левый край. Как насчет этого?

.................................*    ............

Затем я запускаю свою программу Intcode по трем координатам:

.................................*    ............
.................................123..............

Я уверен, что по крайней мере одна из них приведет к выходу 1.

Вопрос в том, какая из них будет?

[0,0,1]
....#####....
......#####..

[0,1,1]
....#####....
.....#####...

[1,1,1]
....#####....
....######...

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

Я использую короткий цикл — 50-100 раз — для продолжения движения вдоль левого края, пока координаты Y не станут больше 100.

С этого момента я могу выполнить более важную проверку:

• Все ли значения в координатах, образующих квадрат 100×100, крайний левый край которого представляет собой нижний левый край этого квадрата, находятся в границах притягивающего луча?

Говоря иначе, я ищу координату, обозначенную X на диаграмме ниже:

................###############.........
................#################.......
.................########OOOOOOOOOO.....
..................#######OOOOOOOOOO#....
...................######OOOOOOOOOO###..
....................#####OOOOOOOOOO#####
.....................####OOOOOOOOOO#####
.....................####OOOOOOOOOO#####
......................###OOOOOOOOOO#####
.......................##OOOOOOOOOO#####
........................#OOOOOOOOOO#####
.........................XOOOOOOOOO#####

Таким образом, каждый раз, когда я определяю следующую крайнюю левую координату, я запускаю программу для трех других координат: для каждого из трех других «краев» квадрата 100×100.

Я знаю, что нашел его, когда на выходе получаю следующее:

[1,1,1]

Поскольку я начинаю поиск с координаты Y 100, некоторое время я вижу следующее:

[0,0,0]

В конце концов, я вижу исключительно это:

[1,0,1]

Продолжая по 100 раз, я слежу за выводом на консоль, чтобы увидеть первый:

[1,1,1]

Наконец, я обнаружил его!

Это координата:

1135,1724

Помните, что это левая нижняя часть квадрата:

OOO
OOO
XOO

Мне нужна координата левого верхнего угла квадрата:

XOO
OOO
OOO

Это должно быть в:

1135, (1724 - 99)

1135, 1625

Что делает возможным правильный ответ:

11351625

• Я ввожу его, нажимаю [Submit], и Виола!
• Правильный ответ!
• Две золотые звезды!

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

• ОБНОВЛЕНО: Я решил обе части!
• Я решил часть 1!
• Теперь я решил 9/10 компьютерных головоломок Intcode!
• Я сделал GIF в попытках определить закономерность для решения Части 2
• Мне кажется, что я обнаружил применимую закономерность для части 2, тщательно проанализировав луч тяги на площади 200×200.

Облом:

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

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

Я знаю, что в 25-й день будет еще как минимум одна.

С пятого дня по одной было каждый нечетный день.

Поэтому я могу только предположить, что до 25-го дня будет еще как минимум две.

Посмотрим, что приготовил 20-й день.