- Адвент кода 2017 День 19
- Часть 1
- Это кажется знакомым…
- Могу я просто посмотреть на это?
- Сколько букв в моей головоломке?
- Решаю не решать вручную
- Решить алгоритмически
- Определите, какая из четырех плиток, прилегающих к +, должна быть следующей трубкой.
- Обновить направление, чтобы учесть поворот за угол
- Тестирование моего алгоритма
- Часть 2
- Воу! Это оно??!!!
- Я сделал это!!!
Адвент кода 2017 День 19
Часть 1
- Это кажется знакомым…
- Могу ли я просто посмотреть?
- Сколько букв в моей головоломке?
- Решение не решать ее вручную
- Решить ее алгоритмически
Это кажется знакомым…
- Мне вспоминается день 13 2020 года — «Безумие шахтной тележки».
- Удивительно — к счастью? — в этой головоломке есть только один движущийся объект: пакет.
- Также отличаются угловые маркеры —
+
вместо/
и.
Могу я просто посмотреть на это?
- Мой пазл большой, да.
- Но не похоже, что там много букв.
- И при тщательном изучении и терпении я, вероятно, мог бы проследить глазами за трубками, записывая буквы по мере их появления.
Прежде чем я это сделаю, несколько упражнений.
Сколько букв в моей головоломке?
Я могу сделать это одним из двух способов:
- Использовать функцию веб-браузера
Find...
при просмотре исходных данных головоломки, искать и записывать каждую заглавную букву алфавита, подсчитывая их по ходу дела. - Написать алгоритм
Второй вариант кажется гораздо более интересным.
Мой алгоритм работает следующим образом:
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
- Ух ты! И это все??!
Воу! Это оно??!!!
- Добавьте переменную для отслеживания количества шагов
- Инкрементируйте эту переменную в трех местах по всему циклу.
- Запустите его на примере: успех!
- Запустить на моем входе: успех!
Я сделал это!!!
- Я решил обе части!
- Я сделал GIF для описания одного из моих небольших алгоритмов.
- Теперь я превзошел свое количество звезд за весь год!
Я решил не делать симулятор.
Мне больше нравится пытаться решить следующую головоломку, чем тратить даже час на создание симулятора для этой головоломки.