Серия трубок

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

Часть 1

1. Это кажется знакомым…
2. Могу ли я просто посмотреть?
3. Сколько букв в моей головоломке?
4. Решение не решать ее вручную
5. Решить ее алгоритмически

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

• Мне вспоминается день 13 2020 года — «Безумие шахтной тележки».
• Удивительно — к счастью? — в этой головоломке есть только один движущийся объект: пакет.
• Также отличаются угловые маркеры — + вместо / и .

Могу я просто посмотреть на это?

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

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

Сколько букв в моей головоломке?

Я могу сделать это одним из двух способов:

1. Использовать функцию веб-браузера Find... при просмотре исходных данных головоломки, искать и записывать каждую заглавную букву алфавита, подсчитывая их по ходу дела.
2. Написать алгоритм

Второй вариант кажется гораздо более интересным.

Мой алгоритм работает следующим образом:

Generate a 2D array representing the tubes:
  Split the input at each newline character into an array of strings
    Split each string at each character into an array of characters

Identify the letters:
  For each row, accumulate an array of characters
    For each columns, accumulate an array of characters
      If the character is not one of these: `-,|,+, `
        Insert the character into the array

Он работает на примере ввода: ACFEDB.

Это работает на входе моей головоломки: DRSFXNPJLZ.

Вот это да! Всего 11 букв!

Возможно, я смогу решить эту часть вручную!

Если я это сделаю, я захочу сделать GIF.

Решаю не решать вручную

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

Я бы предпочел решить эту задачу алгоритмически.

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

Решить алгоритмически

Ингредиенты для моего рецепта алгоритма:

• Каждая плитка в сетке: это будет двумерный массив символов.
• Количество букв, которые нужно собрать: это будет длина списка букв, найденных в сетке
• Текущее местоположение и направление пакета: это будет массив из 3 элементов, где первые два элемента — это строка и столбец, а третий элемент — один из четырех символов: v^<>.
• Относительные координаты каждого следующего местоположения, основанные на направлении: это будет словарь, где ключами являются четыре символа выше, а значениями — двухэлементные массивы с 0, 1 или -1 для относительной строки и столбца.
• Изначально пустой уникальный набор, который в конечном итоге будет хранить все собранные буквы

Главный цикл:

Do as long as the size of the set of collected letters is not equal to the number of letters in the tubes
  Check the character in the next tube
    If it's a letter:
      Add that letter to the set and continue in the current direction
    Else, if it's a +:
      Determine which of the four tiles adjacent to the + must be the next tube
      If the character at that tile is a letter, add the letter to the set
      Update the direction to account for turning a corner
    Else (meaning it's a - or |):
      Continue in the current direction

Все это кажется простым.

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

Определите, какая из четырех плиток, прилегающих к +, должна быть следующей трубкой.

Эта анимация показывает, как работает мой алгоритм:

Более подробное описание:

Start with a list of the four relative adjacent coordinates:
[[-1,0],[0,1],[1,0],[0,-1]]

Filter that list to exclude the pair that corresponds to the current location of the packet

Change each coordinate into a 3-element array with this blueprint:
['character', row #, column #]

Filter that list to exclude the two items where 'character' is a space

Alas, we now have a 1-item array! Flatten it, resulting in:
['character', row #, column #]

Обновить направление, чтобы учесть поворот за угол

Теперь, когда я знаю расположение и характер следующей трубки, которую должен занять пакет, мне нужно:

• Переместить пакет туда
• Обновить направление пакета
• Записать букву в этом месте, если она там есть.

Для обновления направления пакета я использовал оператор switch.

В зависимости от направления пакета и строки или столбца следующей трубки, обновляем направление в соответствии со следующей схемой:

Тестирование моего алгоритма

Было довольно много работы по устранению неполадок:

• В одном месте я неправильно сослался на строки вместо столбцов.
• В некоторых местах я неправильно сослался на индекс.
• Я собирал каждое число дважды.

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

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

Но прежде чем я это сделаю, мне не терпится узнать, насколько сложнее будет часть 2…

Часть 2

1. Ух ты! И это все??!

Воу! Это оно??!!!

• Добавьте переменную для отслеживания количества шагов
• Инкрементируйте эту переменную в трех местах по всему циклу.
• Запустите его на примере: успех!
• Запустить на моем входе: успех!

Я сделал это!!!

• Я решил обе части!
• Я сделал GIF для описания одного из моих небольших алгоритмов.
• Теперь я превзошел свое количество звезд за весь год!

Я решил не делать симулятор.

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