В этом году, в отличие от предыдущих лет, я решил попробовать Advent of Code (AoC), ниже приводится краткое изложение того, что мне понравилось и что я вынес из испытаний.
Язык программирования
Я выбрал язык Elixir, функциональный язык, использующий Erlang VM. Это язык, с которым у меня был некоторый опыт в прошлом, но у меня нет возможности использовать его в повседневной работе, поэтому AoC был хорошим поводом поиграть с ним.
Внешние библиотеки
Моя цель состояла в том, чтобы использовать наименьшее количество библиотек, поэтому единственной, которую я использовал, была NimbleParsec, библиотека, созданная Plataformatec, которая очень помогла мне при анализе ввода, предоставленного в нескольких задачах, я определенно рекомендую попробуй.
Алгоритмы
- В одной из задач мне пришлось создать циклическую структуру данных, и первая идея, которая пришла мне в голову, заключалась в использовании связанных списков, но это было неосуществимо на функциональном языке. После небольшого исследования я остановился на молнии, действительно умном способе отслеживать предыдущие и следующие элементы с помощью двух списков.
- Summed Area Table был одним из алгоритмов, о котором я никогда не слышал, и узнать о нем было довольно интересно. Основное использование алгоритма - быстрое и эффективное генерирование суммы значений в прямоугольном подмножестве сетки. Каждая точка в сетке имеет значение всех ранее замеченных точек, поэтому вычитание точек аналогично вычитанию прямоугольных областей.
- Обычные графические алгоритмы: Поиск в ширину, поиск в глубину, Дейкстра и A *. Связанный ресурс отлично справляется с объяснением различий, а также плюсов и минусов каждого алгоритма. Я обычно обращаюсь к этому разделу, когда собираюсь реализовать поиск, чтобы выбрать свой алгоритм.
- Восхождение на холм как способ начать в случайном месте и идти к локальному максимуму / минимуму. В рассматриваемой задаче я сгенерировал много случайных точек и нашел для каждой локальный максимум, после чего все, что мне нужно было сделать, это вывести максимальное значение среди ранее найденных.
- Направленный граф (орграф) как способ найти количество компонент связности, компонент связности - это подграф, в котором любые две вершины соединены друг с другом ребрами. Этот подграф, в свою очередь, не связан ни с какими другими частями исходного графа.
- Меньше алгоритма и больше структуры данных, одна из проблем заставила меня использовать Абстрактное синтаксическое дерево, чтобы лучше вычислить мое окончательное решение.
Выводы
- Большинство проблем стали относительно легкими, когда я получил лучшее представление о том, как анализировать и сохранять ввод, поскольку всегда выбор правильной структуры данных является ключевым при решении проблемы.
- Многие проблемы были решены после обнаружения закономерностей / циклов, и если ваше решение занимает много времени, высока вероятность того, что вы найдете цикл.
- Несколько проблем, связанных с обратным проектированием / оптимизацией, были самыми утомительными, поскольку вы знаете, что найдете решение, когда закончите анализ инструкций, вам просто нужно приложить усилия.
Последние мысли
В целом это было забавное упражнение, и я рекомендую попробовать его, если у вас есть свободное время. Если вы хотите поговорить или застряли в какой-либо из проблем, вы можете найти меня в Твиттере как @bernardo_amc.