Фрактальное искусство

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

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

Часть 1

1. Кажется знакомым…
2. Подзадача алгоритма: Разделить массив на секции
3. Подзадача алгоритма: Сгенерировать все возможные варианты строк
4. Подзадача алгоритма: Сопоставить каждый раздел с правилом улучшения
5. Подзадача алгоритма: Вольтрон! (а.к.а. объединить все секции в один квадрат)
6. Скрестим пальцы: собираем все части вместе

Кажется знакомым…

• Двумерный массив .s и #s как on или off.
• Необходимость вращать или переворачивать массивы для соответствия некоторому шаблону
• Конечная цель — раскрыть некое изображение, возможно?

Путешествие назад через Advent of Code здесь работает в мою пользу!

Потому что я успешно решил обе части 2020 Day 20: Jurassic Jigsaw!

И, как часть этого, я написал четыре вспомогательные функции, которые работают с двумерным массивом строк:

• Перевернуть по горизонтали
• Перевернуть по вертикали
• Повернуть по часовой стрелке
• Повернуть против часовой стрелки

Я так благодарен своему прошлому за то, что я упорно писал эти функции.

Подзадача алгоритма: Разделить массив на секции

На каждой итерации я должен разбить пиксели на квадраты 2x2 или 3x3.

Например, разбить этот массив:

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

На эти массивы:

#. .#
.. ..

.. ..
#. .#

Как я могу это сделать?

• С помощью вложенных циклов for.
• И постепенно заполняемого двумерного массива
• Где каждый вложенный массив имеет длину 2 или 3 элемента.

Create an empty array
For i from 0 to the square size, incrementing i by 2 or 3
  For j from 0 to the square size, incrementing j by 2 or 3
    Add to the array a 2D array where each array is the same length as the square size
      And the characters in each cell correspond to the cell the proper number of spaces to the right and then below the current cell
Return the array

Надеюсь, эта анимация лучше объясняет, как это работает:

Подзадача алгоритма: Сгенерировать все возможные строчные вариации

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

../.# => ##./#../...
.#./..#/### => #..#/..../..../#..#

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

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

Мой подход к учету этого?

• Обработать каждое правило улучшения в словарь
• Где ключами являются результирующие квадраты большего размера
• А значения — это Set(), хранящие все возможные вариации исходного, меньшего квадрата.

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

В частности:

• Повернуть по часовой стрелке
• Перевернуть вертикально

Я мог бы выбрать любую из функций вращения и переворачивания.

Кроме того, я должен уметь преобразовывать строки в массивы… и обратно!

Преобразование строки в массив:

Split the string at each slash character
  Split each string at each character

Преобразование массива в строку:

For each array in the array
  Join all characters into a single string
Join each string with a slash character

Собрать все вместе:

Process the puzzle input into a list containing 2-element arrays
  Element 1 is one variant of the pattern to be matched
  Element 2 is the resulting larger square pattern

For each 2-element list
  Accumulate a list with two dictionaries
    The first will store all 2x2 square patterns
    The second will store all 3x3 square patterns
  Store into the appropriate dictionary a key that is the second element's string, where the value is the result of the following operations:
     Create an empty unique set of values
     Do as many times as the area of the square
       Convert the string into an array
       Rotate the array clockwise
       Convert the array into a string
       Add the string into the unique set if not already there
       If the current iteration is divisible by 4
         Convert the string into an array
         Flip the array vertically
         Convert the array into a string
         Add the string into the unique set if not already there
     Set the value equal to the now-filled unique set of strings

Для приведенного выше примера алгоритм генерирует такой список словарей:

[
  { '##./#../...': 
      Set(4) {
      '../#.', '#./..', '.#/..', '../.#'
      } 
  },
  {
    '#..#/..../..../#..#': 
      Set(8) {
      '#../#.#/##.',
      '##./#.#/#..',
      '###/..#/.#.',
      '..#/#.#/.##',
      '.#./#../###',
      '###/#../.#.',
      '.##/#.#/..#',
      '.#./..#/###'
      }
  }
]

Запустив тот же алгоритм для моей головоломки, я заметил, что несколько Set включают только 1 или 2 строки.

Это меня насторожило.

Однако при ближайшем рассмотрении я заметил, что строки были:

../..
###/#.#/###

Как бы вы ни переворачивали и ни вращали эти строки как массивы, в них будет только один вариант.

Теперь я уверен, что смогу:

• Генерировать список всех вариантов один раз для использования в каждой итерации
• Избегать попыток сопоставить строки квадратов 3х3, когда проверяемый квадрат 2х2
• Разделить искусство на более мелкие квадраты
• Определить правильное правило улучшения для каждого квадрата.

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

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

Я имею в виду алгоритм, который превращает их:

#. .#
.. ..

.. ..
#. .#

в эти:

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

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

Как работает мой алгоритм:

For each section
  Generate a stringified version of the array
  Determine which of the two dictionaries to reference: 2x2 or 3x3 patterns
  Initialize a match as empty
  For each key in the proper dictionary
    If any of the strings in the set of values associated with that key match the stringified section array
      Update match to reflect the key associated with the matching string
  Overwrite the section with the array-itized string

Надеюсь, эта анимация лучше объясняет, как это работает:

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

Подзадача алгоритма: Вольтрон! (a.k.a. объединить все секции обратно в один квадрат)

Я имею в виду алгоритм, который превращает это:

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

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

в это:

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

Это потребовало от меня серьезного критического мышления.

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

• С вложенными циклами for.
• и постепенно заполняющимся двумерным массивом
• Где каждый вложенный массив имеет длину N элементов, где N равно длине более полного списка (кратно 2 или 3).

Create an empty array
For i from 0 to the square size, incrementing i by the square root of the square's size
  For j from 0 to the square size, incrementing j by the square root of the square's size
    Add to the array a concatenation of the following strings
      If a multiple of 2:
        Current row and column merged with next row, same column
      If a multiple of 3:
        Current row and column merged with next row, same column, merged with next row, same column
Return each string joined with a slash character

Все это кажется одновременно красноречивым и похожим на спагетти.

Но, по крайней мере, после нескольких тестов, кажется, что это работает!

Главный вопрос в том:

• Смогу ли я пройти хотя бы 5 раундов усиления?

Скрестим пальцы: собираем все части воедино

В двух словах, мой алгоритм должен:

Do 5 times
  1. Divide the array into 2x2 or 3x3 squares
  2. Match each square to an enhancement rule
  3. Merge each larger, enhanced square
  4. Convert the merged string into an array in preparation for the next iteration

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

В остальном шаги 1, 2 и 4 прошли гладко.

Шаг 3, похоже, не сработал правильно только на итерации 5.

Для ясности:

• 3×3 — 4×4 — успех (после добавления условия)
• 4×4 до 6×6 — успех
• 6×6 — 9×9 — успех
• 9×9 — 12×12 — успех
• 12×12 — 18×18 — успех… достаточно… пока что

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

К счастью, мой алгоритм смог успешно сгенерировать это число.

Хотя мой алгоритм не смог создать правильное увеличенное изображение от 12×12 до 18×18, содержимое увеличенного изображения было правильным:

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

После написания вложенного алгоритма reduce() у меня был подсчет.

Виола! Часть 1 решена!

Часть 2

1. Я должен заставить это работать, черт возьми!
2. Создание симулятора

Я должен заставить это работать, черт возьми!

• Как и ожидалось, я должен определить, почему мой алгоритм не может правильно улучшить квадрат 12×12.
• Потому что, черт возьми, я должен выполнить 18 улучшений!

Спустя несколько часов я наконец-то понял, в чем дело!

Мои алгоритмы объединения наивно жестко кодировали количество меньших квадратов для объединения.

Этого хватало до — но не включая — изображение 12×12:

• 4×4 генерирует 4 квадрата 2×2, которые становятся двумя колонками квадратов 3×3.
• 6×6 создает 6 квадратов 2×2, которые становятся 3 колонками квадратов 3×3
• 9×9 генерирует 9 квадратов 3×3, которые становятся 3 колонками квадратов 4×4
• 12×12 создает 36 квадратов 2×2, которые становятся 6 колонками квадратов 3×3.

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

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

В конце концов я обнаружил работающее уравнение.

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

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

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

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

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

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

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

Но, в конце концов, я разобрался.

Эта головоломка и ее аналог — 2020 Day 20 — навсегда займут особое, позорное место в моем мозгу и сердце… потому что это дьявольски приятные алгоритмические головоломки, которые я…… в конце концов…… решил!