В этом году, в отличие от предыдущих лет, я решил попробовать Advent of Code (AoC), ниже приводится краткое изложение того, что мне понравилось и что я вынес из испытаний.

Язык программирования

Я выбрал язык Elixir, функциональный язык, использующий Erlang VM. Это язык, с которым у меня был некоторый опыт в прошлом, но у меня нет возможности использовать его в повседневной работе, поэтому AoC был хорошим поводом поиграть с ним.

Внешние библиотеки

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

Алгоритмы

  1. В одной из задач мне пришлось создать циклическую структуру данных, и первая идея, которая пришла мне в голову, заключалась в использовании связанных списков, но это было неосуществимо на функциональном языке. После небольшого исследования я остановился на молнии, действительно умном способе отслеживать предыдущие и следующие элементы с помощью двух списков.
  2. Summed Area Table был одним из алгоритмов, о котором я никогда не слышал, и узнать о нем было довольно интересно. Основное использование алгоритма - быстрое и эффективное генерирование суммы значений в прямоугольном подмножестве сетки. Каждая точка в сетке имеет значение всех ранее замеченных точек, поэтому вычитание точек аналогично вычитанию прямоугольных областей.
  3. Обычные графические алгоритмы: Поиск в ширину, поиск в глубину, Дейкстра и A *. Связанный ресурс отлично справляется с объяснением различий, а также плюсов и минусов каждого алгоритма. Я обычно обращаюсь к этому разделу, когда собираюсь реализовать поиск, чтобы выбрать свой алгоритм.
  4. Восхождение на холм как способ начать в случайном месте и идти к локальному максимуму / минимуму. В рассматриваемой задаче я сгенерировал много случайных точек и нашел для каждой локальный максимум, после чего все, что мне нужно было сделать, это вывести максимальное значение среди ранее найденных.
  5. Направленный граф (орграф) как способ найти количество компонент связности, компонент связности - это подграф, в котором любые две вершины соединены друг с другом ребрами. Этот подграф, в свою очередь, не связан ни с какими другими частями исходного графа.
  6. Меньше алгоритма и больше структуры данных, одна из проблем заставила меня использовать Абстрактное синтаксическое дерево, чтобы лучше вычислить мое окончательное решение.

Выводы

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

Последние мысли

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