Серия трубок


Адвент кода 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 для описания одного из моих небольших алгоритмов.
  • Теперь я превзошел свое количество звезд за весь год!

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

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

Оцените статью
devanswers.ru
Добавить комментарий